[Solved]: What if a formal grammar cannot be terminated?

Problem Detail: 

I'm currently in a class on Computability and we just finished looking at formal grammars before moving onto finite automata. We were given an several examples of a formal grammar, and one stuck out in particular:

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.

When you are given a grammar $G$, then the language it produces, $L(G)$, is all the (finite) words it can generate. All the other "derivations" that don't yield any legal word, can be ignored.

For instance, for the grammar $G_1$:

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