문제

ive been trying to prove a grammar ambiguous, from my understanding its not, but according to the question; it should be ambiguous. The grammar is

S -> AB | aaB
A -> a | Aa
B -> b

the string ive been using is aaab. From what it seems, i dont see any way the Left and Right trees can be different. To begin with the string is either AB or aaB form, if its aaB form, game over, if its AB form, you can either end with a, or continue another branch in Aa.

도움이 되었습니까?

해결책

From what I can see, there is exactly one string which has more than one parse tree (or equivalently, more than one left-most derivation): aab

S -> AB -> AaB -> aaB -> aab

or

S -> aaB -> aab

This one string makes the grammar ambiguous.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top