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.1k views answer comment Share Follow See all 13 Comments See all 13 13 Comments reply rballiwal commented Dec 14, 2018 reply Follow Share i have a hint for you , the above language is CNF so please see how to convert a CNF to GNF 0 votes 0 votes Menon Karthik commented Dec 14, 2018 reply Follow Share yes, I found that it is in CNF but when we evaluate it to GNF, we get a case of left recursion, which I am having troubles with. Also, for CNF the condition is A-> XY and X->a however, while converting a CFG to CNF we move the start symbol like S'->S if start symbol appears on the RHS. Here in the given question start symbol 'S' appears on the RHS. Is it still in CNF ? 0 votes 0 votes rballiwal commented Dec 14, 2018 reply Follow Share absolutely the above language is in CNF and having S in rhs does not affect the configuration : a languge is cnf if it has production of following form A ->BC (double variable -exactly) A->a (single terminal -exactly) now the moving of s->s' is never required as no left recursion can be generated in the conversion of CFG to CNF , 0 votes 0 votes Menon Karthik commented Dec 14, 2018 reply Follow Share So while converting the above CFG to GNF, steps would be - Step 1- Mark S as A1, A as A2, B as A3. Step 2- A1 -> A2A3 A2 -> A3A1|b A3 -> A1A2|a Step 3- A 1-> bA3 | A3A1A3 (sub A2-> A3A1|b) now, A3-> A1A2|a substituting the above back in A1, we get, A1 -> bA3 | aA1A1 | A1A2A1A3 which is a case of left recursion ? 0 votes 0 votes rballiwal commented Dec 14, 2018 reply Follow Share i think you are finding hard to know when does the left recursion occur: let me help you with that and also why only left recursion generated in conversion of CFG to GNF. i will take an example but if you still need any help i would answer it so conversion of language like S-> Sa / b to GNF is not possible by any substitution of produciton like say you substituted the value the value of S->b to S->Sa then it comes out like S->ba/a and thats it but if you look at original producitons then you see that it generates infinite numeber of strings ( specifically bb*a ). so for that reason we used a simple method as follows say S-> b / bB B-> a/aB ( which generates a+ ) now look we have eleminated left recursion by doing this simple method 0 votes 0 votes Menon Karthik commented Dec 14, 2018 reply Follow Share I still am not sure of how to do this. But the technique which I use to solve left recursion is as follows A4 -> b|bA3|A4A3A1 then, Z -> A3A1 | A3A1Z then A4 -> bZ|bA3Z However, I am still confused on how to go about solving the main question. 0 votes 0 votes rballiwal commented Dec 14, 2018 reply Follow Share here is the link look by yourself https://www.geeksforgeeks.org/converting-context-free-grammar-greibach-normal-form/ 0 votes 0 votes Menon Karthik commented Dec 14, 2018 reply Follow Share this is my solution after checking the link, pls tell me if it's correct ( according to the main question) S-> AB A-> BS|b B-> SA|a then S-> AB is not in GNF so substitute A-> BS|b then we get, S-> BSB|bB However, S-> BSB is not in GNF, so substitute B-> SA|a, we get, S-> SASB|aSB|bB here S-> SASB is left recursion so, ( After removal of C-> ͼ) C-> SA|SAC then my production becomes S-> aSBC | bBC | aSB | bB Is this part correct ? Thanks in advance 0 votes 0 votes rballiwal commented Dec 14, 2018 reply Follow Share if you could then can you tell me where did you assume " C " as there is no production of " C " 0 votes 0 votes Menon Karthik commented Dec 14, 2018 reply Follow Share here S-> SASB is left recursion so, ( After removal of C-> ͼ) C-> SA|SAC I have used C to remove left recursion and by (After removal of C-> ͼ) I meant to say that if we go step by step for removing left recursion of S-> SASB, then we would do it like C-> ASBC|ͼ and then remove the null production using its rules. I skipped this part 0 votes 0 votes 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.