Give a CFG for the language of all string over the alphabet (0,1) that consist of:

Question

Give a CFG for the language of all string over the alphabet (0,1) that consist of:

1.x O’s, where x is even and >= 0, followed by

2.y 1’s, where y is even and >=0, followed by

3.x O’s(same x as in the first item above)

For instance, these strings are in the language: ∈, 001100, 11, 00000000, 00001111110000.

The start symbol of your CFG must be called S, and you can use only one other non-terminal symbol, which you have to call L. You must not use any regex-like shortcuts (i.e., no “+” and no “*” to denote multiple occurrences of a symbol).

 

Summary

The alphabet for the given language is {0, 1}.

The language is {02n12m02n | n>=0, m>=0}

The CFG is:

S -> 00S00 | 00A00 | ε

A -> 1A1 | ε

Explanation

Give Language restrictions:-

→x 0’s, where x is even and >=0,

→y 1’s, where y is even and >= 0,

→x 0’s, x as in the first.

L= {∈, 001100, 11, 0000 0000, 0000 111111 0000,  ………}

CFG

Alphabet {0,1}

Language, L= {0²ⁿ1^2m0²ⁿ|n>=0,m>=0}

Grammar, G

CFG

S—>00S00 | 00A00 |e

A—>1A1 | €

Verify :-

S—>€

S—>00A00—>001A100—>001100

S—>00S00—>0000S0000—>00000000

S->00S00—>0000A0000->00001A10000->000011A11000000 –>000011110000

 

Also, read Improving Database Design through Normalization.