Wie man zeigt, dass die angegebene Sprache eindeutig ist

Question

Gegeben nach Grammatik:

$$ begin {align} s rightarrow & a1b a rightarrow & 0a mid varepsilon b rightarrow & 0b Mid 1b Mid varepsilon end {align} $$

Wie kann ich zeigen, dass diese Grammatik eindeutig ist? Ich muss eine Grammatik für dieselbe Sprache finden, die mehrdeutig ist, und sie demonstrieren.

Ich weiß, wenn ich gebeten wurde zu beweisen, dass die Sprache eindeutig ist, sollte ich zwei verschiedene Parse -Bäume für die gleiche Schnur finden, aber ich weiß nicht, was ich tun soll.

Answer 1

Um eine Grammatik zu zeigen, ist eindeutig, dass Sie argumentieren müssen, dass es für jede Zeichenfolge in der Sprache nur einen Ableitungsbaum gibt.

In diesem speziellen Fall können Sie feststellen, dass $ A $ nur 0 $ $ generiert, sodass die vom Startsymbol $ S $ generierten $ 1 $ der erste $ 1 $ in der Zeichenfolge sein müssen.

Jede Grammatik kann mehrdeutig gemacht werden, indem Kettenproduktionen wie $ S bis S $ hinzugefügt werden.

Answer 2

Diese Grammatik entspricht $$ begin {align} s rightarrow & 0a1b mid 1b a rightarrow & 0a Mid varepsilon b rightarrow & 0b mid 1b mid varepsilon {end {{align } $$ und so wie Eine einfache Grammatik, die wir zeigen können, dass diese Grammatik nicht mehrdeutig ist. Natürlich ist diese Grammatik nicht einfach.