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.

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|improve this question
    
Construct a DFA (or an NFA) recognizing it. –  Yuval Filmus Sep 21 '12 at 4:44

1 Answer 1

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|improve this answer

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.