Confusion related to context free grammar

Question

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

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