Иерархия порождающих грамматик Хомского

 

Структура цепочки определяет порядком её вывода из начального символа по правилам грамматики. Для построения распознавателя необходимо иметь алгоритм, который по заданной грамматике строит вывод любой цепочки языка, порождаемого этой грамматикой. Доказано, что такого алгоритма для произвольной грамматики Хомского не существует.

Возможны два пути решения этой проблемы:

1) Для каждой конкретной грамматики Хомского разрабатывать свой алгоритм распознавания.

2) Наложить ограничения на правила грамматики и выделить подклассы грамматик, для которых алгоритм распознавания не только существует, но и является достаточно определимым.

Классификация грамматик Хомского

 

Тип	Вид правил	Название грамматики	Название языка
	a ® b	произвольная	рекурсивно-перечислимый
	aАb ® agb	контекстно-зависимая	контекстно-зависимый
	А ® g	контекстно-свободная	контекстно-свободный
	А ® e A ® aB A ® a	Автоматная	автоматный

 

Для 0-типа алгоритм распознавания не существует.

Для 1-типа – существует, но не эффективен.

Для 2-типа – существует, и он более эффективен.

Для 3-типа – существует простой и эффективный алгоритм.

 

Замечания:

1) Существуют контекстно-свободные языки, которые не являются автоматными.

2) Существуют рекурсивно-перечислимые языки, которые не являются контекстно-свободными.

3) Многие специализированные языки являются автоматными.

4) Почти все универсальные алгоритмические языки являются контекстно-свободными.

5) Теория трансляции имеет дело только с контекстно-свободными и автоматными языками.

Вопросы и упражнения

1. Приведите примеры правил для каждого типа грамматик.

2. Определите типы следующих грамматик:

a) G₁= {{a, b, c}, {A, B, S}, S, R}

R: S®AaB; A®Bbc; B®ab.

b) G= {{a, b, c}, {A, B, S}, S, R}

R: S®AaB; aAb®aBbcb; aB®ab.

c)G= {{a, b, c}, {A, B, S}, S, R}

R: S®aA; A®cB; B®e

3. Для каких из данных грамматик существует самый эффективный алгоритм распознавания цепочек?

Автоматные языки и грамматики