Построение линейной грамматики для языка

Question

Я нахожу трудности в построении грамматики для языка, особенно с линейной грамматикой.

Может ли кто-нибудь дать мне несколько основных советов / методологий, где я могу построить грамматику для любого языка? заранее спасибо

У меня есть сомнения, правильный ли ответ на этот вопрос "Построить линейную грамматику для языка: правильно"

L ={a^n b c^n | n принадлежит натуральным числам}

Решение:

Праволинейная грамматика:

S -> aS | ЪА

A -> cA | ^

Леволинейная грамматика:

S -> Sc | Ab

A -> Aa | ^

Answer 1

Как указано в комментариях, эти грамматики неверны, так как они генерируют строки не на языке. Вот вывод abcc в обеих грамматиках:

S -> aS -> abA -> abcA -> abccA -> abcc
S -> Sc -> Scc -> Abcc -> Aabcc -> abcc

Также, как указано в комментариях, для этого языка существует простая линейная грамматика, где линейная грамматика определяется как имеющая не более одного нетерминального символа в RHS любой продукции:

S -> aSc | b

Существует несколько общих правил построения грамматик для языков. Это либо очевидные простые правила, либо правила, полученные из свойств замыкания и способа работы грамматик. Например:

1. если L = {a} для символа алфавита a, затем S -> a это гамма для L,
2. если L = {e} для пустой строки e, затем S -> e это грамматика для L,
3. если L = R U T для языков R а также T, затем S -> S' | S'' наряду с грамматикой для R а также T грамматика для L если S' является начальным символом грамматики для R а также S'' является начальным символом грамматики для T,
4. если L = RT для языков R а также T, затем S = S'S'' это грамматика для L если S' является начальным символом грамматики для R а также S'' является начальным символом грамматики для T,
5. если L = R* для языка R, затем S = S'S | e это грамматика для L если S' является начальным символом грамматики для R,

Правила 4 и 5, как написано, не сохраняют линейность. Линейность может быть сохранена для леволинейных и праволинейных грамматик (поскольку эти грамматики описывают обычные языки, а обычные языки закрыты для операций такого типа); но линейность не может быть сохранена в целом. Чтобы доказать это, достаточно примера:

R -> aRb | ab
T -> cTd | cd

L  = RT = a^n b^n c^m d^m, 0 < a,b,c,d
L' = R* = (a^n b^n)*, 0 < a,b

Предположим, что существует линейная грамматика для L, Мы должны иметь производство для символа начала S что-то производит. Чтобы произвести что-то, нам нужна строка терминальных и нетерминальных символов. Чтобы быть линейным, мы должны иметь не более одного нетерминального символа. То есть наша продукция должна иметь форму

S := xYz

где x - строка терминалов, Y - единственный нетерминал, а z - строка терминалов. Если x не пусто, отражение показывает, что единственный полезный выбор a; что-либо еще не может получить известные строки в языке. Точно так же, если z не пусто, единственный полезный выбор d, Это дает четыре случая:

1. x пусто, z пустой. Это бесполезно, так как теперь мы должны решить ту же проблему для нетерминала Y как мы имели для S,
2. x = a, z пустой. Y должен теперь генерировать точно a^n' b^n' b c^m d^m где n' = n - 1, Но тогда точно такой же аргумент применяется к грамматике, чей начальный символ Y,
3. x пусто, z = d, Y должен теперь генерировать точно a^n b^n c c^m' d^m' где m' = m - 1, Но тогда точно такой же аргумент применяется к грамматике, чей начальный символ Y,
4. x = a, z = d, Y должен теперь генерировать точно a^n' b^n' bc c^m' d^m' где n' а также m' как в 2 и 3. Но тогда тот же самый аргумент применяется к грамматике, чей начальный символ Y,

Ни один из возможных вариантов полезного производства для S на самом деле полезно приблизить нас к строке в языке. Таким образом, строки не выводятся, противоречие, означающее, что грамматика для L не может быть линейным.

Предположим, что была грамматика для L', Затем эта грамматика должна генерировать все строки в (a^n b^n)R(a^m b^m)плюс те, кто в e + R, Но он не может генерировать те, что в первом, по аргументу, использованному выше: любая полезная для этой цели продукция не приблизит нас к строке в языке.