Comment prouver une grammaire est ambigu? S -> (S) | SS |()

Question

Je suis plutôt novice en grammaire et je me demandais si quelqu'un pouvait m'aider à déterminer à l'aide d'un arbre d'analyse comment cette grammaire est ambiguë? Je sais qu'il doit avoir deux chaînes différentes qui peuvent être créées.

S -> (S)|SS|() 

Je def le convertir en forme normale et CHOMSKY greibach, mais l'ambiguïté laisse perplexe à moi avec ces derniers.

Answer 1

La manière la plus simple de prouver une grammaire ambiguë est de trouver une phrase avec deux arbres d'analyse différents. (.. Ou deux différentes dérivations les plus à droite, ce qui est exactement la même chose ou, si vous préférez, deux différentes dérivations de plus à gauche)

S → S S | X est toujours ambiguë (pour tout X), parce que la phrase X X X a deux arbres d'analyse différentes:

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