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

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

История

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

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

Иерархия

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

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

^
Значение символов:
- ${\text{a}}$ = терминал
- $A$ , $B$ = нетерминал
- $\alpha$ , $\beta$ , $\gamma$ = строка терминалов и/или нетерминалов

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

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

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

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

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

С \to аС

С \to а

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

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

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

S \to аСб

С \to аб

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

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

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

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

С \to аВС

S \to асБК

КБ \to Чехия

Чехия \to Венгрия

ВЗ \to ЧМ

Туалет \to БЛ

АБ \to АБ

бБ \to бб

до н. э. \to до н. э.

СС \to СС

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

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

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

См. также

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

Цитаты

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

Ссылки

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

[5] Значение символов:
${\text{a}}$ = терминал
$A$ , $B$ = нетерминал
$\alpha$ , $\beta$ , $\gamma$ = строка терминалов и/или нетерминалов

[2] ${\text{a}}$ = терминал

[3] $A$ , $B$ = нетерминал

[4] $\alpha$ , $\beta$ , $\gamma$ = строка терминалов и/или нетерминалов

[FOOTNOTEChomsky1956-1] Хомский 1956 .

[FOOTNOTEChomskySchützenberger1963-2] Хомский и Шютценбергер 1963 .

[Allott-3] Аллотт, Николас; Лондал, Терье; Рей, Жорж (27 апреля 2021 г.). «Синоптическое введение». Спутник Хомского . стр. 1–17. дои : 10.1002/9781119598732.ch1 . ISBN 9781119598701 . S2CID 241301126 .

[4] Козен, Декстер К. (2007). Автоматы и вычислимость . Тексты для бакалавриата по информатике. Спрингер. стр. 3–4. ISBN 978-0-387-94907-9 .

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

[7] Судкамп, Томас А. (1997) [1988]. Языки и машины: введение в теорию информатики . Ридинг, Массачусетс, США: Эддисон Уэсли Лонгман. п. 310. ИСБН 978-0-201-82136-9 .

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

[Sipser-1st-9] Jump up to: ^а ^б Сипсер, Майкл (1997). Введение в теорию вычислений (1-е изд.). Cengage Обучение. п. 130 . ISBN 0-534-94728-Х . Тезис Чёрча-Тьюринга

[1]

[2]

[3]

[4]

[а]

[5]

[6]

[7]

[8]