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

Question

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

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

S → aA 
A → aA | ε 
B → bA 

Answer 1

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

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

Было бы странно, если бы G, контекстно-свободная грамматика, не были чувствительны к контексту. Независимо от того, является это или нет, это зависит от вашего точного определения контекстно-зависимой грамматики. Как вы можете прочитать, например, в related Wikipedia article, есть, по крайней мере, два альтернативных определений для контекстно-зависимых грамматик:

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

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

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

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

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

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

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

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