Search code examples
complexity-theorycontext-free-grammarautomatacontext-free-language

Provide a context-free grammar that generates odd length language {w = 0*1* : |w| is odd}

Provide a context-free grammar that generates the following language over

Σ = {0,1}: {w = 0*1* : |w| is odd}

My Solution:

S->AB|0|1

A->0A|^

B->1B|^

But using this grammar we are able to create an even number of string.

I want grammar that produces L = {0,1,000,111,001,011,00000,11111,00001,00011....}

Solution

  • An odd number is the sum of an odd number and an even number, so sentences in the language are either an odd number of 0s followed by an even number of 1s, or an even number of 0s followed by an odd number of ones. Moreover, an odd number is an even number plus one; if we make that substitution in the preceding description we get "an even number of 0s followed by either 0 or 1, followed by an even number of 1s". Since every even number is either 0 or two more than an even number, we end up with. 

    S -> A 0 B | A 1 B
A -> ε | A 0 0
B -> ε | B 1 1

    or

    S -> 0 | 1 | 0 0 S | S 1 1