V: { S, A, B, C } T: { a, b, c } P: { S -> aA | λ | ASA AA -> aA | a }
My professor described the result as “any number of as”. This makes sense if you never use the first S or AA rule; you can simply replace S with ASA as many times as you like, then replace each S with λ (getting some even-length string of As); you can then replace all AAs with as. But what if I picked the first rule? So, I start with S, then replace S with aA. I now have a string that contains neither S, nor AA, so the final terminal string should be aA. (This could also be done with S -> ASA -> AA -> aA.) Is this allowed? If so, what is the result called? Since it still contains a variable, is this just a rejected/invalid result? NB: I did ask my professor about this. He explicitly said to “ignore the first rules of each ‘S’ and ‘AA'”, and could not give me any further explanation on why to do this.
Asked By : Eric
Answered By : Ran G.
S -> SS | Sa | aS
the language that the grammar produces is $L(G_1)=emptyset$, as no derivation ever terminates.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/3542
