문맥 자유 문법은 왼쪽과 오른쪽 재귀가 될 수 있습니까?

Question

ex.

S-> S + T | T

T-> U - T | U

U -> ID | N

연관성은 분명히 보존되지 않습니다. 하지만 어쨌든 모호하다는 것을 알 수는 없습니다. 그래서 이것은 모호하지 않은 cfg입니까?

Answer 1

문법은 표시하는 것처럼 왼쪽과 오른쪽 모두 재귀를 가질 수 있지만 그다지 의미는 없습니다. 모든 문법 때문에 모든 재귀이 중 왼쪽 또는 오른쪽으로 (그러나 지속적으로 문법하지 않는 한 같은 사람이 정기적입니다)되어 다시 작성할 수 있습니다 :

A -> B A C 

가된다 :

A -> B X 
X -> A C 

이제 상호 재귀가 한 규칙에서 왼쪽에 있고 다른 규칙에서 오른쪽에있는 질문의 문법은 모호하지는 않지만 실제로는 왼쪽 또는 오른쪽 재귀와 관련이 없습니다.