# 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?