Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

2 Answers

up vote 7 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

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.