1
$\begingroup$

Given the context-free grammar

\begin{align*} & S \rightarrow AA \\ & A \rightarrow xA \\ & A \rightarrow B \\ & B \rightarrow yB \\ & B \rightarrow \lambda \end{align*} What is the meaning of $\lambda$? $\lambda$ itself means the empty string and will match anything without consuming it, but in terms of the productions, how do you know which one to use? Do you use the last $B$ production only if $B \mapsto yB$ cannot be used? Or can both be used interchangably?

For example, parsing the string $xyy$ could give two different results: two different parse trees

Is there a formal way to prefer one of the two possible options? Which one is the "default"?

$\endgroup$
  • 1
    $\begingroup$ A context-free grammar defines a language. A word is in the language if it can be produced using the productions of the grammar. You are free to use whichever productions you want. It is meaningless to ask "how do you know which one to use". The language is formed by trying all possibilities. $\endgroup$ – Yuval Filmus Feb 20 '17 at 19:50
2
$\begingroup$

I think you have understood this backwards. The CFG defines the language. All strings that can be derived by using the rules defined in the CFG are present in the language. The empty string itself is a terminal variable. You would substitute it in the string that you're deriving and is just empty.

What you are arriving at with the parse trees is called ambiguity of the grammar that you have defined. When the same string can be derived in more than one leftmost derivation, then the grammar is ambiguous. You could use two different substitutions and still arrive at the same string. So, yes, you could use either derivation, but the string itself does not change.

I would say the formal way to derive your string in exactly one particular way is to use a grammar without ambiguity.

$\endgroup$
  • $\begingroup$ Is the ambiguity equivalent to saying that the grammar is non-deterministic? $\endgroup$ – Soupy Feb 24 '17 at 18:35

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.