Является ли эта грамматика {a^2n b^n | n> = 0} контекст бесплатно или нет?

Question

Этот контекст грамматики свободен или нет?

{a^2n b^n | n >= 0} 

Answer 1

Объект, о котором вы спрашиваете, не является грамматикой, а языком: набором строк. Набор строк может быть потенциально описан без контекстной грамматики в том смысле, что существует какая-то грамматика, правила которой генерируют именно этот набор строк.

В этом случае расширение вашего набора выглядит следующим образом:

{ "", "aab", "aaaabb", "aaaaaabbb", ... } 

Это множество всех строк, состоящих из четного числа a -s, а затем половину, как многие b -s.

Этот набор может быть сгенерирован повторений следующих правил:

1. пустая строка в наборе.
2. Если в наборе находится строка s, тогда строка "aa" + s + "b" находится в комплекте.

То есть из любой строки, которая находится в наборе, мы можем сформировать новую строку, которая является также в наборе, просто добавив две a -s на левой и b справа. Вместе с правилом базового случая, что пустая строка находится в наборе, эти правила описывают весь набор.

И эти правила эквивалентны, и может быть записана в виде, контекстно-свободной грамматики:

s -> "" 
    -> "aa" s "b" 

грамматика является контекстно-свободным, потому что он имеет только правила вида «а -> символы ... ": левая сторона имеет только один нетерминальный символ. Поэтому ни одно из поколений не зависит от контекста: один символ берется и заменяется изолированно в соответствии с некоторым доступным правилом.