Типы языка Хомского

Ответ 1

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

Примечание: может быть несколько правил, которые присваивают один и тот же язык.

В целом, чем больше ограничений распространяется на правила, тем менее выразительный язык (меньше слов может быть сгенерирован из правил), но легче распознать, принадлежит ли слово языку, указанному в правилах. Из-за последнего мы хотим определить языки с наибольшими ограничениями на их правила, которые все равно позволят нам сгенерировать один и тот же язык.

Несколько слов о правилах. В общем, вы описываете формальный язык с четырьмя элементами (AKA с четырьмя кортежами):

• Набор нетерминальных символов (N)
• Набор терминальных символов (T)
• Набор правил производства (P)
• Символ начала (S)

Символы терминала (буквы АКА) являются символами, из которых состоят слова языка, обычно представляют собой подмножество букв в нижнем регистре (например, "a" , "b" , "c" )

Нетерминальные символы отмечают промежуточное состояние в генерации слова, что указывает на то, что возможное преобразование может быть применено к промежуточному "слову". Не существует перекрытия между терминальным и нетерминальным символами (т.е. Пересечение двух наборов пустым). Символы, используемые для нетерминалов, обычно являются подмножествами прописных английских букв (например, "A", "B", "C" )

Правила обозначают возможные преобразования на серии терминальных и нетерминальных символов. Они имеют форму: left-side → right-side, где левая и правая стороны состоят из серии терминальных и нетерминальных символов. Примерное правило: aBc → cBa, что означает, что серия символов "aBc" (как часть промежуточных "слов" ) может быть заменена серией "cBa" во время генерации слов.

Символ запуска - это выделенный нетерминальный символ (обычно обозначаемый S), который обозначает "корень" или "начало" генерации слова, то есть первое правило, применяемое в последовательности генерации слов, всегда имеет start-symbol как левый.

Генерация слова успешно завершена, когда все нетерминалы были заменены терминалами (поэтому окончательное "промежуточное слово" состоит только из терминальных символов, что указывает на то, что мы пришли к слову языка в вопросе).

Генерация слова не увенчалась успехом, когда не все нетерминалы были заменены терминалами, но нет никаких правил производства, которые могут применяться к текущему промежуточному "слову". В этом случае генерация должна выходить заново из стартового символа, следуя другому пути к правилам производственного правила.

Пример:

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 (контекстно-зависимые), являются языками, чувствительными к контексту. Правила имеют ограничение на то, что они имеют форму: alpha A beta → alpha gamma beta, где альфа и бета могут быть пустыми, а гамма непустая (исключение: правило S- > epsilon, которое разрешено только в том случае, если стартовый символ S не отображается справа от каких-либо правил). Это ограничивает правила наличием по крайней мере одного нетерминального с левой стороны и позволяет им иметь "контекст": не терминал A в этом примере правила может быть заменен гаммой, только если он окружен ( "находится в контексте" ) альфа и бета. Применение правила сохраняет контекст (т.е. Альфа и бета не меняются).

• Языки, сгенерированные грамматиками типа 2 (без контекста), являются языками без контекста. Правила имеют ограничение на то, что они находятся в форме: A → gamma. Это ограничивает правила наличием ровно одного нетерминального с левой стороны и не имеет "контекста". Это по существу означает, что если вы видите нетерминальный символ в промежуточном слове, вы можете применить любое из правил, у которых есть тот нетерминальный символ слева, чтобы заменить его правой стороной, независимо от окружения нетерминального символа. Большинство языков программирования имеют контекстно-свободные генераторные грамматики.

• Языки, сгенерированные грамматиками типа 3 (обычный), являются регулярными. Правила имеют ограничение на то, что они имеют вид: A- > a или A- > aB (правило S- > epsilon разрешено, если стартовый символ S не отображается справа от каких-либо правил), что означает что каждый нетерминал должен выдать ровно один конечный символ (и, возможно, один не терминал). Регулярные выражения генерируют/распознают языки этого типа.

Некоторые из этих ограничений могут быть сняты/изменены таким образом, чтобы модифицированная грамматика имела одинаковую выразительную силу. Модифицированные правила могут позволить другим алгоритмам распознавать слова языка.

Обратите внимание, что (как отмечалось ранее) язык часто может генерироваться несколькими грамматиками (даже грамматиками, принадлежащими к разным типам). Выразительная способность языкового семейства обычно приравнивается к выразительной силе типа наиболее ограничительных грамматик, которые могут генерировать эти языки (например, языки, генерируемые регулярными (Type 3) грамматиками, также могут генерироваться грамматиками типа 2, но их выразительные сила по-прежнему такова, что у грамматики 3-го типа).

<сильные > Примеры

Регулярная грамматика

T = {a, b}

N = {A, B, S}

P = {S- > aA, A- > aA, A- > aB, B- > bB, B- > b}

генерирует язык, содержащий слова, начинающиеся с ненулевого числа "a" , за которым следует ненулевое число "b" . Обратите внимание, что невозможно описать язык, где каждое слово состоит из числа "a, за которым следует равное число" b с правильными грамматиками.

Контекстно-свободная грамматика

T = {a, b}

N = {A, B, S}

P = {S- > ASB, A- > a, B- > b}

генерирует язык, содержащий слова, начинающиеся с ненулевого числа "a" , за которым следует равное число "b" . Обратите внимание, что невозможно описать язык, где каждое слово состоит из числа "a" , за которым следует равное число "b" , за которым следует равное число "c" с контекстно-свободными грамматиками.

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

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 }

генерирует язык, содержащий слова, начинающиеся с ненулевого числа "a" , за которым следует равное число "b" , за которым следует равное количество "c" . Роль H в этой грамматике заключается в том, чтобы включить "замену" комбинации CB на BC-комбинацию, поэтому B можно собрать слева, а C можно собрать справа. Обратите внимание, что невозможно описать язык, где слова состоят из серии "a" , где число "a" является простым с контекстно-зависимыми грамматиками, но можно написать неограниченную грамматику, которая генерирует этот язык.