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