The authors prove that a generalized Greibach normal form (GNF) grammar still generates a context-free language. They expand the left side of GNF-type rules to be any nonempty product of variables (nonterminals), not just a single variable. Then, by means of a factorization and composition depending on left association, they convert the new grammar to a weakly equivalent grammar in GNF.

More specifically, “a grammar is a 4-tuple G = (V,T,S,P), where V and T are finite sets of variables and terminals, respectively, S ∈ V is the start symbol, and P is a finite set of productions [or rules] of the form α → β, with α,β ∈ (V ∪ T)^* and α non-empty.” They use ε to denote the empty string.

A subset of T^* is called a language. We assume the application of rules and definition of the language L(G) generated by G as well known. Unfortunately, the authors never define a language and do not define the language G generates until after the introduction and the statement of the principal result, which uses both “language” and “generated by.” Here is that result:

Theorem 1. Let L be a language without ε. Then L is context-free if and only if L can be generated by a grammar for which every production has the form α→aβ where α ∈ V⁺ and aβ ∈ TV^*.

This becomes a GNF grammar when α is restricted to being a single variable. It should be mentioned that some expositors of GNF allow the ε-production S → ε and others exclude S from occurring in β. These variations are ignored here.

If L is context-free, then a GNF generating it proves if … then. Here is a sketch of the construction of then … if--see the paper for the proof. Given a grammar G = (V,T,S,P) whose every rule has the form α → aβ, where α ∈ V⁺, a ∈ T, and β ∈ V^*, construct a new grammar = (, T, V_S,ε, )--obviously in GNF, but not obviously equivalent to G. Take N_G ⊆ V⁺ to be all left sides of rules in P, and take M_G ⊆ V^* to be all proper prefixes of strings in N_G. Then the new variables are = {V_α,β : α ∈ N_G, β ∈ M_G}, and the new rules = ₁ ∪ ₂ come in two kinds, the second generalizing the first:

₁ = {V_α,β → a : α → aβ ∈ P},

₂ = V_α,β → aV_β1,τ1 V_τ1β2,τ2 … V_τk-1βk,τk : k ≥ 1

& α → aβ₁ … β_kβ_k+1 ∈ P

& β_i ≠ ε (i = 1,…,k)

& β = τ_kβ_k+1}.

The conditions for are simplified over the original, because to mention V_γ,δ is to force γ∈N_G and δ∈M_G. The definition of is subtle and brilliant. Note how the final string (suffix of a prefix) is stored as state in the second subscript of the variable.

On page 95, for the case when δ is a proper prefix of β₁, it could be noted that δ may be empty. In the discussion of this case, “and since → aδ and” should read “and since →aδ ∈ P and”.

For the case δ = β₁…β_k, it could be noted that k′ = 1 and β′₁ = α.

For the case δ ≠ β₁…β_k, observe that φ may be empty, although ψ is not. The index limits for β′_i,τ′_i must be restated as:

β′_i = β_j+i-1 for i = 3,…,k-j+1,

τ′_i = τ_j+i-1 for i = 2,…,k-j.

(β_k+1,τ_k do not exist; when j = k-1, there is no β′₃ or τ′₂.) Taking k′ = k-j+1, we have α=β′₁…β′_k′.

In the last line on page 95, “Since → aβ₁…β_jφ, by” should read “Since → aβ₁…βjφ ∈ P, by”. Note that V_{β′1,τ′1} = V_,τjφ.

Then, at the top of page 96, the third line:

V_{β’1,τ’1}V_{τ’1β’2,τ’2}…V_{τ’k-1β’k,ε}

aV_β1,τ1…V_τj-iβj,τjV_{τj φψ,τj+1}…V_{τ’k-1β’k,ε}

w

needs correction to:

V_{β’1,τ’1}V_{τ’1β’2,τ’2}…V_{τ’k’-1β’k’,ε}

= V_{,τj φ}V_{τ’1β’2,τ’2}…V_{τ’k-jβ’k-j+1,ε}

= V_{,τj φ}V_{τj φ ψ,τj+1}…V_τk-1βk,ε

aV_β1,τ1…V_τj-iβj,τjV_{τj φψ,τj+1}…V_τk-1βk,ε

a = w.

The authors write of revising the basic definitions. The only obvious thing is the reversal of the order of P,S in the definition of a grammar, but on page 94 they revert to the standard (V,T,P,S).

Some steps are left out. For V_S,ε to belong to requires that S ∈ N_G, which must be so as long as L(G) is nonempty, that is, nontrivial. There are several places where it is asserted that γ → w belongs to P, which requires w ∈ T; although unstated, this follows from the hypotheses. In addition, citing w, ∈ T^* always entails w, being nonempty.

It might be mentioned that whether a grammar has the required form is obviously a computable question. The conversion to GNF is also computable. GNF covers broader problems of computably finding such a grammar for a CFL given by some other method.

The authors could have spoken to the importance and usefulness of their elegant result. This and the issues mentioned above should have been handled by the referees.