Wie testet man eine Grammatik?

OP #3191226
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?
Gast #3191297
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.
Gast #3191315
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...
OP #3191359
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 :)

Antwort schreiben

Eine eigene Frage? Dieser Thread ist über 13 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.