문법을 증명하는 방법은 모호합니까?

Question

나는 문법에 익숙하지 않고 누군가가 파스 트리를 사용하여 아래 문법이 모호한 것을 어떻게 결정할 수 있는지 궁금해하고있다. 내가 만들 수있는 두 개의 다른 문자열이 필요하다는 것을 알고 있습니다.

S -> (S)|SS|() 

나는 데프 정상적인 형태와 greibach을 촘스키로 변환 할 수 있지만, 모호함이 저를 당혹이다.

Answer 1

모호한 문법을 ​​증명하는 가장 쉬운 방법은 두 개의 다른 구문 분석 트리가있는 문장을 찾는 것입니다. 문장 X X X 두 개의 서로 다른 구문 분석 트리를 가지고 있기 때문에 (.. 또는 당신이 원하는 경우, 정확히 같은 일 또는 두 개의 서로 다른 오른쪽 유도, 두 개의 서로 다른 왼쪽의 유도)

S → S S | X은 (어떤 X의 경우) 항상 모호합니다 :

 S   S 
    /\  /\ 
/ S  S \ 
//\ /\ \ 
X X X X X X