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

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

Включения множества, описываемые иерархией Хомского

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

История

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

Независимо и вместе с лингвистами математики разрабатывали вычислительные модели (автоматы). Анализ предложения на языке аналогичен вычислениям, и грамматики, описанные Хомским, одновременно напоминают и эквивалентны по вычислительной мощности различным моделям машин. ^[4]

Иерархия

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

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

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

Обычные (Тип-3) грамматики

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

Например, регулярный язык генерируется грамматикой типа 3 со следующими продуктами . ${\displaystyle L=\{a^{n}|n>0\}}$ ${\displaystyle G=(\{S\},\{a,b\},P,S)}$ ${\displaystyle P}$

С → аС

С → а

Контекстно-свободные (Тип 2) грамматики

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

Например, контекстно-свободный язык генерируется грамматикой типа 2 со следующими продуктами . ${\displaystyle L=\{a^{n}b^{n}|n>0\}}$ ${\displaystyle G=(\{S\},\{a,b\},P,S)}$ ${\displaystyle P}$

S → аСб

С → аб

Язык контекстно-свободный, но не регулярный (по лемме о накачке для регулярных языков ).

Контекстно-зависимые (Тип 1) грамматики

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

Например, контекстно-зависимый язык генерируется грамматикой типа 1 со следующими продуктами . ${\displaystyle L=\{a^{n}b^{n}c^{n}|n>0\}}$ ${\displaystyle G=(\{S,A,B,C,W,Z\},\{a,b\},P,S)}$ ${\displaystyle P}$

С → аВС

S → асБК

ЦБ → З

Чехия → Венгрия

ВЗ → ЧК

Туалет → БЛ

АБ → АБ

бБ → бб

до н. э. → до н. э.

СС → СС

Язык контекстно-зависим, но не контекстно-свободен (согласно лемме о накачке для контекстно-свободных языков ). Доказательство того, что генерирует эта грамматика, схематично описано в статье Контекстно-зависимые грамматики . ${\displaystyle L=\{a^{n}b^{n}c^{n}|n>0\}}$

Рекурсивно перечислимые (Тип-0) грамматики

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

Смотрите также

• Нормальная форма Хомского

Цитаты

1. Аллотт, Николас; Лондал, Терье; Рей, Жорж (27 апреля 2021 г.). «Синоптическое введение». Товарищ Хомскому : 1–17. дои : 10.1002/9781119598732.ch1. ISBN 9781119598701. S2CID  241301126.
2. Хомский 1956.
3. Хомский и Шютценбергер 1963.
4. Козен, Декстер С. (2007). Автоматы и вычислимость. Тексты для бакалавриата по информатике. Спрингер. стр. 3–4. ISBN 978-0-387-94907-9.
5. Геверс, Х.; Рот, Дж. (2016). «Приложения, иерархия Хомского и резюме» (PDF) . Обычные языки . Архивировано (PDF) из оригинала 19 ноября 2018 г.
6. Судкамп, Томас А. (1997) [1988]. Языки и машины: введение в теорию информатики . Ридинг, Массачусетс, США: Эддисон Уэсли Лонгман. п. 310. ИСБН 978-0-201-82136-9.
7. Хомский, Ноам (1963). «Глава 12: Формальные свойства грамматик». В Люсе, Р. Дункан; Буш, Роберт Р.; Галантер, Юджин (ред.). Справочник по математической психологии . Том. II. John Wiley and Sons, Inc., стр. 323–418.
8. Сипсер, Майкл (1997). Введение в теорию вычислений (1-е изд.). Cengage Обучение. п. 130. ИСБН 0-534-94728-Х. Тезис Чёрча-Тьюринга

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

• Хомский, Ноам (1956). «Три модели описания языка» (PDF) . IRE Транзакции по теории информации . 2 (3): 113–124. дои : 10.1109/TIT.1956.1056813. S2CID  19519474. Архивировано (PDF) из оригинала 07 марта 2016 г.
• Хомский, Ноам (1959). «О некоторых формальных свойствах грамматик» (PDF) . Информация и контроль . 2 (2): 137–167. дои : 10.1016/S0019-9958(59)90362-6 .
• Хомский, Ноам ; Шютценбергер, Марсель П. (1963). «Алгебраическая теория контекстно-свободных языков». В Браффорте, П.; Хиршберг, Д. (ред.). Компьютерное программирование и формальные системы (PDF) . Амстердам: Северная Голландия. стр. 118–161. Архивировано (PDF) из оригинала 13 июня 2011 г.