Context sensitive grammar for this language

Question

Language X = { 0^m such that m = 2n+1 where n >= 0}

Can someone help me find the context sensitive grammar for X? Ive been trying for ages but im still not close.

What i have right now:

S -> B0C|00

B0 -> DD0|00

BD -> DD

0C -> 0EE|00

EC -> EE

D -> B

E -> C

But this doesn't work. I can't figure out how to double the number of zeros.

Eran Zimmerman Gonen · Accepted Answer · 2012-04-15 18:56:38Z

1

Why not just use a simple grammar (even context-free in this case, though I can also make one that isn't), such as:

S -> 0 | 00S

answered Apr 15, 2012 at 18:56

4,5171 gold badge22 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

1 Answer 1