die erste Regel ist der Induktionsanfang. \( \{BR\} \) enthält kein "\(BO\)" als Zeichenfolge irgendeines Wortes.
Sei \( L_n \) eine Sprache über \( \{B, R, O\} \), die in keinem Wort die Zeichenfolge "\(BO\)" enthält.
Dann folgt mit der zweiten Regel trivialerweise, dass kein durch diese Regel erzeugtes Wort die Zeichenfolge "\(BO\)" enthält. (Die einzige in Hinsicht auf \( xR \) neue zweistellige Zeichenfolge in \(xRO\) ist "\(RO\)".)
Ein Wort \(Bx\) enthält die Zeichenfolge "\(BO\)" nicht. Insbesondere enthält die Zeichenfolge \( x \) weder die Zeichenfolge "\(BO\)", noch beginnt sie mit "\(O\)". \( xx \) kann folglich nicht die Zeichenfolge "\(BO\)" enthalten. (Die einzige in Hinsicht auf \(Bx\) neue zweistellige Zeichenfolge besteht aus dem letzten Buchstaben von \(x\) gefolgt von dem ersten Buchstaben von \(x\), letzterer ist aber kein "\(O\)", da \(Bx\) mit seinen ersten beiden Buchstaben sonst die Buchstabenfolge "\(BO\)" enthielte, im Widerspruch zur Voraussetzung.)
Damit ist alles gezeigt.
Mister
