2
$\begingroup$

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??

$\endgroup$
  • $\begingroup$ Welcome! Please remember to upvote answers you like, and accept the one that helped you mist. "Thank you" comments are well-intended but considered superfluous on Stack Exchange. $\endgroup$ – Raphael Feb 11 '15 at 21:45
6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

A derivation is a "proof" that a certain word is generated by a certain grammar. The grammar itself doesn't have a left-most derivation. Each word in the grammar has left-most derivations, possibly more than one if the grammar is ambiguous.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.