Comment montrer que la langue donnée est sans ambiguïté

Question

Compte tenu de la grammaire suivante:

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

Comment puis-je montrer que cette grammaire est sans ambiguïté? Je dois trouver une grammaire pour la même langue qui est ambigu, et le démontrer.

Je sais que si on m'a demandé de prouver que la langue est alors je ambiguë trouver deux arbres d'analyse différents pour même chaîne, mais je ne sais pas quoi faire.

Answer 1

Pour afficher une grammaire est sans ambiguïté que vous devez faire valoir que pour chaque chaîne dans la langue il n'y a qu'un seul arbre de dérivation.

Dans ce cas particulier, vous pouvez observer que $ A $ seulement génère $ 0 $ 's, de sorte que le 1 $ généré par le symbole de départ $ S $ doit être la première 1 $ dans la chaîne.

Toute la grammaire peut être ambiguë en ajoutant des productions de la chaîne comme $ S \ S $.

Answer 2

Cette grammaire équivaut à $$ \ Begin {align} S \ rightarrow & 0A1B \ mid 1B \\ A \ rightarrow & 0A \ mid \ varepsilon \\ B \ rightarrow et 0B \ mid 1B \ mid \ varepsilon \\ \ End {align} $$ et ainsi comme une grammaire simple, nous pouvons montrer que cette grammaire n'est pas ambiguë. Bien sûr, cette grammaire est pas simple.