0
$\begingroup$

Let $L$ be a context-free language on the alphabet $\Sigma$.

I need to show that for each $a \in \Sigma$ the language $L_a = \{ x \in \Sigma^* \; | \; a.x \in L\}$ is context-free as well.

I wanted to prove it by generating a context-free grammar for $L_a$ by the generation of a new nonterminal for each existing one, to check if an 'a' has been read, but this doesn't work as what I need are all words from $L$ with a leading 'a'.

Could you please help me to find a solution?

Thanks in advance!

2 Answers 2

7

Let $G$ be a context-free grammar the produces $L$. You can assume that $G$ is in Chomsky normal form, i.e. all productions are of the form $X \to YZ$ or $X\to c$ or $S \to \varepsilon$ (in this case $S$ must not appear on the right side of any production). In order to get a context-free grammar for $L_a$ you have to modify $G$ in such a way that it produces the words in $L$ that start with an $a$ but produces them without it. You can achieve this by adding for every non-terminal $X$ of $G$ a new non-terminal $\tilde X$ together with the production rule $\tilde X\to \tilde Y Z$ whenever $X\to YZ$ is a production in $G$. This way the left-most symbol in the intermediate steps of a production is always one of the added non-terminals $\tilde X$. Furthermore, for every rule $X\to a$ add the new rule $\tilde X \to \varepsilon$. This way, if $G$ would produce an $a$ at the first position this $a$ is now deleted. Finally, declare $\tilde S$ as the new start symbol. This should result in a context-free grammar that produces $L_a$.

0

Hint:

Another solution can be reached via automata approach. Any context-free language can be recognized some push-down automate and any such automate can be put into already-read-letter-a state prior to reading any input (that is you can create a new automate using the old one with desired properties).