Informatiker Board | Automatentheorie | Vollständigen endlichen Automat für regulären Ausdruck + Reguläre Grammatik erstellen

Informatiker Board » Themengebiete » Theoretische Informatik » Automatentheorie » Vollständigen endlichen Automat für regulären Ausdruck + Reguläre Grammatik erstellen

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Seiten (2): [1] 2 nächste »

Vollständigen endlichen Automat für regulären Ausdruck + Reguläre Grammatik erstellen

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

FHDresden4Life
unregistriert

Vollständigen endlichen Automat für regulären Ausdruck + Reguläre Grammatik erstellen

Zitatantwort auf diesen Beitrag erstellen

Meine Frage:
Guten Tag,

ich bräuchte dringend Hilfe!

Ich muss aus einem gegebenen regulären Ausdruck einen vollständigen
endlichen Automaten erstellen. Zudem soll eine reguläre Grammatik angegeben werden.

Der Ausdruck sieht folgendermaßen aus: ((abc)+d)|(ef*g?)

Ich bin um jeden Ratschlag dankbar!

Liebe Grüße

Meine Ideen:
Der reguläre Ausdruck ist recht simpel gestaltet. Mein Problem ist allerdings, dass mir vorallem die reguläre Grammatik Kopfzerbrechen bereitet und ich keinen konkreten Ansatz dafür finde.

07.01.2015 15:55

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Hallo FHDresden4Life,

konstruieren wir doch zuerst den Automaten. Der Einfachheit halber hier einen NEA (es lässt sich ja ein DEA daraus erstellen). Siehe Anhang. Aus diesem NEA kann man die Grammatik im Prinzip ablesen:

$[latex] \begin{array}{rl} S \rightarrow & Z_0 Z_0 \rightarrow & abcZ_0 | abcZ_3 Z_3 \rightarrow & deZ_5 | de Z_5 \rightarrow & f | fZ_6 | g Z_6 \rightarrow & f | fZ_6 | g \end{array} [/latex]$

Ich hoffe Du kannst es nachvollziehen und ich habe nicht irgendwelche Fehler gemacht.

Gruß,

Karlito

Karlito hat dieses Bild (verkleinerte Version) angehängt:

07.01.2015 18:01

Nehmen Sie Karlito in Ihre Freundesliste auf

FHDresden4Life
unregistriert

Guten Abend Karlito,

Vielen Dank für deine äußerst schnelle Antwort!
Deinen Ansatz kann ich nachvollziehen, verstehe jedoch nicht wieso Z1,2,4 und 7 nicht in der Grammatik auftauchen?

Freundliche Grüße!

07.01.2015 19:16

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Wenn man es ausführlich macht, können die Zustände mit in der Grammatik auftauchen. Ich habe quasi einen Schritt übersprungen und die Grammatik reduziert.

Z1 und Z2 sind nicht nötig, da man mit der eingabe abc direkt auf Z3 oder Z0 kommt.
Z4 ist nicht nötig, da man mit de direkt von Z3 auf Z5 kommt und
Z7 ist nicht nötig, da nach der eingabe g keine Folgeeingabe notwendig ist. Z7 ist terminierend und hat keinen Folgezustand. Man könnte alse alle Z7 durch epsilon ersetzen und somit würde
[latex]Z_5 -> gZ_7[/latex]

zu Z5 -> $[latex]Z_5 -> g\epsilon[/latex]$ und somit zu [latex]Z_5 -> g[/latex]

.

Klar?

Gruß,

Karlito

07.01.2015 19:31

FHDresden4Life
Grünschnabel

Dabei seit: 13.01.2015
Beiträge: 6

Zitat:

Original von Karlito
Hallo FHDresden4Life,

konstruieren wir doch zuerst den Automaten. Der Einfachheit halber hier einen NEA (es lässt sich ja ein DEA daraus erstellen). Siehe Anhang. Aus diesem NEA kann man die Grammatik im Prinzip ablesen:

$[latex] \begin{array}{rl} S \rightarrow & Z_0 Z_0 \rightarrow & abcZ_0 | abcZ_3 Z_3 \rightarrow & deZ_5 | de Z_5 \rightarrow & f | fZ_6 | g Z_6 \rightarrow & f | fZ_6 | g \end{array} [/latex]$

Ich hoffe Du kannst es nachvollziehen und ich habe nicht irgendwelche Fehler gemacht.

Gruß,

Karlito

Guten Tag Karlito, müsste der Automat nicht so aussehen?

Wie würde dann die Grammatik lauten? Stimmen die Zustandsbeschreibungen?

Edit: der Automat sollte jetzt ein DEA sein?!

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von FHDresden4Life: 18.01.2015 16:12.

13.01.2015 18:44

Nehmen Sie FHDresden4Life in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Ich prüfe das gleich. Ich habe die Alternative im regulären Ausdruck übersehen. Muss aber erst mal kurz einkaufen...

Gruß,

Karlito

13.01.2015 19:25

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Der Automat passt so. Die Grammatik läuft im prinzip genau so wie vorher. Einfach ablesen. Probier es doch mal bitte.

Gruß,

Karlito

13.01.2015 20:00

FHDresden4Life
Grünschnabel

Dabei seit: 13.01.2015
Beiträge: 6

Zitat:

Original von Karlito
Der Automat passt so. Die Grammatik läuft im prinzip genau so wie vorher. Einfach ablesen. Probier es doch mal bitte.

Gruß,

Karlito

Alles klar, ich mach mich ran.

Habe allerdings noch zwei andere Fragen.

Stimmt die Reihenfolge der Zustandsbezeichnungen? Also Z1 bis Z8 oder ist die Reihenfolge irrelevant?

Desweiteren soll dieser Automat vollständig sein, dh. er soll Fehlerbehandlungen enthalten... Davon hab ich absolut keinen Schimmer, hast du irgendwelche Ratschläge diesbezüglich?

13.01.2015 20:10

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Zitat:

Original von FHDresden4Life
Stimmt die Reihenfolge der Zustandsbezeichnungen? Also Z1 bis Z8 oder ist die Reihenfolge irrelevant?

Die Reihenfolge und Bezeichnung ist irrelevant. Verschiedene Zustände sollten nur verschiedene Namen haben.

Zitat:

Original von FHDresden4Life
Desweiteren soll dieser Automat vollständig sein, dh. er soll Fehlerbehandlungen enthalten... Davon hab ich absolut keinen Schimmer, hast du irgendwelche Ratschläge diesbezüglich?

Man führt dafür einen neuen Zustand ein, den so genannten Papierkorbzustand. Danach führt man für alle ungültigen Eingaben von allen Zuständen eine neue Kante zu diesem Papierkorbzustand ein. Weiterhin eine reflexive Kante vom Papierkorbzustand für alle möglichen Eingaben.

Gruß,

Karlito

13.01.2015 20:53

FHDresden4Life
Grünschnabel

Dabei seit: 13.01.2015
Beiträge: 6

Kann ich diesen Papierkorbzustand anhand meines Beispiels an jeder Stelle einabeuen? Oder gibt es bestimmte Kriterien?

13.01.2015 21:04

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Ja klar kannst Du den Papierkorbzustand in dein Beispiel einbauen. Laut der Definition die ich kenne ist, das was Du gezeichnet hast auch kein DEA. in einem DEA gibt es von jedem Zustand für jede Eingabe einen (eindeutigen) Übergang. Und da kommt der Papierkorbzustand ins Spiel.

13.01.2015 21:46

FHDresden4Life
Grünschnabel

Dabei seit: 13.01.2015
Beiträge: 6

Guten Abend,

also mein Automat wurde so abgenommen, war korrekt - Vielen Dank!

Ich musste allerdings feststellen, dass mit Regulärer Grammatik jene aus der Chomsky-Hierarchie (Stufe 3).

Ich habe dass mal stellenweise versucht anhand meines Automaten und kam zu folgendem Ergebnis:

S -> aT
T ->; b
T -> c
T -> dS
S -> eT
S -> eS
T -> epsilon
T -> f
T -> fS
T ->; gS

Ich weiß nicht ob das korrekt ist, hat jemand eine Idee?

Liebe Grüße

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von FHDresden4Life: 14.01.2015 18:54.

14.01.2015 18:53

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Hallo FHDresden4Life,

$[latex] \begin{array}{rll} S \rightarrow & aT & T \rightarrow & b & \text{ab als Wort in der Sprache enthalten} T \rightarrow & c & \text{kann nicht stimmen, da sonst ac als Wort in der Sprache wäre} T \rightarrow & dS & \text{adb wäre so ein Wort der Sprache} \cdots & & \end{array} [/latex]$

Edit: Schau Dir doch noch mal an wie ich die Grammatik erstellt habe, es ist wie gesagt eigentlich nur abzulesen...

Hier der Anfang:
$[latex] \begin{array}{rl} Z_0 \rightarrow & aZ_1 Z_0 \rightarrow & eZ_6 \cdots & \end{array} [/latex]$

Gruß,

Karlito

14.01.2015 19:10

FHDresden4Life
Grünschnabel

Dabei seit: 13.01.2015
Beiträge: 6

Zitat:

Original von Karlito
Hallo FHDresden4Life,

$[latex] \begin{array}{rll} S \rightarrow & aT & T \rightarrow & b & \text{ab als Wort in der Sprache enthalten} T \rightarrow & c & \text{kann nicht stimmen, da sonst ac als Wort in der Sprache wäre} T \rightarrow & dS & \text{adb wäre so ein Wort der Sprache} \cdots & & \end{array} [/latex]$

Edit: Schau Dir doch noch mal an wie ich die Grammatik erstellt habe, es ist wie gesagt eigentlich nur abzulesen...

Hier der Anfang:
$[latex] \begin{array}{rl} Z_0 \rightarrow & aZ_1 Z_0 \rightarrow & eZ_6 \cdots & \end{array} [/latex]$

Gruß,

Karlito

Okay, ich habe die Prozedur wohl verstanden.
Ich frage mich nur ob ich die Endzustände ebenfalls Kennzeichnen darf, wie ich es in meinem Beispiel via Epsilon getan habe.

Meine Fertige Grammatik ist im Anhang.

Gruß

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von FHDresden4Life: 18.01.2015 16:12.

14.01.2015 20:34

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Hallo FHDresden4Life,

das mit dem epsilon kann man so machen. Du hast aber noch ein kleines Fehlerchen in deiner Lösung. $[latex]Z_4\rightarrow cZ_2[/latex]$ muss zu $[latex]Z_4\rightarrow aZ_2[/latex]$ werden. Ist sicher nur ein Copy-Paste-Fehler...

Gruß,

Karlito

14.01.2015 22:20

Seiten (2): [1] 2 nächste »

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Automatentheorie » Vollständigen endlichen Automat für regulären Ausdruck + Reguläre Grammatik erstellen