Question

Give a grammar that generates each of the following languages:

(1) L = {a2n cm bm | m ≥ 0, n ≥ 0}

(2) L = {an b2m cn | m ≥ 0, n ≥ 0}

(3) L = {an bm | n+m is even}

(4) L = {an bm | n ≤ m+3}

(5) The complement of the language L = {anbn | n ≥ 0}

Answer 1

The generated grammars for the given L is as follows,

(1) L = {a2n cm bm | m ≥ 0, n ≥ 0}

   

     L = {ε} U {Even length of infinite a’s} U {All odd and even length string cb } U {combination of a’s and cb’s with even length a’s}

     L = {ε,aa,aaaa,aaaaaa,aaaaaaaa,....,cb,cbcb,cbcbcb,.....,aacb,aacbcb,aacbcbcb,.. aaaacb,aaaacbcb,.....}

(2) L = {an b2m cn | m ≥ 0, n ≥ 0}

     L = {ε} U U {Even length of infinite b’s} U {All odd and even length string ac } U {combination of a’s,b’s and c’s with equal number of a’s and c’s and even length b’s}

      L = {ε,bb,bbbb,bbbbbb,bbbbbbbb,....,ac,acac,acacac,.....,abbc,abbbbc,abbbbbbc,.....}

(3) L = {an bm | n+m is even}

No constraint in giving so we can consider n>=0 and m>=0. Considering zero as even number.

     L = {ε} U { even length strings formed consists of ab}

     L={ε,aa,bb,ab,aaaa,aaab,aabb,abbb,bbbb,...}

(4) L = {an bm | n ≤ m+3}

Considering the considering the condition n<= m+3

So,

when m=0,n<=3 can be applied

When m=1,n<=4

When m=2,n<=5.

L = {ε, a,aa,aaa,b,ab,aab,aaab,aaaab,bb,abb,aabb,aaabb,aaaabb,aaaaabb,...}

(5) The complement of the language L = {anbn | n ≥ 0}

Consider L* as the complete closure of all combinations of a’s and b’s

    L = L* - {equal number of a’s and b’s}

       = {unequal number of a’s and b’s}

       = {ε,a,aa,aaa,... b,bb,bbb,...,aab,aaab,...,abb,abbb,....}