retagged by
1,133 views

2 Answers

2 votes
2 votes
We know that for any language (context free language) , we can have more than one grammar and many grammar can produce same language. For eg: for language L, we might have more than one grammar (let say) G1 and G2.

Both grammar G1 and G2 might represent the same language L but tha way in which we represent Grammar, it is going to create a lot of impact when it comes to derivations in the sense if we represent the grammar in some form that is going to be more useful in order to do the derivations compare to the other Normal forms.

We also know that when the Grammar has epsilon and unit production then that grammar is not suitable for membership algorithm. Similarly every representation of grammar has some advantages:

Context free Grammar has classified in two parts

Advantages of CNF: 1) length of each production is restricted

                               2) Number of steps to derive a string of length  ' n ' = 2 *n -1

                               3) It is easy to apply membership algorithm

Advantages of GNF: `1) Number of steps to derive a string of length ' n  ' = n
1 votes
1 votes
For creating a membership algorithm. So the main question we wanted to answer was -

Does a given Grammer produce the given string?

So we thought we can actually solve this by producing all strings with size 0, then size 1, then size 2. Till we reach a length of our given string. Like if I am given ABC. I will produce strings with the length of size 0,1,2,3 not more than that.

The problem was -

Because of null even a string of length 50 can be reduced to a length of 3, So we needed to check all possible combination which is exponential in time, Means we are writing a procedure, not an algorithm.
And because of unit productions, we were not sure whether we were doing some useful work or not. Like converting A to B , B to C, C to D. We are actually taking a lot of extra steps. so we needed an algorithm which can do that.
So in order to work on the earlier concept, we need to remove all the abnormality and restrict our grammar to produce steps that increase the length of the string in every step. CNF does that. and GNF is used for the conversion of CNF to PDA.

Related questions

2 votes
2 votes
1 answer
1
hustlerrr asked Nov 17, 2021
4,519 views
Convert the following grammar into Greibach Normal Form.E- E + T | TT- T*F | FF->(E) | a I am unable to process this type of grammer into GNF, Can someone please provide ...
0 votes
0 votes
0 answers
2
2 votes
2 votes
1 answer
4