Here is a passage from Kozen's Automata and Computability (pages 145-146) that I'm confused about:

Now we show how to convert an arbitrary grammar to an equivalent one (except possibly for $ \epsilon $) in Greibach normal form.

We start with a grammar $ G = (N, \sum, P, S) $ in Chomsky normal form. This assumption is mainly for ease of presentation; we could easily modify the construction to apply more generally. The construction as given here produces a Greibach grammar with at most two nonterminals on the right hand side (cf. [60, Exercise 4.16, p. 104]).

For $ \alpha, \beta \in (N \cup \sum)^* $, write $$ \alpha \longrightarrow^{L}_{G} \beta $$ if $\beta$ can be derived from $\alpha$ be a sequence of steps in which productions are applied only to the leftmost symbol in the sentential form (wwhich must therefore be a nonterminal). For $ A \in N $ and $ a \in \sum $, define $$ R_{A, \alpha} = \{\beta \in N^* \mid A \longrightarrow^L_G \alpha\beta \} $$ For example in the CNF grammar (21.1)*, we would have $$ C \longrightarrow^L_G SB \longrightarrow^L_G SSB \longrightarrow^L_G SSSB \longrightarrow^L_G ACSSB \longrightarrow^L_G [CSSB, $$ so $CSSB \in R_{C, [}.$

The set $ R_{A, \alpha} $ is a regular set over the alphabet $N$, because the grammar with nonterminals $\{A' \mid A \in N \}$, terminals $N$, start symbol $S'$, and productions $$ \{A' \longrightarrow B'C \mid A \longrightarrow BC \in P \} \cup \{A' \longrightarrow \epsilon \mid A \longrightarrow a \in P \} $$ is a strongly left-linear grammar for it. This may seem slightly bizarre, since the terminals of this grammar are the nonterminals $N$ of $G$, but a moment's thought will convince you that it makes perfect sense.

Since $R_{A, \alpha}$ is regular, by Homework 5, Exercise 1 it also has a strongly right linear grammar $G_{A, \alpha}$; that is, one in which all productions are of the form $X \longrightarrow BY$ or $X \longrightarrow \epsilon$, where $X,Y$ are nonterminals of $G_{A, \alpha}$ and $B \in N$.

*CFN grammar (21.1) is $$ S \longrightarrow AB \mid AC \mid SS, \; C \longrightarrow SB, \; A \longrightarrow [, \; B \longrightarrow ] $$

I am confused starting at the paragraph "The set $ R_{A, \alpha} $ is a regular set over the alphabet..." Breaking this down phrase by phrase:

1.)The set $ R_{A, \alpha} $ is a regular set over the alphabet $ N $

Okay, so $ R_{A, \alpha} $ is some subset of $N^*$ and can be expressed as the language of a regular expression.

2.)because the grammar with nonterminals $ \{ A' \longrightarrow \mid A \in N \} $, terminals $N$, start symbol $ S' $, and productions $ \{A' \longrightarrow B'C \mid A \longrightarrow BC \in P \} \cup \{A' \longrightarrow \epsilon \mid A \longrightarrow a \in P \} $ is a strongly left-linear grammar for it.

Okay, so consider a newly formed grammar whose nonterminals are just the nonterminals of the old grammar but with an apostrophe, whose terminals are the old nonterminals, whose start symbol is $ S^{'} $, and whose productions are [blah] is a "strongly left linear grammar for it". I know what strongly left linear means and it's obvious that these productions are left linear. But it's a little unclear to me what they mean by "grammar for it". Do they mean that the language of this new grammar is equal to $ R_{A, \alpha} $? If so, why?


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.