# Michael Sipser Edition 3 Exercise 2 Question 6 (Page No. 155)

48 views

Give context-free grammars generating the following languages.

1. The set of strings over the alphabet $\{a,b\}$ with more $a's$ than $b's$
2. The complement of the language $\{a^{n}b^{n}\mid n\geq 0\}$
3. $\{w\#x\mid w^{R}$ $\text{is a substring of$x$for }$ $w,x \in\{0,1\}^{*}\}$
4. $\{x_{1}\#x_{2}\#...\#x_{k}\mid k\geq 1,$ $\text{each}$  $x_{i}\in\{a,b\}^{*},$ $\text{and for some i and }$ $j,x_{i}=x_{j}^{R}\}$
0
question 3 is a regular language I think?

RE=(a+b)*#(a+b)*
0
How come?
0
not sure... just guessed... I could be wrong
0
You should never guess in these topics :)

a.  S->AaA

A->AA | aAB | bAa | a |  ε

B->b

b.  $\overline{L}$={$a^nb^m | n>m>1$}  $\cup$  {$a^nb^m | m>n>1$} $\cup$ {(a+b)*b(a+b)*a(a+b)*}

Grammar for $\overline{L}$:

A->aaAb | aaCb

B->aBbb | aCbb

C->aCb | ε

D->aD | bD | a | b | ε

edited by
0
Can it generate $aab?$
0

@Arjun sir

I've changed it

pls check is it correct now?

0
For b part, you havent given bounds for $m,n$. Also $bab$ won't be generated rt?
0

thanks for pointing out that @Arjun sir

corrected :P

## Related questions

1
21 views
Show that the string the girl touches the boy with the flower has two different leftmost derivations in grammar $G_2$ on $\text{page 103.}$ Describe in English the two different meanings of this sentence.
Give context-free grammars that generate the following languages$.$ In all parts, the alphabet $\sum$ is $\{0,1\}.$ $\text{{w| w contains at least three 1’s}}$ $\text{{w| w starts and ends with the same symbol}}$ $\text{{w| the length of w is odd}}$ $\text{{w| the length of w is odd and its middle symbol is a 0}}$ $\text{{$w|w=w^{R},$that is, w is a palindrome}}$ $\text{The empty set}.$
Let $\Sigma = \{a,b\}.$ Give a $CFG$ generating the language of strings with twice as many $a’s$ as $b’s.$ Prove that your grammar is correct$.$
Let $CFG$ $G$ be the following grammar$.$ $S\rightarrow aSb \mid bY \mid Y a$ $Y\rightarrow bY \mid aY \mid \epsilon$ Give a simple description of $L(G)$ in English$.$ Use that description to give a $CFG$ for $\overline{L(G)},$ the complement of $L(G).$