Типы хомского языка
Я пытаюсь понять четыре различных типа языка Хомского, но определения, которые я нашел, на самом деле ничего не значат для меня. Я знаю, что тип 0 - свободная грамматика, тип 1 - контекстно-зависимый, тип 2 - контекстно-свободный, а тип 3 - обычный. Итак, кто-то может объяснить это и поместить в контекст, спасибо.
1 ответ
Язык - это набор слов, принадлежащих этому языку. Однако во многих случаях вместо того, чтобы перечислять каждое слово в языке, достаточно указать набор правил, которые генерируют слова языка (и только те), чтобы определить, что такое рассматриваемый язык.
Примечание: может быть несколько наборов правил, описывающих один и тот же язык.
В целом, чем больше ограничений наложено на правила, тем менее выразительным является язык (тем меньше слов может быть сгенерировано из правил), но легче распознать, принадлежит ли слово к языку, указанному в правилах. Из-за последнего мы хотим идентифицировать языки с наибольшим количеством ограничений по их правилам, которые все еще позволят нам генерировать тот же язык.
Несколько слов о правилах: В общем, вы описываете формальный язык с четырьмя пунктами (AKA a четыре кортежа):
- Набор нетерминальных символов (N)
- Набор терминальных символов (T)
- Свод правил производства (П)
- Начальный символ (S)
Терминальные символы (буквы АКА) - это символы, из которых состоят слова языка, обычно это подмножество строчных английских букв (например, "a", "b", "c")
Нетерминальные символы обозначают промежуточное состояние при генерации слова, указывая, что возможное преобразование все еще может быть применено к промежуточному "слову". Нет совпадения между терминальными и нетерминальными символами (т. Е. Пересечение двух наборов пустое). Символы, используемые для нетерминалов, обычно представляют собой подмножества заглавных английских букв (например, "A", "B", "C")
Правила обозначают возможные преобразования на серии терминальных и нетерминальных символов. Они имеют вид: левая сторона -> правая сторона, где как левая, так и правая сторона состоят из серии терминальных и нетерминальных символов. Пример правила: aBc -> cBa, что означает, что последовательность символов "aBc" (как часть промежуточных "слов") может быть заменена серией "cBa" во время генерации слов.
Начальный символ является выделенным нетерминальным символом (обычно обозначаемым S), который обозначает "корень" или "начало" генерации слова, т.е. первое правило, применяемое в серии генерации слова, всегда имеет стартовый символ как его левая сторона.
Генерация слова успешно завершается, когда все нетерминалы были заменены терминалами (поэтому последнее "промежуточное слово" состоит только из терминальных символов, что указывает на то, что мы пришли к слову рассматриваемого языка).
Генерирование слова является неудачным, когда не все нетерминалы были заменены терминалами, но нет действующих правил производства, которые могут быть применены к текущему промежуточному "слову". В этом случае генерация должна заново отличаться от начального символа, следуя другому пути применения правил производства.
Пример:
L= {T, N, P, S},
где
T= {a, b, c}
N= {A, B, C, S}
P= {S-> A, S-> AB, S-> BC, A-> a, B-> bb, C-> ccc}
который обозначает язык трех слов: "a", "abb" и "bbccc"
Пример применения правил:
S-> AB-> Ab-> АВВ
где мы 1) начали с начального символа (S), 2) применили второе правило (заменив S на AB), 3) применили четвертое правило (заменив A на a) и 4) применили пятое правило (заменив B на bb). Поскольку в результирующем "abb" нет нетерминалов, это слово языка.
Говоря в целом о правилах, греческие символы альфа, бета, гамма и т. Д. Обозначают (потенциально пустую) серию терминальных + нетерминальных символов; греческая буква epsilon обозначает пустую строку (т. е. пустую последовательность символов).
Четыре различных типа в иерархии Хомского описывают грамматики различной выразительной силы (разные ограничения на правила).
Языки, генерируемые грамматиками типа 0 (или неограниченными), наиболее выразительны (менее ограничены). Набор рекурсивно перечислимых языков содержит языки, которые можно сгенерировать с помощью машины Тьюринга (в основном, компьютера). Это означает, что если у вас есть язык, который является более выразительным, чем этот тип (например, английский), вы не можете написать алгоритм, который может перечислять каждое каждое (и только эти) слова языка. У правил есть одно ограничение: левая сторона правила не может быть пустой (никакие символы не могут быть введены "на ровном месте").
Языки, генерируемые грамматиками типа 1 (контекстно-зависимыми), являются контекстно-зависимыми языками. Правила имеют ограничение в виде: альфа A бета -> альфа гамма бета, где альфа и бета могут быть пустыми, а гамма непустой (исключение: правило S->epsilon, которое допускается только в том случае, если начальный символ S не появляется справа от каких-либо правил). Это ограничивает правила наличием по крайней мере одного нетерминала на левой стороне и позволяет им иметь "контекст": нетерминал A в этом примере правила может быть заменен гаммой, только если он окружен символом (" в контексте ") альфа и бета. Применение правила сохраняет контекст (то есть альфа и бета не изменяются).
Языки, генерируемые грамматиками типа 2 (безконтекста), являются языками без контекста. У правил есть ограничение, что они имеют вид: A -> гамма. Это ограничивает правила иметь только один нетерминал слева и не иметь "контекста". По сути, это означает, что если вы видите нетерминальный символ в промежуточном слове, вы можете применить любое из правил, имеющих этот нетерминальный символ на левой стороне, чтобы заменить его правой стороной, независимо от окружения нетерминального символа. Большинство языков программирования имеют контекстно-зависимую генерирующую грамматику.
Языки, генерируемые грамматиками типа 3 (обычные), являются обычными языками. Правила имеют ограничение, что они имеют форму: A->a или A->aB (правило S->epsilon разрешено, если начальный символ S не появляется справа от каких-либо правил), что означает что каждый нетерминал должен генерировать ровно один символ терминала (и, возможно, один нетерминал). Регулярные выражения генерируют / распознают языки этого типа.
Некоторые из этих ограничений могут быть сняты / изменены таким образом, чтобы измененная грамматика имела одинаковую выразительную силу. Измененные правила могут позволять другим алгоритмам распознавать слова языка.
Обратите внимание, что (как отмечалось ранее) язык часто может создаваться несколькими грамматиками (даже грамматиками, принадлежащими к разным типам). Выразительная сила языкового семейства обычно приравнивается к выразительной силе типа наиболее ограничивающих грамматик, которые могут генерировать эти языки (например, языки, генерируемые обычными (тип 3) грамматиками, могут также генерироваться грамматиками типа 2, но их выразительные по-прежнему мощь грамматик типа 3).
Примеры
Обычная грамматика
T= {a, b}
N= {A, B, S}
P= {S-> aA, A-> aA, A-> aB, B-> bB, B-> b}
генерирует язык, который содержит слова, начинающиеся с ненулевого числа "а", за которым следует ненулевое число "б". Обратите внимание, что невозможно описать язык, где каждое слово состоит из числа "а", за которым следует равное количество "б" с регулярными грамматиками.
Контекстная грамматика
T= {a, b}
N= {A, B, S}
P= {S-> ASB, A-> a, B-> b}
генерирует язык, который содержит слова, начинающиеся с ненулевого числа "а", за которым следует равное количество "б". Обратите внимание, что невозможно описать язык, в котором каждое слово состоит из числа "а", за которым следует одинаковое количество "б", а затем такое же количество "с" с помощью контекстно-свободных грамматик.
Контекстно-зависимая грамматика
T= {a, b, c}
N= {A, B, C, H, S}
P= {S-> aBC, S-> aSBC, CB-> HB, HB-> HC, HC-> BC, aB-> ab, bB-> bb, bC-> bc, cC-> cc}
генерирует язык, который содержит слова, начинающиеся с ненулевого числа "а", за которым следует равное количество "б", а затем равное количество "с". Роль H в этой грамматике заключается в том, чтобы разрешить "замену" комбинации CB на комбинацию BC, чтобы B можно было собирать слева, а C - справа. Обратите внимание, что невозможно описать язык, где слова состоят из серии "а", где число "а" является простым с контекстно-зависимой грамматикой, но возможно написать неограниченную грамматику, которая генерирует этот язык.
Есть 4 типа грамматики
ТИП-0:
Грамматика, принятая Неограниченной Грамматикой
Язык, принятый рекурсивно перечислимым языком
Автомат - машина Тьюринга
ТИП-1:
Грамматика принята контекстно-зависимой грамматикой
Язык, принятый контекстно-зависимым языком
Автомат - линейно ограниченный автомат
ТИП-2:
Грамматика, принятая контекстно-свободной грамматикой
Язык, принятый Context free language
Автомат - автомат PushDown
ТИП-3:
Грамматика, принятая обычной грамматикой
Язык, принятый обычным языком
Автомат - конечный автомат
-
Хомский - это нормальная форма, в которой каждая продукция имеет форму:
- A-> BC или A->a
В Хомском может быть две переменные или только один терминал для правила