Come dimostrare che data lingua è inequivocabile

Question

Dato seguente grammatica:

$$ \ Begin {align} S \ rightarrow & A1B \\ A \ rightarrow & 0A \ metà \ varepsilon \\ B \ rightarrow & 0B \ metà 1B \ metà \ varepsilon \\ \ End {align} $$

Come posso dimostrare che questa grammatica è ambigua? Ho bisogno di trovare una grammatica per la stessa lingua che è ambiguo, e dimostrarlo.

Lo so se mi è stato chiesto di dimostrare che la lingua è ambigua allora dovrei trovare due diversi alberi di analisi per la stessa stringa, ma non so cosa fare.

Answer 1

Per mostrare una grammatica è ambigua si deve sostenere che per ogni stringa nella lingua v'è un solo albero di derivazione.

In questo caso particolare è possibile osservare che $ A $ genera solo $ 0 $ 's, in modo che il $ 1 $ generato dal simbolo iniziale $ s $ deve essere il primo $ 1 $ nella stringa.

Ogni grammatica può essere reso ambiguo con l'aggiunta di produzioni a catena come $ S \ S $.

Answer 2

Questa grammatica è equivalente con $$ \ Begin {align} S \ rightarrow & 0A1B \ mid 1B \\ A \ rightarrow & 0A \ metà \ varepsilon \\ B \ rightarrow & 0B \ metà 1B \ metà \ varepsilon \\ \ End {align} $$ e così come una semplice grammatica possiamo dimostrare che questa grammatica non è ambiguo. Naturalmente questa grammatica non è semplice.