5 votes 5 votes S→ AB A→ BS|b B→ SA|a INTO GNF Theory of Computation gnf conjunctive-normal-form theory-of-computation context-free-language + – Menon Karthik asked Dec 14, 2018 Menon Karthik 26.8k views answer comment Share Follow See all 13 Comments See all 13 13 Comments reply Show 10 previous comments rballiwal commented Dec 14, 2018 reply Follow Share ok then its fine , i have not checked the answer but , it seems ok as the method is absolutely ok , 0 votes 0 votes Menon Karthik commented Dec 14, 2018 reply Follow Share Thanks. It would be great if you could cross check since I have end sem tomorrow. Thanks 0 votes 0 votes Gateuser00001 commented Oct 1, 2023 reply Follow Share To convert the given context-free grammar into Greibach Normal Form (GNF), we need to follow a set of rules. GNF is a specific form of a context-free grammar where each production has the form A → aα, where 'a' is a terminal symbol, and α is a possibly empty string of variables (non-terminals). The given grammar is: ``` S → AB A → BS | b B → SA | a ``` Let's convert this grammar into GNF: **Step 1:** Eliminate ε-productions (productions that derive the empty string ε). There are no ε-productions in the given grammar, so no changes are needed for this step. **Step 2:** Eliminate unit productions (productions of the form A → B). In the given grammar, we have unit productions: ``` A → BS B → SA ``` We can replace these unit productions with their respective right-hand sides, recursively if necessary. After this step, we get: ``` A → bS | b B → aS | a ``` **Step 3:** Remove left-recursion. In the given grammar, we have indirect left-recursion through A and B. To remove left-recursion, we'll introduce new non-terminals and rewrite the productions. The modified grammar becomes: ``` S → AB A → bSA' | b A' → bSA' | b B → aSB' | a B' → aSB' | a ``` **Step 4:** Remove productions with more than one non-terminal on the right-hand side. The modified grammar has productions with more than one non-terminal on the right-hand side: ``` A' → bSA' | b B' → aSB' | a ``` We can convert these productions into GNF by introducing new non-terminals. Here's the final GNF: ``` S → AB A → bX | b X → SA' A' → bX | b B → aY | a Y → SB' B' → aY | a ``` Now, every production in this grammar has the form A → aα, where 'a' is a terminal symbol, and α is a possibly empty string of variables (non-terminals), which is the characteristic of Greibach Normal Form (GNF). 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes I have done like this hope you like it Akhand Savage answered May 15, 2019 Akhand Savage comment Share Follow See all 0 reply Please log in or register to add a comment.