A context-free grammar is said to be in Greibach normal form (GNF) in formal language theory if all production rules’ right-hand sides begin with terminal symbols, optionally followed by some variables.
In this article, we will look more into the GNF according to the GATE Syllabus for (Computer Science Engineering) CSE. We will read ahead to find out more about it.
What is GNF?
The Greibach normal form is referred to as GNF. A context-free grammar (CFG) is in Greibach normal form (GNF) if and only all of its production rules meet one of the criteria listed below:
- A non-terminal that generates a terminal. For instance, X → x.
- A start symbol that generates ε. For instance, S → ε.
- A non-terminal that generates a terminal followed by any number of non-terminals. For instance, S → xXSY.
Example
GA = {S → xXY | xY, X → xX| x, Y → yY | y}
GB = {S → xXY | xY, X → xX | ε, Y → yY | ε}
The production rules of the GA grammar satisfy the rules that are specified for GNF; thus, the GA grammar is in GNF. But the production rule of GB grammar does not satisfy the rules that are specified for GNF as X → ε and Y → ε contain ε (only the start symbols generate ε). Thus, the grammar GB is not present in GNF.
CFG into GNF Conversion Steps
Step 1: Conversion of the grammar into its CNF.
In case the given grammar is not present in CNF, first convert it into CNF.
Step 2: In case the grammar exits the left recursion, eliminate it.
Step 3: If any production rule is not present in GNF, convert the production rule given in the grammar into GNF form.
Example
S → AY | XX
X → x | SX
Y → y
A → x
Answer:
As the given grammar is already in CNF, and no recursion is left, we can skip the first and the second steps and directly go to the third step.
The production rule X → SX is not in GNF. Thus, substitute S → AY | XX in the production rule X → SX as:
S → AY | XX
X → x | AYX | XXX
Y → y
A → x
The production rule S → AY and Y → AYX is not in GNF. Thus, substitute A → x in the production rule S → AY and Y → AYX as:
S → xY | XX
X → x | xYX | XXX
Y → y
A → x
We will now remove left recursion (X → XXX), then get:
S → xY | XX
X → xZ | xYXZ
Z → XXZ | ε
Y → y
A → x
Removal of the null production Z → ε would get:
S → xY | XX
X → xZ | xYXZ | x | xYX
Z → XXZ | XX
Y → y
A → x
The production rule S → XX is not in GNF; thus, substitute X → xZ | xYXZ | x | xYX in production rule S → XX as:
S → xY | xZX | xYXZX | xX | xYXX
X → xZ | xYXZ | x | xYX
Z → XXZ
Z → xZX | xYXZX | xX | xYXX
Y → y
A → x
The production rule C → XXZ is not in GNF, so substitute X → xZ | xYXZ | x | xYX in production rule Z → XXZ as:
S → xY | xZX | xYXZX | xX | xYXX
X → xZ | xYXZ | x | xYX
Z → xZXZ | xYXZXZ | xXZ | xYXXZ
Z → xZX | xYXZX | xX | xYXX
Y → y
A → x
Hence, this is the GNF form for the grammar G.
Keep learning and stay tuned to get the latest updates on the GATE Exam along with Eligibility Criteria, GATE Syllabus for CSE (Computer Science Engineering), GATE 2023, GATE Admit Card, GATE CSE Notes, GATE CSE Question Paper, and more.
