контекст свободная грамматика двусмысленная?

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

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

См. Пример (хотя и сложный) here.