[Solved]: Can there be two different left most derevations for a grammar?

Problem Detail: 

Suppose there is a CFG with the rules

S--> Aa A--> Bb B--> A B--> Epsilon 

To my best understanding the left most derivation would go like this..

 S==> Aa ==>  Bba ==> Aba ==> Bbba ==> bba 

or

 S==> Aa ==>  Bba ==> Aba ==> Bbba ==> Abba ==> Bbbba ==> bbba 

or

 S==> Aa ==> Bba ==> ba 

Of these which is the true left most derivation of the language? If it is true that all of them are valid left most derivations,why is it that many text book talk about left most derivations of a language rather than a final string??

Asked By : user2277550

Answered By : babou

A leftmost derivation of a string in the language defined by a grammar $G$ characterizes a parse-tree for that string. It is a way of describing the parse tree, which is unique for each parse tree.

But to answer the specifics of your question, there is no lefmost derivation of a language, only of the strings of a language. Furthermore, since a leftmost derivation is a sequence of grammar rules applications to produce the string, a leftmost derivation is necessarily defined with respect to a specific grammar. Indeed, the language does not really matter, only the grammar and a string derived with that grammar.

If a string has only a single derivation for a grammar $G$, it is said unambiguous for that grammar. When it has several, it is said ambiguous for that grammar. When it has none, it does not belong to the language generated by the grammar.

A grammar is ambiguous if it generate at least one ambiguous string. It is unambiguous if every string in its language is unambiguous.

The grammar in your question is unambiguous. Each of the derivations you give is a leftmost derivation, but each for a different string in the language of the grammar.

Actually, this grammar is so simple that it has only leftmost derivations, because there is at most one non-terminal in each rule right-hand side. But a grammar can have only leftmost derivations and be ambiguous.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/38258

 Ask a Question

 Download Related Notes/Documents