I need to prove this context free grammar ambiguous, I know to prove this I need to find 2 different paths of the same string, but this question has 'begin' and 'end' which I don't know what they mean
S -> begin A end
A -> A ; A | a | S
Asked
Active
Viewed 908 times
0
-
1I guess "begin" and "end" are just some terminals. – dtldarek Aug 24 '13 at 20:23
2 Answers
0
Hint:
- Let $B \to B\ \,;\ B \mid \mathtt{b}$.
- Prove that the above grammar is ambiguous.
- Prove that any grammar that uses $B$ is ambiguous.
- If it is not specified, then "begin" and "end" words are just some terminals (those are lower-case after all).
I hope this helps $\ddot\smile$.
dtldarek
- 37,381
-
it will just produce "b;b" or "b;b;b;b" ... I'm not sure how to prove that ambiguous, still confusing about this problem – Herious Aug 24 '13 at 22:01
-
@Herious Do you know how to produce "b;b;b"? In how many ways you can do this? – dtldarek Aug 24 '13 at 22:09
-
@Herious Take $C \to \mathtt{b}, B, \mathtt{b}$. In how many ways you can get "bb;b;bb"? What about $D \to \mathtt{begin}, B, \mathtt{end}$? – dtldarek Aug 24 '13 at 22:16
-
0
begin and end must be terminals.
all CFG (without useless symbols) with left and right recursion for the same symbol is ambiguous.
In this case, the productions A -> A ; A | a | S are causing ambiguity.
For example, the string 'begin a; a; a end' has 2 leftmost derivations:
S > begin A end > begin A ; A end > begin A ; A; A end > begin a ; A ; A end > begin a ; a ; A end > begin a ; a ; a end
S > begin A end > begin A ; A end > begin a ; A end > begin a ; A ; A end > begin a ; a ; A end > begin a ; a ; a end
This is because the production A -> A ; A does not indicate whether the ";" is left or rigth associative. If you want ";" to be left associative, you should write:
A -> A ; a | A ; S | a | S
I hope this help you.
Andres
- 39