Ich habe eine Frage zur Theoretischen Informatik.
Ich habe eine Aufgabe, bei der ich zur folgenden Sprache eine Grammatik
bilden soll:
L = {0^n * 1^m | n != m}
Dabei habe ich mir folgende Grammatik überlegt:
1 | S -> GE | EF
|
2 | E -> 0E1 | epsilon
|
3 | F -> 1 | 1F
|
4 | G -> 0|0G
|
Die Überlegung war, dass ich im mittleren Teil eine gleiche Anzahl von
Nullen und Einsen konkateniere, oder eben nichts (epsilon).
Und daran hänge ich dann links beliebig viele Nullen(mindestens aber
eine) an, oder rechts davon beliebig viele Einsen(mindestens aber eine)
an.
Für mich erscheint das im Moment logisch und vielleicht ist das auch
richtig, aber gibt es einen Weg, dass auch zu beweisen?
