Иерархия Хомского

редактировать

иерархия классов формальных грамматик

В теории формального языка, компьютер науки и лингвистики, иерархия Хомского (иногда называемая иерархией Хомского – Шютценбергера ) является иерархией сдерживания классы формальных грамматик.

Эта иерархия грамматик была описана Ноамом Хомским в 1956 году. Она также названа в честь Марселя-Пауля Шютценбергера, сыгравшего решающую роль в развитие теории формальных языков.

Содержание

1 Формальные грамматики
2 Иерархия
- 2.1 Грамматики типа 0
- 2.2 Грамматики типа 1
- 2.3 Тип 2 грамматики
- 2.4 грамматики типа 3
3 ссылки

Формальные грамматики

Формальные грамматики этого типа состоят из конечного набора производственных правил (левая часть → правая часть), где каждая сторона состоит из конечной последовательности следующих символов:

конечный набор нетерминальных символов (указывающих на то, что какое-то производственное правило еще может быть применено)
конечный набор терминальных символов (указывающий, что никакое производственное правило не может быть применено)
начальный символ (выделенный нетерминальный символ)

A формальная грамматика предоставляет схему аксиомы для (или генерирует) формальный язык, который представляет собой (обычно бесконечное) множество последовательностей символов конечной длины, которые могут быть построены путем применения производственных правил к другой последовательности символов (которая изначально содержит только начальный символ). Правило можно применить, заменив вхождение символов в его левой части на те, которые появляются в его правой части. Последовательность применения правил называется производной. Такая грамматика определяет формальный язык: все слова, состоящие исключительно из терминальных символов, которые могут быть получены путем производных от начального символа.

Нетерминалы часто представлены прописными буквами, терминалы - строчными буквами, а начальный символ буквой S. Например, грамматика с терминалами {a, b}, нетерминалами {S, A, B}, производственными правилами

S → AB

S → ε (где ε - пустая строка)

A → aS

B → b

и начальный символ S, определяет язык всех слов в форме $anbn {\ displaystyle a ^ {n} b ^ {n}}$ $a ^ nb ^ n$ (т.е. n копий a, за которыми следуют n копий b).

Ниже приводится более простая грамматика, которая определяет тот же язык:

Терминалы {a, b}, Нетерминалы {S}, Начальный символ S, Производственные правила

S → aSb

S → ε

В качестве другого примера, грамматика для подмножества игрушек английского языка задается:

terminals: {generate, hate, great, зеленый, идеи, лингвисты}
нетерминалы: {SENTENCE, NOUNPHRASE, VERBPHRASE, NOUN, VERB, ADJ}
правила производства: SENTENCE → NOUNPHRASE VERBPHRASE; NOUNPHRASE → ADJ NOUNPHRASE; NOUNPHRASE → СУЩЕСТВИТЕЛЬНОЕ; VERBPHRASE → VERB NOUNPHRASE; VERBPHRASE → VERB; NOUN → Идеи; СУЩЕСТВИТЕЛЬНОЕ → лингвисты; ГЛАГОЛ → генерировать; ГЛАГОЛ → ненавидеть; ADJ → отлично; ADJ → зеленый

и начальный символ SENTENCE. Пример вывода:

SENTENCE → NOUNPHRASE VERBPHRASE → ADJ NOUNPHRASE VERBPHRASE → ADJ NOUN VERBPHRASE → ADJ NOUN VERB NOUNPHRASE → ADJ NOUN VERB ADJ NOUNPHRASE → ADJ NOUN VERB ADJ NOUNPHRASE → ADJ NOUN VERUN ADJ ADJ NOJ ADJ ADJ ADJ NOJ ADJ ADJ NOJ ADJ ADJ NOJ ADJ ADJ СУЩЕСТВИТЕЛЬНОЕ → великие лингвисты ГЛАГОЛ ADJ ADJ NOUN → великие лингвисты генерируют ADJ ADJ NOUN → великие лингвисты создают великие ADJ NOUN → великие лингвисты генерируют большое зеленое СУЩЕСТВИТЕЛЬНОЕ → великие лингвисты генерируют великие зеленые идеи.

Другие последовательности, которые могут быть получены из этой грамматики: : «идеи ненавидят великих лингвистов», а «идеи порождают». Хотя эти предложения бессмысленны, они синтаксически правильны. Синтаксически неверное предложение (например, «идеи идеи большой ненависти») не может быть получено из этой грамматики. См. «Бесцветные зеленые идеи яростно спят », где есть аналогичный пример, приведенный Хомским в 1957 году; см. грамматику структуры фраз и правила структуры фраз для получения дополнительных примеров естественного языка и проблем формальной грамматики в этой области.

Иерархия

Набор включений, описываемых иерархией Хомского

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

Грамматика	Языки	Автомат	Производственные правила (ограничения) *	Примеры
Тип-0	Рекурсивно перечисляемый	Машина Тьюринга	$γ → α {\ displaystyle \ gamma \ rightarrow \ alpha}$ ${\ displaystyle \ gamma \ rightarrow \ alpha}$ . (без ограничений)	$L = {w \| w {\ displaystyle L = \ {w \| w}$ ${\ displaystyle L = \ {w \| w}$ описывает завершающую машину Тьюринга $} {\ displaystyle \}}$ $\}$
Тип-1	Контекстно-зависимый	Линейный- ограниченная недетерминированная машина Тьюринга	$α A β → α γ β {\ displaystyle \ alpha A \ beta \ rightarrow \ alpha \ gamma \ beta}$ $\ alpha A \ beta \ rightarrow \ alpha \ gamma \ beta$	$L = {anbncn \| п>0} {\ displaystyle L = \ {a ^ {n} b ^ {n} c ^ {n} \| n>0 \}}$ $L=\{a^{n}b^{n}c^{n}\|n>0 \}$
Тип 2	Контекстно-свободный	Без -детерминированный автомат выталкивания	$A → α {\ displaystyle A \ rightarrow \ alpha}$ ${\ displaystyle A \ rightarrow \ alpha}$	$L = {anbn \| n>0} {\ displaystyle L = \ {a ^ {n} b ^ {n } \| n>0 \}}$ $L=\{a^{n}b^{n}\|n>0 \}$
Тип 3	Обычный	Конечный автомат	$A → a {\ displaystyle A \ rightarrow {\ text {a}}}$ ${\ displaystyle A \ rightarrow {\ text {a}}}$ . и. $A → a B {\ displaystyle A \ rightarrow {\ text {a}} B}$ ${\ displaystyle A \ rightarrow {\ text {a}} B}$	$L = {an \| n ≥ 0} {\ displaystyle L = \ {a ^ {n} \| n \ geq 0 \}}$ ${\ displaystyle L = \ {a ^ {n} \| n \ geq 0 \}}$
* Значение символов:. $a {\ displaystyle {\ text {a}}}$ ${\ displaystyle {\ text {a}}}$ = терминал $A {\ displaystyle A}$ $A$ , $B {\ displaystyle B}$ $B$ = нетерминальный $α {\ displaystyle \ alpha}$ $\ alpha$ , $β {\ displaystyle \ beta}$ $\ бета$ , $γ {\ displaystyle \ gamma}$ $\ gamma$ = строка терминалов и / или нетерминалов $α {\ displaystyle \ alpha}$ $\ alpha$ , $β {\ displaystyle \ beta}$ $\ бета$ = возможно пусто $γ {\ displaystyle \ gamma}$ $\ gamma$ = никогда не пусто.

Обратите внимание, что набор грамматик, соответствующий рекурсивным языкам, не является членом этой иерархии; они должны быть правильно между Типом-0 и Типом-1.

Каждый регулярный язык является контекстно-независимым, каждый контекстно-свободный язык является контекстно-зависимым, каждый контекстно-зависимый язык является рекурсивным, и каждый рекурсивный язык рекурсивно перечислим. Все это правильные включения, означающие, что существуют языки с рекурсивным перечислением, которые не являются контекстно-зависимыми, контекстно-зависимыми языками, которые не являются контекстно-независимыми, и контекстно-независимыми языками, которые не являются регулярными.

Грамматики типа 0

Грамматики типа 0 включают все формальные грамматики. Они генерируют в точности все языки, которые может распознать машина Тьюринга. Эти языки также известны как рекурсивно перечислимые или языки, распознаваемые по Тьюрингу. Обратите внимание, что это отличается от рекурсивных языков, которые могут быть решены с помощью постоянно останавливающейся машины Тьюринга.

грамматик типа 1

грамматик типа 1 генерируют контекстно-зависимые языки. Эти грамматики имеют правила вида $α A β → α γ β {\ displaystyle \ alpha A \ beta \ rightarrow \ alpha \ gamma \ beta}$ $\ alpha A \ beta \ rightarrow \ alpha \ gamma \ beta$ с $A {\ displaystyle A}.$ $A$ нетерминал и $α {\ displaystyle \ alpha}$ $\ alpha$ , $β {\ displaystyle \ beta}$ $\ бета$ и $γ {\ displaystyle \ gamma}$ $\ gamma$ строки терминалов и / или нетерминалов. Строки $α {\ displaystyle \ alpha}$ $\ alpha$ и $β {\ displaystyle \ beta}$ $\ бета$ могут быть пустыми, но $γ {\ displaystyle \ gamma}$ $\ gamma$ не должно быть пустым. Правило $S → ϵ {\ displaystyle S \ rightarrow \ epsilon}$ $S \ rightarrow \ epsilon$ разрешено, если $S {\ displaystyle S}$ $S$ не отображается справа от любого правило. Языки, описываемые этими грамматиками, - это в точности все языки, которые могут быть распознаны линейным ограниченным автоматом (недетерминированной машиной Тьюринга, лента которой ограничена константой, умноженной на длину ввода)

Грамматики типа 2

грамматики типа 2 генерируют контекстно-свободные языки. Они определяются правилами формы $A → α {\ displaystyle A \ rightarrow \ alpha}$ ${\ displaystyle A \ rightarrow \ alpha}$ , где $A {\ displaystyle A}$ $A$ является нетерминалом и $α {\ displaystyle \ alpha}$ $\ alpha$ - строка терминалов и / или нетерминалов. Эти языки - это в точности все языки, которые могут быть распознаны недетерминированным автоматом выталкивания. Контекстно-свободные языки - или, скорее, его подмножество детерминированного контекстно-свободного языка - являются теоретической основой фразовой структуры большинства языков программирования, хотя их синтаксис также включает контекстно-зависимый разрешение имени из-за объявлений и области действия. Часто для упрощения синтаксического анализа используется подмножество грамматик, например, LL-анализатор.

грамматики типа 3

грамматики типа 3 генерируют обычные языки. Такая грамматика ограничивает свои правила одним нетерминалом в левой части и правой частью, состоящей из одного терминала, за которым, возможно, следует один нетерминал (правый регулярный). В качестве альтернативы, правая часть грамматики может состоять из одного терминала, которому, возможно, предшествует единственный нетерминал (левый регулярный). Они генерируют одни и те же языки. Однако если объединить правила левого регулярного и правого регулярного, язык больше не должен быть регулярным. Правило $S → ϵ {\ displaystyle S \ rightarrow \ epsilon}$ $S \ rightarrow \ epsilon$ также разрешено здесь, если $S {\ displaystyle S}$ $S$ не отображается справа любого правила. Эти языки являются в точности всеми языками, которые могут быть определены с помощью конечного автомата. Кроме того, это семейство формальных языков можно получить с помощью регулярных выражений. Обычные языки обычно используются для определения шаблонов поиска и лексической структуры языков программирования.

Ссылки

Хомский, Ноам (1959). «О некоторых формальных свойствах грамматик» (PDF). Информация и контроль. 2 (2): 137–167. doi : 10.1016 / S0019-9958 (59) 90362-6.
Хомский, Ноам ; Шютценбергер, Марсель П. (1963). «Алгебраическая теория контекстно-свободных языков». In Braffort, P.; Хиршберг, Д. (ред.). Компьютерное программирование и формальные языки (PDF). Амстердам: Северная Голландия. стр. 118–161.
Дэвис, Мартин Д.; Сигал, Рон; Вейкер, Элейн Дж. (1994). Вычислимость, сложность и языки: основы теоретической информатики (2-е изд.). Бостон: Academic Press, Harcourt, Brace. п. 327. ISBN 0-12-206382-1.