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

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

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

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

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

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

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

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

S → AB

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

А → АС

B → b

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

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

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

S → aSb

S → ε

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

терминалы

{генерировать, ненавидеть, здорово, зеленый, идеи, лингвисты}

нетерминалы

{ S, NP, VP, N, V, Adj }

правила производства

S → НП ВП

NP → Adj NP

NP → N

ВП → В НП

ВП → В

N → идеи

N → лингвисты

V → генерировать

V → ненавижу

Adj → отлично

Adj → зеленый

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

S → NP VP → Adj NP VP → Adj N VP → Adj NV NP → Adj NV Adj NP → Adj NV adj Adj NP → Adj NV Adj N → великий NV Adj Adj N → великие лингвисты V Adj Adj N → великие лингвисты генерировать Adj Adj N → великие лингвисты порождают великие Adj N → великие лингвисты создают большие зеленые N → великие лингвисты генерируют великие зеленые идеи.

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

Иерархия

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

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

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

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

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

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

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

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

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

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

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

Грамматики типа 3 порождают обычные языки . Такая грамматика ограничивает свои правила одним нетерминалом в левой части и правой частью, состоящей из одного терминала, за которым, возможно, следует один нетерминал (правый регулярный). В качестве альтернативы, правая часть грамматики может состоять из одного терминала, которому, возможно, предшествует единственный нетерминал (левый регулярный). Они генерируют одни и те же языки. Однако, если правила левого регулярного и правого регулярного правил объединены, язык больше не должен быть регулярным. Правило также разрешено здесь, если оно не отображается справа от любого правила. Эти языки - в точности все языки, которые могут быть определены конечным автоматом . Кроме того, это семейство формальных языков можно получить с помощью регулярных выражений . Обычные языки обычно используются для определения шаблонов поиска и лексической структуры языков программирования. ${\ Displaystyle S \ rightarrow \ varepsilon}$${\ displaystyle 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.