Theo.Inf. Beweis finden das jede regulaere Sprache von einer Context freien Grammatik gen. wird die nicht mehrdeutig ist
-
Hi,
ich befasse mich gerade mit Theoretischer Informatik und moechte beweisen das jede regulaere Sprache von einer Context freien Grammatik generiert wird die nicht mehrdeutig ist.
Ich habe gedacht man keonnte das vielleicht duch einen Beweis durch Wiederspruch zeigen indem man zeigt das dann auch der DFA mehrdeutig sein muesste aber das scheint irgendwie nicht zu klappen. Hat jemand eine andere Idee?Vielen Dank
MammOhMann
-
MannOhMann schrieb:
Hi,
ich befasse mich gerade mit Theoretischer Informatik und moechte beweisen das jede regulaere Sprache von einer Context freien Grammatik generiert wird die nicht mehrdeutig ist.
Ich habe gedacht man keonnte das vielleicht duch einen Beweis durch Wiederspruch zeigen indem man zeigt das dann auch der DFA mehrdeutig sein muesste aber das scheint irgendwie nicht zu klappen. Hat jemand eine andere Idee?Das kann nicht klappen. Die Aussage, die du zeigen willst ist, dass es zu einer gegebenen Regulären Sprache eine nicht mehrdeutige kontextfreie Grammatik existiert, die diese Sprache erzeugt.
Du kannst nicht zeigen, dass es keine mehrdeutige gibt. Du kannst aus eine eindeutigen kontextfreien Grammatik auf ganz einfache weise eine mehrdeutige Grammatik erstellen, die die selbe Sprache erzeugt. Dementsprechend kann dein Beweis nicht klappen.
Die Frage ist, wie hast du reguläre Sprache definiert? Bei uns ging das über eine reguläre Grammatik, die existieren muss und diese Sprache erzeugt. Und man konnte einfach sehen, dass jede reguläre Grammatik auch kontextfrei ist.
Falls du weißt, dass jede reguläre Sprache durch einen DEA (oder DFA, wie du es nennst) entschieden werden kann, dann versuch mal aus einem gegebenen DEA eine Grammatik zu erstellen, die eindeutig und regulär ist... Dann hast du das gezeigt.
-
Versteh ich nicht ganz, wenn ich das für einen DFA zeige dann gilt es aber doch nicht für jeden oder ?
-
Was bedeutet mehrdeutig? Ansonsten: Baue aus einen DFA eine rechtslineare Grammatik. Also das Non-Terminal steht rechts. Jeder Zustand wird ein Non-Terminal und fuer jeden Uebergang gibt es eine Regel. Wenn z.B. von Zustand (1) nach (2) unter Eingabe von a gewechselt wird, dann sieht die Regel wie folgt aus: 1->a2. Die Eigenschaften des DFA uebertragen sich somit auf die Grammatik.
Versteh ich nicht ganz, wenn ich das für einen DFA zeige dann gilt es aber doch nicht für jeden oder ?
Nicht, wenn du deinen Beweis allgemein genug haelst.
-
MannOhMann schrieb:
Versteh ich nicht ganz, wenn ich das für einen DFA zeige dann gilt es aber doch nicht für jeden oder ?
Nicht für einen. Für jeden. Also ganz allgemein.
knivil schrieb:
Was bedeutet mehrdeutig?
Eine kontextfreie Grammatik heißt mehrdeutig, falls es zu einem Wort aus ihrer Sprache zwei verschiedene (Rechts-)Ableitungen gibt. Falls es kein solches Wort gibt, eindeutig.
-
Dann muss man seinen DFA eben erst minimieren.
-
knivil schrieb:
Dann muss man seinen DFA eben erst minimieren.
Das braucht man für den Beweis nicht.