2
$\begingroup$

Given a context-free grammar $G$, let $\longrightarrow_G$ be the (one-step) rightmost derivation relation, and $\longrightarrow^*_G$ its reflexive and transitive closure.

Let $S$ be the start symbol of $G$, $\mathbf{N}$ the set of non-terminal symbols and $\mathbf{T}$ the set of terminal symbols. For each rewriting rule $A\rightarrow \alpha$ ($A\in\mathbf{N}, \alpha\in (\mathbf{N}\cup\mathbf{T})^*$), define the sets $\operatorname{Left}_G(A)$ and $L_{G,A\rightarrow\alpha}$ by:

$$\operatorname{Left}_G(A)=\{\beta\mid \exists w\in \mathbf{T}^*: S\longrightarrow_G^* \beta A w\}\qquad L_{G,A\rightarrow\alpha} = \{\beta\alpha\mid\beta\in \operatorname{left}_G(A)\}$$

I want to show, that for every context-free grammar $G$ and every rule $A\rightarrow \alpha$ of $G$, $L_{G,A\rightarrow\alpha}$ is a regular language over the alphabet $\mathbf{N}\cup\mathbf{T}$.

I can use the fact that a language generated by a left-linear context-free grammar is regular. Here a context-free grammar $G$ is said to be left-linear if $\alpha\in \mathbf{T}^*\cup (\mathbf{N}\mathbf{T})^*$ holds for every rewriting rule $A\rightarrow \alpha$ of $G$.


I've tried from both sides, the first thought was to show if I can get the language by getting the grammar from $G$ to $Left_G$, then maybe I can get some properties that $\beta$ may have, that lead to the fact that it's close to left-linear grammar, but I just can't, after thinking for a whole afternoon.
Then I thought maybe I can start from the goal language $\beta \alpha$, that I cut them into rewriting relation that is left-lineared, like we have $S\rightarrow_G^*\beta\alpha$, if we want to cut a left-linear grammar out of it, we need $S\rightarrow_G^*A\omega$, which $\omega \in T^*$ and we have$\alpha \rightarrow \alpha\omega$ or something, but as the $\alpha \in (N\bigcup T)^*$, so I don't even know if I can cut the language that way.

I'll appreciate if I can have some hint, like where may I begin to consider, or is there any properties about the relation I just missed or don't know?

$\endgroup$
  • $\begingroup$ books.google.com.pe/… $\endgroup$ – rici Jan 16 '18 at 16:12
  • $\begingroup$ Another explanation: cs.williams.edu/~tom/courses/434/outlines/lect14_2.html (See step 9) $\endgroup$ – rici Jan 16 '18 at 17:55
  • $\begingroup$ Thank you for all your comments, that helps me a lot. Here's what I think now. As $\alpha$ is a handle of the grammar G, so we can cut the handle step by step, and because it's the (one-step) rightmost derivation relation, we can right every reduction into a left-linear production, so this language is linear. Am I right? @rici $\endgroup$ – JOHNKYON Jan 17 '18 at 6:18
  • $\begingroup$ A note on terminology: left-linear is regular, which is more restrictive than linear - see en.m.wikipedia.org/wiki/Regular_grammar $\endgroup$ – reinierpost Jan 17 '18 at 6:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.