Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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 (:

share|cite|improve this question
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

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.