Question

Question 3 Give a context-free grammar for each of the following languages over = {a,b,c}. 1. {a^jen: n >0}. 2. {animck : k=n+m} 3. Strings of a's and b's that contain twice as many a's as b's (for example, aba).

Answer 1

Dear Student,

Given,

>= {a,b,c}

Let S is the starting Symbol.

1) Context free Grammar for
(= {a"b2n : n > 0

$aSbble

This production will give the the above grammar.

2. Context free Grammar for    
(= {abck: K= n+m

     
$ → ScT

  $T \rightarrow bTc | \epsilon$

Here c is generated for every a and b to give the required grammar.

3) Context free grammar for , L={ a's are as twice as many as b's}

  $S \rightarrow aSbSa | bSaa | aaSb | SS | \epsilon$

Here every b is associated with two a to give the required grammar.