i have a hint for you , the above language is CNF so please see how to convert a CNF to GNF

The Gateway to Computer Science Excellence

+2 votes

0

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 ?

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

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 ,

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

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 ?

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

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

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

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.

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

here is the link look by yourself https://www.geeksforgeeks.org/converting-context-free-grammar-greibach-normal-form/

0

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

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

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.6k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,650 questions

56,192 answers

193,987 comments

94,852 users