Скачать или смотреть Greibach Normal Form (GNF) || Lesson 68 || Finite Automata || Learning Monkey ||

Greibach Normal Form (GNF)
In this class, We discuss Greibach Normal Form (GNF).
The reader should have prior knowledge of Chomsky's normal form. Click Here.
Greibach Normal Form: A given CFG is greibach normal form. if the productions are of the form
A – aα where α may be any number of non-terminals.
A – a where a is any terminal symbol
To convert the CFG into GNF, we follow the steps.
Using GNF, we can make the decision easily. because the first symbol is a terminal.
Example:
S – AB
A – BS | b
B – SA | a
First: convert CFG to CNF.
The CFG is in CNF., so there is no need for the first step in our example.
Second Step:
Give non-terminals a separate naming.
S is assigned A1
A is assigned A2
B is assigned A3
Substitute the naming in the CFG.
A1 – A2A3
A2 – A3A1 | b
A3 – A1A2 | a
Check productions of the form Ai – Aj where i = j
The production A3 – A1A2 | a is not in the given form.
In the production A3 – A1A2 | a i = 3, and j = 1. where i j.
Using substitution, we need to bring the production to satisfy the condition i = j..
Substitute A1 in the production A3.
A3 – A2A3A2 | a
we substitute the production A2 in the production A3.
A3 – A3A1A3A2 | a | bA3A2
The above production is in left recursion.
Third Step:
Eliminate Left recursion.
Here α is A1A3A2, and β is a | bA3A2
The below grammar shows CFG after eliminating left recursion.
A3 – aZ3 | bA3A2Z3
Z3 – A1A3A2Z3 | ε
Now the production A3 is in GNF.
Using substitution brings back all the productions to GNF.
Substitute A3 to the production A2.
A2 – b | aZ3A1 | bA3A2Z3A1 | aA1 | bA3A2A1
Now, we substitute A2 to the production A1. The production A2 is in GNF.
A1 – bA3 | aZ3A1A3 | bA3A2Z3A1A3 | aA1A3 | bA3A2A1A3
Now we can substitute A1 in production Z3. the production A1 is in GNF.
The reader can continue substituting A1 in Z3.
Finally, We got all the productions in GNF.


Link for playlists:
   / @wisdomerscse  


Link for our website: https://learningmonkey.in

Follow us on Facebook @   / learningmonkey  

Follow us on Instagram @   / learningmonkey1  

Follow us on Twitter @   / _learningmonkey  

Mail us @ [email protected]