Greibach Normal Form (GNF) || Lesson 68 || Finite Automata || Learning Monkey || скачать в хорошем качестве

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 @ learningmonkey01@gmail.com