Правила производства грамматики

Question

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

Язык состоит из тех строк (из терминалов 'a' и 'b'), гдечисло а = число б.Попытка найти правила производства грамматики, которая определит вышеуказанный язык.

Более формально L (G) = {w |Na (w) = Nb (w)}

Так что я думаю, это должно выглядеть примерно так: L = {ϵ, ab, aabb, abab, abba, bbaa, ... и т. Д.}

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

Answer 1

Я думаю, что это так:

S -> empty  (1)
S -> aSb    (2)
S -> bSa    (3)
S -> SS     (4)

Редактировать: я изменил правила.Теперь вот как производить bbaaabab

S ->(4) SS ->(4) SSS ->(3) bSaSS ->(3) bbSaaSS -> (1)bbaaSS 
  ->(2) bbaaaSbS ->(2) bbaaaSbaSb ->(1)bbaaabaSb ->(1) bbaaabab

Answer 2

Еще один совет: напишите все свои производственные правила так, чтобы они гарантировали Na (w) = Nb (w) на каждом шаге.