0 votes
32 views

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}.$
| 32 views

## 1 Answer

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 | ε
by Loyal (5.2k points)
edited by

0 votes
0 answers
1
0 votes
0 answers
4