1
$\begingroup$

Prove that the following grammar is unambiguous:

$$X \to aX | Y$$

$$Y \to Yab | b$$

I know that I must prove that the strings produced by this grammar have only one parse tree, but how can I do this?

$\endgroup$
4
$\begingroup$

First, figure out what the language is.

Then, try to do a few examples of productions in the grammar. What do you notice about the derivation trees and sequences? How would this help you to prove this grammar is unambiguous?

Hint: At each step in the process of deriving a word, what are the possible derivation rules you can use? How would each of them affect the resulting word?

$\endgroup$
4
  • $\begingroup$ I don't understand. How finding language can help me for proving this? The language is (a^i) b ((ab)^j) $\endgroup$ – hermi Apr 20 at 14:04
  • $\begingroup$ It wont necessarily help you, but not knowing the language will only hinder you. $\endgroup$ – nir shahar Apr 20 at 15:53
  • 1
    $\begingroup$ @Narcissus though it is true that certain ambiguous grammars have an unambiguous language (i.e. the ambiguity is not inherent to the language),trying to find out the language using given grammar shall make you understand the way sentences in the language are derived using the production rules. Suppose if the grammar is ambiguous you shall find a way to guess a string with two distinct parse trees. Moreover if the grammar is unambiguous, you shall be able to figure out what is the thing which at each step is preventing you to get two different parse trees. $\endgroup$ – Abhishek Ghosh Apr 20 at 19:39
  • 1
    $\begingroup$ @Narcissus This problem being undecidable, there is no general algorithm/mechanical way to solve such problems in general. You need to dig into the specific instance given $\endgroup$ – Abhishek Ghosh Apr 20 at 19:43
1
$\begingroup$

The main observation is that every word generated by $Y$ starts with $b$.

Consider a word $w$. If it starts with $a$, it must have resulted by applying the rule $X \to aX$. Otherwise, it must have resulted by applying the rule $X \to Y$. In other words, if $w = a^n b z$, then the derivation must start by applying $n$ many times the rule $X \to aX$, and then deriving $bz$ from $Y$. We can determine the entire derivation given $|bz|$; details left to you.

$\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.