Convert a Context-Free Grammar to GNF Worked Example | AI Research

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

Verified Sources

Sep 12, 2026

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:

S \to XY

X \to YS \mid b

Y \to SX \mid a

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

Greibach Normal Form (GNF) overview + conversion steps

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$ .

GNF conversion roadmap for this grammar

Choose terminal-start strategy

Ensure all productions on RHS begin with terminal by expanding nonterminal prefixes."

Resolve S-started productions

Expand $S \to XY$ until the first symbol is $a$ or $b$ ."

Resolve X- and Y-started alternatives

Rewrite $X \to YS$ and $Y \to SX$ so they begin with $a$ or $b$ ."

Finalize in A→aα shape

Collect and simplify into GNF-ready productions."

Convert the grammar to GNF by prefix elimination (worked derivation)

1
Step 1
We want every production $A \to a\alpha$ where $a \in \{a,b\}$ and $\alpha$ is a string of nonterminals (possibly empty).
2
Step 2
Start with $S \to XY$ . Substitute $X \to YS \mid b$ and $Y \to SX \mid a$ to expose terminal prefixes.
3
Step 3
From $S \to XY$ , consider $X$ alternatives: if $X \to b$ then $S \to bY$ . If $X \to YS$ then $S \to (YS)Y$ . Now ensure the leftmost symbol is a terminal by expanding the first symbol of $Y$ .
4
Step 4
For $X \to YS$ , expand $Y \to a \mid SX$ . If $Y \to a$ then $X \to aS$ . If $Y \to SX$ then $X \to (SX)S$ and we must re-expand the leftmost $S$ .
5
Step 5
For $Y \to SX$ , expand $S \to XY$ , then $X$ can yield $b$ or $YS$ . This creates terminal-leading possibilities; keep substituting until the prefix is terminal.
6
Step 6
After completing substitutions, every RHS can be written as $a$ or $b$ followed by a string of nonterminals. Remove duplicates and keep RHS in the required terminal-first structure.

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$

S \Rightarrow bY

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

Case 2: $X \to YS$

S \Rightarrow (YS)Y

i.e.

S \to YSY

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.

type="tip" title="Strategy that works here" content="Because $X$ can produce $b$ immediately and $Y$ can produce $a$ immediately, we aim to rewrite any RHS so the leftmost symbol is forced to choose $X→b$ or $Y→a$ at the earliest possible step. This avoids needing deeper expansions than necessary."

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:

SXS \Rightarrow (bY)XS = bYX S

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

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

type="warning" title="GNF conversions are sensitive to termination" content="Naively substituting $S→XY$ into nonterminal-leading RHS can create longer strings that still begin with nonterminals, potentially requiring left-recursion elimination / ordering. A correct algorithm ensures a terminating finite set of GNF productions."

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$ :

Y \to (XY)X

So:

Y \to XYX

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:

\begin{aligned} S &\to bY \mid aSY\\ X &\to b \mid aS \mid bYSX\\ Y &\to a \mid bYX \mid aSYX \end{aligned}

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\}$ ).

GNF verification and correctness criteria

Knowledge Check

Question 1 of 4

Q1Single choice

In GNF, what is the required form of each production?

A → aα where a is a terminal and α is a string of nonterminals

A → α where α can start with either terminal or nonterminal

A → aA | ε only

S → aSb | b only

Explore Related Topics

Ambiguity in the Grammar $S \rightarrow ABA,\; A \rightarrow aA \mid \epsilon,\; B \rightarrow bB \mid \epsilon$

The grammar (S\rightarrow ABA,;A\rightarrow aA\mid\epsilon,;B\rightarrow bB\mid\epsilon) is ambiguous because the two (A) nonterminals can distribute the same (a)-string in multiple ways, especially when (B) derives (\epsilon).

It generates the language (L(S)={a^i b^j a^k\mid i,j,k\ge0}=a^*b^a^).
The shortest string (a) has two distinct left‑most derivations (or parse trees), proving ambiguity.
Every string (a^n) with (n\ge1) can be split between the two (A) symbols in (n+1) ways, yielding multiple parse trees.
The ambiguity stems from both (A) producing (a^*) and (B) being able to vanish via (\epsilon).
An equivalent unambiguous grammar can be constructed, showing the ambiguity is a property of this grammar, not necessarily of the language.

Type 2 Grammar (Context-Free Grammar): A Short Note with Formal Meaning and Examples

Constructing an NPDA for a Given CFG

Browse all research articles