retagged by
3,062 views
0 votes
0 votes

Give context-free grammars that generate the following languages$.$ In all parts, the alphabet $\sum$ is $\{0,1\}.$

  1. $\text{{w| w contains at least three 1’s}}$
  2. $\text{{w| w starts and ends with the same symbol}}$
  3. $\text{{w| the length of w is odd}}$
  4. $\text{{w| the length of w is odd and its middle symbol is a 0}}$
  5. $\text{{$w|w=w^{R},$that is, w is a palindrome}}$
  6. $\text{The empty set}.$
retagged by

1 Answer

0 votes
0 votes
a.  S->A1A1A1A

     A->0A | 1A |  ε

b.  S->0A0 | 1A1 | 0 | 1 | ε

      A->0A | 1A | ε

c.   S->0S0 | 1S1 | 0S1 | 1S0 | 0 | 1

d.   S->0S0 | 1S1 | 0S1 | 1S0 | 0

e.   S->0S0 | 1S1 | 0 | 1 | ε
edited by

Related questions

0 votes
0 votes
0 answers
1