Иерархия Хомского - контекстно-зависимые языки типа 1

Question

Я пытаюсь понять иерархию Хомского на разных уровнях.

Я проверил несколько примеров, и вот тот, который я действительно не понимаю. Может быть, кто-то знает, почему этот язык не является контекстно-зависимым:

S → aA 
A → aA | ε
B → bA

Answer 1

Грамматика G То, что вы предоставляете, вне всякого сомнения, не зависит от контекста (каждое правило имеет один нетерминал в LHS и строку терминалов и нетерминалов в RHS). Поэтому язык L то, что он генерирует, не зависит от контекста. Следовательно, поскольку категория контекстно-свободных языков является надлежащим подмножеством категории контекстно-зависимых языков, язык L является контекстно-зависимым. (Я не знаю, где вы читаете этот язык L не зависит от контекста. Либо вы неправильно это прочитали, либо то, что вы прочитали, просто неправильно.)

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

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

1. Грамматика, где все правила имеют вид αAβ → αγβ, где A - нетерминальный символ, а α, β, γ - строки терминалов и нетерминалов.
2. Грамматика, где все правила имеют вид α → β, где α и β - строки терминалов и нетерминалов, но длина α не больше длины β. В качестве исключения может быть правило S → ε для начального символа S (что в противном случае было бы запрещено).

Согласно определению 1, грамматика G является контекстно-зависимым (контекстные строки α и β тривиально пусты). Однако согласно определению 2 грамматика G нет, из-за пустого правила производства для нетерминала A, который не является начальным символом.

Однако возможно предоставить эквивалентную грамматику G', который является контекстно-зависимым в соответствии с обоими определениями и производит тот же язык L, Одна такая грамматика может быть построена следующим образом:

A производит строки с нулем или более "a". Мы можем заменить его определение на:

A → A' | ε
A' → a | aA'

где A'производит строки из одного или нескольких "a". Обратите внимание, что правила для A не являются рекурсивными. Мы можем заменить произведения для A в правилах для S и B, а затем исключить нетерминальный A. Это дает нам:

S → aA' | a
A' → a | aA'
B → bA' | b

Эта грамматика (которая может быть еще более упрощена, если заметить, что A'и S производят один и тот же язык) является контекстно-зависимой согласно обоим определениям выше.