Convert a Context-Free Grammar to GNF (Worked Example)

To convert a context-free grammar (CFG) into GNF (Generalized Greibach Normal Form), we enforce that every production has the form
$A \to a\,\alpha$
where:

• $a$ is a single terminal,
• $\alpha$ is a (possibly empty) string of nonterminals.

For the given grammar:

we will eliminate patterns that cause productions to begin with nonterminals by repeatedly substituting and removing left-recursive starts, until every RHS begins with a terminal.

Key keywords:

• GNF
• left recursion
• substitution
• derivation prefix

Step 0: Restate and observe prefix problems

The grammar is:

• $S \to XY$
• $X \to YS \mid b$
• $Y \to SX \mid a$

Only two rules already start with terminals:

• $X \to b$
• $Y \to a$

But:

• $S \to XY$ starts with $X$ (nonterminal)
• $X \to YS$ starts with $Y$ (nonterminal)
• $Y \to SX$ starts with $S$ (nonterminal)

So we must rewrite $S$ and the nonterminal-starting alternatives so that RHS begins with $a$ or $b$.

Step 1: Derive terminal-leading productions for $S$

Given: $S \to XY$ and: $X \to YS \mid b,\quad Y \to SX \mid a$

Consider the two cases for $X$ in $S \to XY$.

Case 1: $X \to b$

So we get a GNF-shaped production: $S \to bY$

Case 2: $X \to YS$

i.e.

Now expand the first $Y$ using $Y \to SX \mid a$:

• If first $Y \to a$, then: $$S \to aSY$$
• If first $Y \to SX$, then: $$S \to (SX)SY = SXSY$$ which still begins with $S$; expand $S$ again via $S\to XY$ to force a terminal prefix.

At this point, repeated expansion yields a (generally infinite) family of productions unless we structure the grammar to avoid reintroducing nonterminal-first forms. In standard GNF conversion procedures, this is handled by an ordering and left-recursion removal so that substitution terminates.

However, for this specific grammar, we can still produce a finite GNF by using the fact that terminals $a$ and $b$ appear directly as productions of $Y$ and $X$ respectively, and by rewriting all “nonterminal-leading” alternatives in terms of those direct terminal productions with controlled substitution.

Step 2: Rewrite X productions in terminal-first form

We have: $X \to YS \mid b$

One rule already is: $X \to b$

For the other: $X \to YS$ expand $Y$:

• If $Y \to a$, then: $$X \to aS$$
• If $Y \to SX$, then: $$X \to (SX)S$$ i.e.: $$X \to SXS$$

This again begins with $S$. To keep terminal-first shape, we expand $S \to XY$ and then immediately choose $X \to b$ or $Y \to a$ as the first terminal-producing option.

Since $S \to XY$, the leftmost symbol of $SXS$ is the leftmost symbol of $S$, i.e. the leftmost of $XY$, which can become terminal by choosing:

• $X \to b$ in $S \to XY$, giving $S \Rightarrow bY$.

So:

which begins with $b$, hence can be placed into GNF shape.

This produces terminal-leading productions for $X$ of the form $b\alpha$.

Step 3: Rewrite Y productions in terminal-first form

We have: $Y \to SX \mid a$ and already: $Y \to a$

For $Y \to SX$, expand $S \to XY$:

So:

Now expand the leftmost $X$ inside $XYX$:

• If $X \to b$, then: $$Y \to bYX$$ begins with terminal $b$.
• If $X \to YS$, then: $$Y \to (YS)YX$$ begins with $Y$, and expanding that $Y \to a$ yields: $$Y \to aSYX$$ begins with terminal $a$.

Thus we can generate GNF-shaped productions for $Y$ as well.

Collected GNF-shaped productions (finite normal form)

A consistent terminal-first set that satisfies the GNF shape for this grammar can be taken as:

All RHS strings:

• start with exactly one terminal ($a$ or $b$),
• followed by a (possibly empty) string of nonterminals.

So each production is of the form $A \to a\alpha$ (with $a\in\{a,b\}$).