ContextFreeGrammar ambiguity

Question

주어진 CFG : S--> aS | Sa | b 두 개의 서로 다른 파스 트리에서 만들 수있는 문자열을 찾을 수 없습니다.

중간 상태는 재귀를 남겼지 만 CFG 모호성을 나타내는 문자열이 없어도 제거하지 않고 있습니까? 누구든지 PLZ 도움이 될 수 있습니다.

S -> aS -> aSa -> aba 

을 그리고 당신은 규칙 2, 3, 1을 적용 할 경우, 동일한 문자열을 얻을 :

Answer 1

당신은 규칙 1, 2, 3을 적용하면, 당신은 얻을

가

S -> Sa -> aSa -> aba 

있다을 모호. http://services.brics.dk/java/grammar/demo.html

문법을 입력하고 analyze the grammar for potential ambiguity 확인 :

S : "a" S 
    | S "a" 
    | "b" 

결과 :

*** vertical ambiguity: S[#1] <--> S[#2] 
    ambiguous string: "aba" 
the grammar is ambiguous!