Wie testet man eine Grammatik?

[Mike M. (mikeii)]

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:

S -> GE | EF
E -> 0E1 | epsilon
F -> 1 | 1F
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?

[D. I. (Gast)]

Naja jenachdem in welcher Chomsky-Klasse du unterwegs bist (das Ding 
schaut regulär, also nach Chomsky-3, aus, könnte aber auch kontextfrei 
sein - Chomsky-2) gibts unterschiedliche Methoden.

Pumping-Lemma wäre da ein Begriff der mir gerade in den Sinn kommt. 
Dieses geht sowohl für C3 als auch für C2.

Edit: Sorry, Pumping-Lemma war ne andere Baustelle, dann kann ich dir 
leider grad doch nicht weiterhelfen.

[Mike M. (mikeii)]

Kontextfrei ist die Grammatik, das weiß ich schon, aber das will ich 
nicht beweisen, die Regularität auch nicht, nur ob diese Grammatik mir 
auch die richtige Sprache erzeugt.

[D. I. (Gast)]

Einen Ansatz hätte ich vllt:

Bau einen Automaten für deine Grammatik und einen für die Sprache und 
dann beweise, dass die beiden Automaten äquivalent sind bzw ineinander 
überführbar sind, vllt geht das.

Puh Formale Sprachen sind schon ne zeitlang her...

[Mike M. (mikeii)]

Hm, ob ich das schon kann weiß ich noch nicht, ich belege das Fach erst 
seit dem Semester (leider, hätte ich schon früher machen können).
Wenn ich das recht verstehe brauche ich hier einen Kellerautomaten, 
damit ich die Anzahlen unterscheiden kann. Aber da ist mir nicht ganz 
klar wie ich das bewerkstelligen kann.
Ich werde es mal versuchen, evtl. wird was draus :)