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

If G is a context-free grammar such that it has the productions of the form

$$ X \rightarrow \alpha Y ,X \rightarrow \alpha $$

How can I show that L(G) is a regular language

share|cite|improve this question
Construct a DFA (or an NFA) recognizing it. – Yuval Filmus Sep 21 '12 at 4:44

I’m going to assume that $\alpha$ here represents any string of terminal symbols.

For each production $\pi$ in $G$ and each terminal symbol $\sigma$ in $\pi$ except the first one introduce a new non-terminal symbol $N_{\pi,\sigma}$. If $\pi$ is $X\to\sigma_1\sigma_2\dots\sigma_nY$, replace $\pi$ by the following regular productions:

$$\begin{align*} X&\to\sigma_1N_{\pi,\sigma_2}\\ N_{\pi,\sigma_2}&\to\sigma_2N_{\pi,\sigma_3}\\ &\;\vdots\\ N_{\pi,\sigma_k}&\to\sigma_kN_{\pi,\sigma_{k+1}}\\ &\;\vdots\\ N_{\pi,\sigma_n}&\to\sigma_nY \end{align*}$$

That takes care of the productions of the form $X\to\alpha Y$, and from here you should be able to figure out what you should do to replace the productions of the form $X\to\alpha$. (Of course you’ll still have to prove that the new grammar generates the same language.)

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.