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

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

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

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

Основная статья: Формальная грамматика

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

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

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

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

S → AB

S → ε (куда ε это пустая строка)

А → в качестве

B → б

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

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

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

S → aSb

S → ε

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

терминалы

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

нетерминалы

{ПРИГЛАШЕНИЕ, РОДИТЕЛЬСТВО, ГЛАГОЛ, СУЩЕСТВИТЕЛЬНОЕ, ГЛАГОЛ, ПРИЛОЖЕНИЕ}

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

ПРИГОВОР → СЛОВОСОЧЕТАНИЕ ФРАЗОВЫЙ ГЛАГОЛ

СЛОВОСОЧЕТАНИЕ → ADJ СЛОВОСОЧЕТАНИЕ

СЛОВОСОЧЕТАНИЕ → ИМЯ СУЩЕСТВИТЕЛЬНОЕ

ФРАЗОВЫЙ ГЛАГОЛ → ГЛАГОЛ СЛОВОСОЧЕТАНИЕ

ФРАЗОВЫЙ ГЛАГОЛ → ГЛАГОЛ

ИМЯ СУЩЕСТВИТЕЛЬНОЕ → идеи

ИМЯ СУЩЕСТВИТЕЛЬНОЕ → лингвисты

ГЛАГОЛ → генерировать

ГЛАГОЛ → ненавидеть

ADJ → здорово

ADJ → зеленый

и начальный символ ПРИГОВОР. Пример вывода:

ПРИГОВОР → NOUNPHRASE VERBPHRASE → ADJ NOUNPHRASE VERBPHRASE → ADJ NOUN VERBPHRASE → ADJ NOUN VERB NOUNPHRASE → ADJ NOUN VERB ADJ NOUNPHRASE → ADJ NOUN ГЛАГОЛ ADJ ADJ NOUNPHRASE → ADJ NOUN ГЛАГОЛ ADJ ADJ NOUN → отлично СУЩЕСТВИТЕЛЬНОЕ ГЛАГОЛ ADJ ADJ СУЩЕСТВЕННОЕ → великие лингвисты ГЛАГОЛ ADJ ADJ СУЩЕСТВЕННОЕ → великие лингвисты создают ADJ ADJ NOUN → великие лингвисты создают великие ADJ NOUN → великие лингвисты создают отличный зеленый ИМЯ СУЩЕСТВИТЕЛЬНОЕ → великие лингвисты генерируют прекрасные зеленые идеи.

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

Иерархия

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

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

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

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

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

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

Основная статья: Неограниченная грамматика

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

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

Основная статья: Контекстно-зависимая грамматика

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

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

Основная статья: Бесконтекстная грамматика

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

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

Основная статья: Обычная грамматика

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

Рекомендации

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

• Хомский, Ноам (1959). «О некоторых формальных свойствах грамматик» (PDF). Информация и контроль. 2 (2): 137–167. Дои: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.