Построение распознователя грамматик. Построение распознавателя для заданной грамматики и реализация е. Курсовая работа по дисциплине "Основы дискретной математики"

• Название: Курсовая работа по дисциплине "Основы дискретной математики"
• Анкор: Построение распознователя грамматик
• Дата: 28.04.2022
• Размер: 227 Kb.
• Имя файла: Построение распознавателя для заданной грамматики и реализация е.doc
• Тип: Курсовая; #502707
• страница: 4 из 6

2. Разработка программного продукта

2.1 Построение распознавателя для грамматики

Для заданной в варианте грамматики построить распознаватель.

Вариант 10:
G [Q] = (VT = { a, b, h }; VN = { Q, A, B, H }; P = { Q  a Q H (1);

Q  b a h A (2); A  a b B h (3); H  b B (4); B  a b b H h (5); H   (6) })
Решение:

1 Проверка нетерминальные символов исходной грамматики на достижимость (все правила, в которые входят недостижимые нетерминалы, не нарушая эквивалентности, можно исключить).
(2) (3) (5)  (номера правил)

{ Q }  { Q, A }  { Q, A, B }  { Q, A, B, H }

(недостижимых нетерминалов нет)
2 Проверка нетерминальных символов полученной после выполнения п.1 грамматики на продуктивность (все правила, в которые входят непродуктивные нетерминальные символы, не нарушая эквивалентности, можно исключить).
(6) (5) (3) (2)  (номера правил)

 { Н }  { Н, B }  {Н, B, A } {Н, B, A, Q }

(непродуктивных нетерминалов нет).
3. Определение типа полученной после выполнения предыдущих пунктов грамматики.

После эквивалентных преобразований новая грамматика не изменилась:
G [Q] = (VT = { a, b, h }; VN = { Q, A, B, H };

P = { Q  a Q H (1);

Q  b a h A (2);

A  a b B h (3);

H  b B (4);

B  a b b H h (5);

H   (6) })
4. Определим тип полученной грамматики: по виду правил можно сказать, что это контекстно-свободная грамматика (неправосторонняя - несоответствие в правилах (1), (3) и не является S-грамматикой -есть эпсилон-правило (6)).

Полученная грамматика может быть q -грамматикой- (по определению для такой грамматики множества “Выбор” для правил с одинаковыми левыми частями попарно не пересекаются).

Для такой грамматики множества “Выбор” для правил с одинаковыми левыми частями попарно не пересекаются (пересечение пусто).
“Выбор Q (1) ” = { a }; “Выбор Q (2) ” = b

“Выбор Q (1) ”  “Выбор Q (2) ” = { (пусто) };

“Выбор H (4) ” = { b }; “Выбор H (6) ” = "СледH" = {h, -| }

“Выбор H (4) ”  “Выбор H (6) ” = { (пусто) };
Исследуемая грамматика является q - грамматикой.

5. В соответствии с известным алгоритмом строим для этой грамматики МП-распознаватель:

Алфавит магазинных символов Vмаг = { Q, H, A, B, a, b, h }

Управляющая таблица имеет вид:

	a			b		h		--|
	E			E		E		Доп.
Q	Зам. QH		П	Зам. ahA	П	E		Отв.
A	Зам. bBh		П	E		E		Отв.
В	Зам. bbHh	П		E		E		Отв.
Н	E			Зам. B	П	Выт. H	Д	Выт. H	Д
a	Выт. a		П	E		E		Отв.
b	E			Выт. b	П	E		Отв.
h	E			E		Выт. h	П	Отв.

4 Для проверки правильности работы МП-распознавателя выведем, применяя правила грамматики, правильную цепочку:
(2) (3) (5) (5)

Q  b a h A  b a h b B h  b a h b a b b H h h  b a h b a b b h h

Необработ. цепочка	Обраб. симв.	Верхн. маг. симв	Содерж. магазина	Действия с маг.
bahababbhh --| ahababbhh -| hababbhh-| ababbhh --| babbhh --| abbhh --| bbhh --| bhh--| hh--| h --| --|	b a h a b a b b h h --|	Q a h A b B b b H h h 	Q  a h A  h A  A  bB h  bbHhh  bHhh  Hhh hh h 	Зам. ahA Выт. a Выт. h Зам. b Bh Выт. b Зам. bbHh Выт. b Выт. b Выт. H Выт. h Выт. h Доп.

5. Полное описание МП - распознавателя:

Входной алфавит { a, b, h --|}

Алфавит магазинных символов {Q, A, B, H, a, b, h, }

Множество состояний { S 1 }

Начальная конфигурация (S 1, Q, )

Допускающая конфигурация (S 1, )

Управляющая таблица приведена выше.

6. Программа, реализующая МП - распознаватель, приведена в приложении.