Give a contextfree grammar to generate each language below G

Give a context-free grammar to generate each language below.

Give a context-free grammar to generate each language below. (a) L_1 = {omega {0, 1}*| the length of omega is odd} (b) L_2 = {omega {0, 1}*| the length of omega is odd and omega starts with 1} (c) L_3 = {omega {0, 1}*| the length of omega is odd and omega starts and ends with 1} (d) L_4 = {omega {0, 1}*| the length of omega is odd and the middle symbol of omega is 1}.

Solution

CFG:
Ans a)
S->0|1|0S0|0S1|1S0|1S1

strings generated with this CFG are : 1,0,111,101,000,010, 10101,01010,11011,00100,11111,00000 ..etc

Ans b)
S->1A1|1A0|1
A->1A1|0A0|1A0|0A1|1|0

strings generated with this CFG are : 1, 111, 101, 100, 10101, 11011, 11111, 11110 ..etc

Ans c)
S->1A1|1
A->1A1|0A0|1A0|0A1|1|0

strings generated with this CFG are : 1, 111, 101, 10101, 11011, 11111, 11011 ..etc

Ans d)
S->1|0S0|0S1|1S0|1S1

strings generated with this CFG are : 1, 111, 010, 10101, 00100, 11111,..etc