The Gateway to Computer Science Excellence
+2 votes

A→ BS|b

B→ SA|a


in Theory of Computation by (41 points) | 660 views
i have a hint for you , the above language is CNF so please see how to convert a CNF to GNF
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 ?
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 ,
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 ?
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
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


Z -> A3A1 | A3A1Z


A4 -> bZ|bA3Z

However, I am still confused on how to go about solving the main question.
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


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,


here S-> SASB is left recursion so, ( After removal of C->  ͼ)


then my production becomes

S-> aSBC | bBC | aSB | bB

Is this part correct ? Thanks in advance
if you could then can you tell me where did you assume " C " as there is no production of " C "
here S-> SASB is left recursion so, ( After removal of C->  ͼ)


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
ok then its fine , i have not checked the answer but , it seems ok as the method is absolutely ok ,
Thanks. It would be great if you could cross check since I have end sem tomorrow.


1 Answer

0 votes

I have done like this hope you like it

This is my solution

by (11 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,650 questions
56,192 answers
94,852 users