Контекстно-свободная грамматика для языка

У меня проблема со следующим языком:

альтернативный текст

Я должен написать контекстно-свободную грамматику:

альтернативный текст

который описывает это. Я уже сделал несколько упражнений, но это действительно сложно для меня. Я сижу часами без полезного подхода. Было бы несложно написать грамматику без части N0: (m=l) v (l = 2n) . Но я не знаю, как это сделать. Буду очень благодарен за любой совет.


language-design compiler-construction computation-theory
person Ordo    schedule 22.12.2010    source источник
comment
Вы также можете опубликовать это на cstheory.stackexchange.com, если вы еще этого не сделали.   -  person MatthewMartin    schedule 22.12.2010
comment
@Matthew: cstheory предназначена для вопросов исследовательского уровня.   -  person sepp2k    schedule 22.12.2010

Ответы (1)


arrow_upward
1
arrow_downward

Я не уверен в синтаксисе для G2, но работает следующий CFG:

S = S1 | S2

S1 = S11 C
S11 = <empty> | a S11 b
C = <empty> | c C

S2 = aa S2 c | B
B = <empty> | b B
person Community    schedule 22.12.2010
comment
Честно говоря, это не работает, но все равно спасибо, может быть, я смогу заставить его работать с некоторыми изменениями. Пример, который не работает: S = S2; S2 = a S2 cc, где S2 = B = ‹пусто›. Это создаст акк, который не разрешен. - person Ordo; 22.12.2010