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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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?
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.