# Michael Sipser Edition 3 Exercise 2 Question 20 (Page No. 156)

38 views
Let $A/B = \{w\mid wx\in A$  $\text{for some}$ $x \in B\}.$ Show that if $A$ is context free and $B$ is regular$,$ then $A/B$ is context free$.$

edited

## Related questions

1
36 views
Let $C$ be a context-free language and $R$ be a regular language$.$ Prove that the language $C\cap R$ is context-free. Let $A = \{w\mid w\in \{a, b, c\}^{*}$ $\text{and}$ $w$ $\text{contains equal numbers of}$ $a’s, b’s,$ $\text{and}$ $c’s\}.$ Use $\text{part (a)}$ to show that $A$ is not a CFL$.$
Use the results of $\text{Question 16}$ to give another proof that every regular language is context free$,$ by showing how to convert a regular expression directly to an equivalent context-free grammar$.$
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).$