Beweis der Eigenschaft
Gegeben sei das Alphabet und die Sprache definiert als:
Die Sprache besteht also aus allen Wörtern über , in denen die Summe der Anzahlen der Buchstaben ‘a’ und ‘b’ gleich der Anzahl der Buchstaben ‘c’ ist.
Zu zeigen (Z.Z.):
Beweis:
-
Wir nehmen zwei beliebige Wörter . Nach Definition von gilt:
und
-
Betrachten wir das Wort , die Konkatenation von und . Es gilt für die Anzahlen der Buchstaben in :
-
Durch Addition der entsprechenden Gleichungen für und erhalten wir:
Da und , kann dies umgeschrieben werden zu:
Dies entspricht der Anzahl der ‘c’s in :
-
Also erfüllt jedes Wort , das durch Konkatenation von Wörtern aus gebildet wird, die Bedingung für die Zugehörigkeit zu . Daher ist jedes Wort in auch in enthalten.
-
Zusätzlich ist das leere Wort , das durch die Anwendung des Kleene-Sterns eingeschlossen ist, trivialerweise in , da keine Buchstaben vorhanden sind und somit die Bedingung erfüllt ist, da alle Zählungen null sind.
Fazit:
Da sowohl das leere Wort als auch jede Konkatenation von Wörtern aus die definierende Eigenschaft von erfüllen, haben wir gezeigt, dass .