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

Язык X = {0^m такой, что m = 2n+1, где n >= 0}

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

Что у меня есть прямо сейчас:

S -> B0C|00

B0 -> DD0|00

BD -> DD

0C -> 0EE|00

EC -> EE

D -> B

E -> C

Но это не работает. Я не могу понять, как удвоить количество нулей.


person Vinay Bangalore Nagaraj    schedule 05.04.2012    source источник


Ответы (1)


Почему бы просто не использовать простую грамматику (даже контекстно-свободную в данном случае, хотя я могу сделать и другую), например:

S -> 0 | 00S
person Eran Zimmerman Gonen    schedule 15.04.2012