# Converting Chomsky Normal Forms to Greibach Normal Form

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?