Контекстно-бесплатная грамматика неоднозначная?

Question

Для следующей контекстно-свободной грамматики:

S --> (S) | SS | A

A --> a | A,A | E        (E is the empty string)

Формальное определение:

G=(V,T,P,S)

V={A,S}

T={E;a; ( ; ) ; , }

S=S

P:
S --> (S)
S --> SS
S --> A
A -->a

A -->A,A

A --> E    (E is the empty string)

Как я узнаю, что эта грамматика неоднозначна или нет? Спасибо.

Answer 1

Если бы это было неоднозначно, достаточно было бы найти слово, которое анализируется несколькими различными способами. Чтобы доказать, что оно не является двусмысленным, вы можете использовать более общее доказательство и доказать, что это особый случай, или вы можете построить доказательство по индукции на основе некоторого свойства набора сгенерированных слов.

Смотрите (хотя и сложный) пример здесь.