Grammatik für Bitsequenzen erstellen (Informatik Studium)?
Hi, also ich studiere Informatik im ersten Semester und habe eine Übung, die ich bald abgeben muss. Ich hab auch keine Probleme soweit, nur brauch ich bei einer Frage gerade bisschen Hilfe, weswegen ich hier mal nachfragen wollte.
Ich möchte keine Lösung, sondern lediglich irgendwie einen Denkanstoß oder Hinweis.
Also die Aufgabe lautet:
Geben Sie für diese Aufgabe eine kontextfreie Grammatik G an, die folgende Sprachen erzeugt:
Bitsequenzen, in denen zuerst eine nichtleere Folge von Nullen, dann eine nichtleere Folge von Einsen steht, wobei die Anzahl von Einsen ungleich der Anzahl von Nullen ist, etwa 00111 oder 000001.
Ich habe schon eine Grammatik, die mir jede beliebige Bitsequenz ausgeben kann, jedoch würden da die Fälle eintreten, dass die Anzahl von 0 und 1 auch gleich sein könnten, was nicht gemäß der Aufgabe ist.
Die lautet so:
G = (N, T, P, Bitsequenz)
N = { Fragment, Bitsequenz }
T = { 0, 1 }
P = { Bitsequenz = 0 Fragment 1,
Fragment = 0 Fragment | Fragment 1 | 0 | 1, }
Geht es überhaupt, dass man eine Grammatik für auch unendliche lange Bitsequenzen erstellen kann, die garantiert, dass die Anzahl 0 und 1 ungleich ist? Weil es gibt ja keine Kontrollstruktur in der Grammatik, die das prüfen könnte.
Bin sehr dankbar für Hilfe
1 Antwort
Also prinzipiell sollten es die Regeln
S -> 0A1
A -> 0A1|B|C
B -> 0B|0
C -> 1C|1
erfüllen.
Mit den ersten beiden Regeln erzeugst du eine Weile lang gleich viele Nullen und Einsen (mindestens 1 Mal). Durch den Wechsel nach B oder C danach dann noch ne beliebige Anzahl (mindestens 1 Zeichen) von Nullen oder Einsen.
Du hast also die Regeln erfüllt damit.
Müsste sich sauber in eine kontextfreie Grammatik (Chomsky-2) überführen lassen, wenn ich das noch richtig im Kopf habe.
Dein Problem bei der Aufgabe war, dass du mehrere Variablen brauchst dafür. Denn nur mit einer wie in deiner Aufgabe kannst du das nicht erreichen. Damit ginge meiner Ansicht nach höchstens eine Grammatik, wo gleich viele oder nur eine begrenzte Anzahl mehr von dem einen als dem anderen Zeichen vorkommen. Aber nicht grundsätzlich nur mehr Nullen als Einsen oder umgekehrt in beliebiger Anzahl.
Danke für die Hilfe. Ja das war ein Versehen weil ich diese Frage hier gestellt hatte und sie dann nirgends auffindbar war und ich sie auch nicht einsehen konnte. Ich dachte sie wurde aus irgendeinem Grund nicht erstellt und da hatte ich nochmal gefragt ^
Übrigens: Beiträge bitte nicht doppelt posten. Das ist ärgerlich für alle, die Antworten schreiben, aber nicht sehen, dass der Beitrag woanders schon diskutiert wurde.