# L is a context free language over {0, 1}, prove, disprove:

cont...

L is a context free language over {0, 1}, prove, disprove: L1 is a CFL over {a, b}, where L1 is the language of all words from L, that 0 is converted to a and 1 is converted to bba.

Thanks (:

-
Since you are new, I want to give you some advice about the site: To get the best possible answers, you should explain what your thoughts on the problem are so far. That way, people won't tell you things you already know, and they can write answers at an appropriate level; also, people are much more willing to help you if you show that you've tried the problem yourself. – Zev Chonoles Dec 26 '12 at 21:02
Hi, thanks for your response. I'm not sure how to approach it. Do I need to show a grammar in order to prove? How do I disprove? Thanks – user54319 Dec 26 '12 at 21:04

## 1 Answer

HINT: Let $G$ be a context-free grammar for $L$. Let $\mathscr{N}$ be the set of non-terminal symbols of $G$. Then every production $\pi$ of $G$ has the form $N\to w$, where $N\in\mathscr{N}$ and $w\in(\mathscr{N}\cup\{0,1\})^*$. Let $\pi'$ be the production obtained from $\pi$ by changing every $0$ in $w$ to an $a$ and every $1$ in $w$ to $bba$. Let $G\,'$ be the grammar obtained from $G$ by replacing the terminal alphabet $\{0,1\}$ with $\{a,b\}$ and each production $\pi$ of $G$ by $\pi'$. Show that $G\,'$ is a context-free grammar that generates $L_1$.

-