1,206 views
1 votes
1 votes
Which of the following grammars are equivalent?S is non terminal ,e is epsilon,a is terminal

1. S-> aS |e

2. S-> aS | a |e

3. S-> aaS |e

1 Answer

1 votes
1 votes

In the given grammars 1st and 2nd grammar are equivalent

1-This grammar can generate following strings 

{ϵ,a,aa,aaa,....}

2-This grammar  generates similar string as 1st one

{ ϵ,a,aa,aaa,....}

3-Difference with this grammar is it can't generate single a and can only generate string with even number of a's                                                                   

Related questions

1 votes
1 votes
0 answers
2
smriti bhati asked Jan 26, 2018
297 views
What is the correct way to solve questions of this kind where equations like these are given and you are asked to determine what languages do the variables X1 X2 X3.. rep...
7 votes
7 votes
2 answers
3
pC asked Jul 23, 2016
6,451 views
How to convert a Regular Expression to Left Linear Grammar ?Eg : (0+1)*00(0+1)*
2 votes
2 votes
4 answers
4
vkm07 asked Jul 31, 2016
1,600 views
Which of the following is the most general phase-structured grammar?(a) regular (b) context-free(c) context-sensitive (d) none of the above