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

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

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

Формальные грамматики [ править ]

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

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

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

Нетерминалы часто представлены заглавные буквы, терминалы строчных букв, и стартовый символ по $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 N

→ великие лингвисты

V Adj Adj N

→ великие лингвисты генерировать

Adj Adj N

→ великие лингвисты генерируют великие

Adj N

→ великие лингвисты создают большие зеленые

N

→ великие лингвисты генерируют великие зеленые идеи

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

Иерархия [ править ]

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

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

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

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

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

Грамматики типа 0 [ править ]

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

Грамматики типа 1 [ править ]

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

Грамматики типа 2 [ править ]

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

Грамматики типа 3 [ править ]

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

Ссылки [ править ]

^ Silberztein, Max (2013). «Вычислительные устройства NooJ». Формализация естественных языков с помощью NooJ . С. 1–13. ISBN 978-1-4438-4733-9.
^ Хомский, Ноам (1956). «Три модели для описания языка» (PDF) . Сделки IRE по теории информации (2): 113–124. DOI : 10.1109 / TIT.1956.1056813 .
^ Geuvers, H .; Рот, Дж. (2016). «Приложения, иерархия Хомского и резюме» (PDF) . Обычные языки .
^ Хомский, Ноам (1963). «Глава 12: Формальные свойства грамматик». В Люси Р. Дункан; Буш, Роберт Р .; Галантер, Юджин (ред.). Справочник по математической психологии . II . John Wiley and Sons, Inc., стр. 323–418.
^ Сипсер, Майкл (1997). Введение в теорию вычислений (1-е изд.). Cengage Learning. п. 130 . ISBN 0-534-94728-X. Тезис Черча-Тьюринга

Хомский, Ноам (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.

[1] Silberztein, Max (2013). «Вычислительные устройства NooJ». Формализация естественных языков с помощью NooJ . С. 1–13. ISBN 978-1-4438-4733-9.

[2] Хомский, Ноам (1956). «Три модели для описания языка» (PDF) . Сделки IRE по теории информации (2): 113–124. DOI : 10.1109 / TIT.1956.1056813 .

[3] Geuvers, H .; Рот, Дж. (2016). «Приложения, иерархия Хомского и резюме» (PDF) . Обычные языки .

[4] Хомский, Ноам (1963). «Глава 12: Формальные свойства грамматик». В Люси Р. Дункан; Буш, Роберт Р .; Галантер, Юджин (ред.). Справочник по математической психологии . II . John Wiley and Sons, Inc., стр. 323–418.

[Sipser-1st-5] Сипсер, Майкл (1997). Введение в теорию вычислений (1-е изд.). Cengage Learning. п. 130 . ISBN 0-534-94728-X. Тезис Черча-Тьюринга

[1]