Endlicher Automat + Reguläre Grammatik

[Rah2k]

Hallo,
dieses ganze Thema Reguläre Grammatik bereitet mir etwas Kopfschmerzen...Folgende Aufgabe habe ich zu Lösen:

Wir haben uns in der Vorlesung mit den allgemeinen EBNF-Regeln für die Beschreibung einer ganzen Zahl beschäftigt. Die dort verwendeten Regeln entsprachen aber noch nicht denen einer regulären Grammatik. Definieren Sie bitte eine reguläre Grammatik zur Beschreibung von ganzen Zahlen. Denken Sie daran, dass eine Zahl evtl. mit einem negativen Vorzeichen beginnen kann. Die Zahl wird ohne führende Nullen geschrieben, kann aber beliebig lang sein. Konstruieren Sie anschließend einen endlichen Automaten, der ganze Zahlen erkennen kann. Geben Sie die Übergangsfunktion δ sowohl in Form einer Tabelle als auch in Form eines Zustandsdiagramms an.

EBNF:

Zahl = ([-], EinBisNeun, {NullBisEins} | "0";
EinsBisNeun = "1" | "2" | ... | "9";
NullBisNeun = "0" | "1" | ... | "9";

Mein Problem ist nun die EBNF-Notation in eine reguläre Grammatik zu fassen. Meine bisherige Lösung:

G = (N, T, P, S);
N = {S, R, Z};
T = {0,1,2,...,9,+,-};
P = {
  S --> +Z
  S --> -Z
  S --> 0..9
  S --> 1..9R
  R --> 0..9
  R --> 0..9R
  Z --> 1..9
  Z --> 1..9R
}

Zustandsdiagramm:
Im Anhang.

Kann mir jemand sagen ob das soweit korrekt ist?

 

[httpdigest]

Ich denke, nur Minus ist ein gültiges und optionales führendes Vorzeichen. Und du solltest wahrscheinlich auch Epsilon zur Hilfe nehmen, um deine Regeln nicht häufig duplizieren zu müssen. Desweiteren würde ich den zweiten, dritten und vierten S Übergang vereinfachen.

G = (N, T, P, S);
N = {S, R, Z};
T = {0,1,2,...,9,-};
P = {
  S --> 0
  S --> Z
  S --> -Z
  Z --> 1..9R
  R --> 0..9R
  R --> ε
}

 

[Rah2k]

  S --> Z

Danke! Aber darf man das so machen? In einer Regulären Grammatik muss doch immer auf der "rechten Seite" ein Terminal stehen. Und noch eine allgemeine Frage zur regulären Grammatik: Darf ich die Produktionsregeln auch in der EBNF darstellen?

 

[httpdigest]

Das wäre zwar eine "erweiterte" reguläre Grammatik, aber immer noch eine reguläre Grammatik.
Du hast aber Recht, und streng genommen dürftest du auch nicht die Abkürzung "0..9" bzw. "1..9" benutzen. Wenn du also auf Nummer Sicher gehen willst, dann müsstest du das Ganze wohl so machen:

G = (N, T, P, S);
N = {S, R, Z};
T = {0,1,2,...,9,-};
P = {
  S --> 0
  S --> -Z
  S --> 1R
  S --> 2R
  S --> 3R
  S --> 4R
  S --> 5R
  S --> 6R
  S --> 7R
  S --> 8R
  S --> 9R
  Z --> 1R
  Z --> 2R
  Z --> 3R
  Z --> 4R
  Z --> 5R
  Z --> 6R
  Z --> 7R
  Z --> 8R
  Z --> 9R
  R --> 0R
  R --> 1R
  R --> 2R
  R --> 3R
  R --> 4R
  R --> 5R
  R --> 6R
  R --> 7R
  R --> 8R
  R --> 9R
  R --> ε
}

Das kannst du nicht 1-zu-1 genau so als EBNF schreiben, da die reguläre Grammatik hier ja nicht-deterministisch ist. Das heißt, es gibt mehrere Übergänge mit demselben Start-Nicht-Terminal. Um das Ganze als EBNF abzubilden, darf es immer nur einen Übergang mit demselben Nicht-Terminal geben. Es gibt denke ich sogar einen Algorithmus, um von einer strikten rechts-regulären Grammatik zu einer EBNF zu kommen.

 

[httpdigest]

... da die reguläre Grammatik hier ja nicht-deterministisch ist. Das heißt, es gibt mehrere Übergänge mit demselben Start-Nicht-Terminal.

Sorry, das Ganze war leider nicht ganz korrekt. Um das Ganze nochmal formal korrekt zu sagen: Eine rechts-reguläre Grammatik ist im Allgemeinen immer äquivalent zu einem nicht-deterministischen endlichen Automaten, so dass der Automat dieselbe Sprache erkennt wie die Grammatik generiert. Was wir also mit dieser Grammatik haben, sind ja ziemlich 1-zu-1 unsere Zustandsübergänge für das Zustandsübergangsdiagramm des Automaten, das du ja auch zeichnen sollst.
Dass diese reguläre Grammatik aber nicht-deterministisch ist, ist falsch. Insbesondere war auch falsch, dass die Grammatik nicht-deterministisch sein soll, weil sie mehrere Produktionsregeln mit demselben Start-Nichtterminalsymbol hat. Eine Grammatik kann nicht deterministisch oder nicht-deterministisch sein. Sie enthält ja Produktionsregeln zum Generieren einer Sprache, bzw. zum Generieren aller Sätze dieser Sprache. Automaten auf der anderen Seite können eine Sprache bzw. Sätze einer Sprache erkennen, müssen also bei Input eines Satzes für jedes Zeichen aus den Zustandsübergängen erkennen können, welchen Zustand sie für dieses Zeichen als nächstes einnehmen sollen.
Wollte ich nur nochmal klarstellen und mich berichtigen, da man bei solchen Sachen einfach formal korrekt sein muss, um nichts durcheinanderzubringen.
Wenn du jetzt also aus den Produktionsregeln der Grammatik dein Zustandsübergangsdiagramm des Automaten malst, dann kann dieser Automat nicht-deterministisch oder deterministisch sein. Das ergibt sich dann daraus, dass er mehrere Zustandsübergänge ausgehend von einem Zustand über dasselbe Terminalsymbol zu unterschiedlichen anderen Zuständen hat. Wenn das passiert, ist es ein nicht-deterministischer Automat, da ja nicht entschieden werden kann, über welchen Übergang zu welchem der möglichen Folgezustände man nun gehen soll, wenn man das Terminalsymbol liest.
In unserem Fall wäre der Automat aber wohl deterministisch, da es keine zwei Produktionsregeln bzw. Zustandsübergänge vomselben Nicht-Terminalsymbol über dasselbe Terminalsymbol zu unterschiedlichen Nicht-Terminalsymbolen gibt. Also es gibt nicht sowas in der Grammatik:

A --> aA
A --> aB

 

[Rah2k]

@httpdigest Danke für die ausführliche Erklärung, so langsam wird mir das ganze Thema etwas klarer.
Ich habe das ganze nun mal in ein Zustandsdiagramm- und -Tabelle überführt (Anhang). Das kann man denke ich so lassen oder?

Zur Grammatik nochmal (Weil ich das ganze auch Verstehen möchte): Großbuchstaben werden ja in den Produktionsregeln als Nicht-Terminal erkannt. Angenommen ich möchte eine Grammatik für ein Personennamen erstellen, indem ausdrücklich ein Großbuchstabe vorkommen muss. Wie kann ich dann in den Produktionsregeln den Großbuchstaben von einem Nicht-Terminal unterscheiden? Dürfte ich sowas machen?

G = (N, T, P, <S>)
N = {<S>, <A>}
T = {a,...,z,A,...,Z}
P = {
   <S> --> α<A>
   <A> --> β<A> |
   α ∈ {A,...,T}
   β ∈ T
}

Danke schon mal vorab.

 

[httpdigest]

Normalerweise werden nur Endzustände (und nicht der Startzustand) mit einem doppelten Rahmen markiert. Was der Startzustand sein soll, erkennt man daran, dass ein unmarkierter Pfeil von "Außen" zu ihm läuft - dieser fehlt noch bei dir.
Außerdem könntest du auch noch zwischen dem Endzustand für erfolgreiches Erkennen und fehlerhaftes Erkennen unterscheiden. Z.B. ist ja der String "-1-" ungültig, würde bei dir aber auch zu E führen (S -> Z -> R -> E).
Und du solltest vielleicht wirklich ein vernünftiges Graphenzeichen-Tool verwenden mit runden Kreisen. Die Rechtecke sind für ein Zustandsübergangsdiagramm etwas verwirrend.
Ich empfehle dir wärmstens Graphviz.
Windows-Download: https://graphviz.gitlab.io/_pages/Download/windows/graphviz-2.38.zip
Du musst nur ganz kurz in die Graphviz-Deklarationssprache (DOT Language) reinkommen und dann baut dir das Tool einen gelayouteten Graphen.
Schau dir z.B. mal das hier an: https://www.graphviz.org/pdf/dotguide.pdf
Dadurch würde deine Zeichnung schonmal sehr viel professioneller aussehen und nicht wie als wäre sie mit dem Zeichentool innerhalb von MS Word gemacht worden.

Bezüglich der Benutzung von Großbuchstaben als Terminalsymbole würde ich sagen, alles ist okay, solange du die Bedeutung der Symbole durch die Mengen eindeutig klärst. Hast du ja soweit gemacht. Ich bin mir nur nicht 100%ig sicher, ob die Abkürzung mit β ∈ T als Terminalsymbol erlaubt ist. Ist ja auch wieder nur ein Shortcut ähnlich wie 0..9 oder 1..9.

 

[Rah2k]

Normalerweise werden nur Endzustände (und nicht der Startzustand) mit einem doppelten Rahmen markiert. Was der Startzustand sein soll, erkennt man daran, dass ein unmarkierter Pfeil von "Außen" zu ihm läuft - dieser fehlt noch bei dir. [...] Die Rechtecke sind für ein Zustandsübergangsdiagramm etwas verwirrend.

Das mit den Rechtecken und der Umkreisung des Startzustandes sollen wir laut Prof. so machen. Du hast mir jedenfalls wieder sehr weiter geholfen, danke!

 

[httpdigest]

Eine Sache noch, die mir beim Rüberschauen deines Zustandsübergangsdiagramms noch aufgefallen ist: Er erkennt noch nicht erfolgreich "1". Wenn du die Eingabe "1" auf den Automaten anwendest, dann ist er ja erst im "Z" Zustand.
Hast du die reguläre Grammatik wirklich 1:1 so umgesetzt? Denn in dieser produziert ja S bei 1 sofort R (was mit Epsilon auch gleich ein Endzustand wäre).
Was man an dem Diagramm nun nicht erkennt (und deswegen meinte ich, soll man Endzustände mit doppeltem Rahmen zeichnen), ist, ob "Z" jetzt nun auch ein erfolgreicher Endzustand ist, oder nicht.
Es macht seeeehr viel mehr Sinn, die Endzustände als solche zu kennzeichnen und das wird überall auch so gemacht. Ich halte es für sehr unwahrscheinlich, dass dein Prof. eine solche Kennzeichnung nicht haben möchte.
Vielleicht nochmal kurz zum Sinn eines solchen Automaten: Er soll in der Lage sein, valide Sätze einer Sprache zu erkennen. Und, wenn man nicht weiß, wann er denn nun einen Satz erfolgreich erkannt hat, bringt es ja eigentlich nichts, bzw. man kann diesen Automaten dann nicht implementieren.

 

[Rah2k]

Also wir sollen Endzustände mit einem "gestrichelten" Rechteck kennzeichnen. Das habe ich in meinem Zustandsdiagramm oben auch gemacht, erkennt man nur nicht gut auf dem Bild. Fehlerzustände sollen wir so gestalten, dass diese einfach nicht mehr verlassen werden und den Startzustand eben doppelt einrahmen. Ein Beispiel aus der Vorlesung im Anhang. "E" soll in meinem Diagramm einfach das Epsilon darstellen.

Also: Z und R sind bei mir Endzustände. E mit Epsilon der Fehlerzustand, welcher nicht mehr verlassen werden kann. So haben wir es zumindest gelernt

 

[Rah2k]

@httpdigest ich muss dich nochmals nerven. Könnte man die Produktionsanweisung auch wie folgt darstellen?

 S= ("1",A | "2",A | ... | "9",A) | "-",B | "0";
A = ("0",A | "1",A | ... | "9",A) | eps;
B = ("1",A | "2",A | ... | "9",A);

Das ist die Schreibweise, welche wir in den Vorlesungen verwendet haben und ich denke in der Klausur wird diese auch verlangt.

Wobei, sowas wie

 ("0", A) | ("1", A)

darf man nicht machen oder?
Danke vorab!

 

[httpdigest]

Zum ersten Code-Block: Kann sein, dass ihr das dürft. Das weiß ich nicht.
Zum zweiten Code-Block: Warum soll man das nicht dürfen? Ist doch syntaktisch dasselbe wie die ersten Varianten.

 

[Rah2k]

Zum zweiten Code-Block: Warum soll man das nicht dürfen? Ist doch syntaktisch dasselbe wie die ersten Varianten.

Aber wenn ich die Grammatik in einem Ableitungsbaum darstellen würde, hätte ich 3 Kindsknoten (S -> "0", "1" und "A"). Wie soll das denn gehen *confuse*

 

[httpdigest]

Häh? Dein zweiter Codeblock:

("0", A) | ("1", A)

entspricht doch exakt dem Anfang von der zweiten Zeile (der Produktionsregel für A) in:

S = ("1",A | "2",A | ... | "9",A) | "-",B | "0";
A = ("0",A | "1",A | ... | "9",A) | eps;
B = ("1",A | "2",A | ... | "9",A);

sagt es doch: "Entweder eine '0' gefolgt von A, oder eine '1' gefolgt von A." (solange der Kommaoperator ',' auch "gefolgt von" bedeutet, was ich jetzt mal vermute)
Das ist doch ziemlich eindeutig und in Ordnung.
Du müsstest nur die Prioritäten der Operatoren festlegen, um zu wissen, wann man klammern muss und wann nicht. Aktuell verstehe ich es so, dass ',' enger bindet als '|', womit dann die Klammerung bei `("0", A) | ("1", A)` eher unnötig ist.