Ist eine deterministisch-endlicher Automat (DFA) ein LR(0)-Parser?

Hallo an alle Wissenden in diesem Forum,

mal eine Frage zum Thema Automatentheorie und Parsing.
Wenn ich einen Regulären Ausdruck habe: [0-9]+
Ist dieser dann nicht äquivalent zu der Grammatik:
s$: integer;
integer: DIGIT integer | DIGIT ;
(wobei DIGIT natürlich wieder 0-9 ist)?

Und der daraus resultierende LR(0) Parser (hier die Kernelkonfigurationen):

*STATE 0
s -> .integer

STATE 1
s -> integer .

STATE 2
integer -> "DIGIT" .integer
integer -> "DIGIT" .

STATE 3
integer -> "DIGIT" integer .*

Ist diese Maschine bereits eine äquivalenten DFA zum regulären Ausdruck, oder muß man immer den Weg über die NFA gehen? Oder hab ich generell einen Denkfehler in the Brain?

Danke,
Herr_Fragemann

Korbinian

Ein LR(0) ist immer ein DFA wenn ich mich nicht irre...

Korbinian schrieb:

Ein LR(0) ist immer ein DFA wenn ich mich nicht irre...

Hmm was ich nicht ganz kapiere (oder ich seh den Wald vor lauter Bäumen nicht!): Einen aus einer LR(1) Grammatik erzeugten DFA (ist es denn einer?) kann ich mit einem Kellerautomaten ausführen (wäre ja eine Grammatik vom Typ-2).
Aber bei einem DFA, mit dem ich einen regulären Ausdruck, der in einen DFA umgewandelt wurde, brauche ich doch keinen Kellerautomaten (PDA), sondern nur einen einfachen, endlichen Automaten (FSM). Allerdings würden doch LR(0) states auch reduziert werden, was wiederum auf einem Stack passiert?!

Oder wird durch meine o.g. LR(0) Grammatik, da sie Typ-3 ist, gar kein PDA benötigt?

Danke,
Herr_Fragemann *verwirrt*

Apollon

Ich habe jetzt nichts, ausser deiner letzten Frage verstanden. Daher beantworte ich nur diese: deine oben genannte Grammatik benoetigt keinen PDA. Ansonsten: wenn Du Woerter einer Grammatik mit einem DFA/NFA erkennen kannst oder mit einer Reg-Exp beschreiben, dann ist es eine Typ-3 Sprache.

EDIT: anders gesagt sind DFAs, NFAs und Reg-Exp gleichmaechtig.

Apollon schrieb:

EDIT: anders gesagt sind DFAs, NFAs und Reg-Exp gleichmaechtig.

Danke Apollon. Aber ein LALR(1)-Parser ist doch auch ein deterministisch Endlicher Automat, oder nicht? Oder bezeichnet man die Parse-Tabellen, die den Automaten formen, schon als PDA? Hmm eigentlich schon. Also ist eine LR(0) Parser auch ein PDA, und kein DFA?

Ich glaub ich sehe den Wald so langsam...

virtuell Realisticer

Nabend,

Herr_Fragemann schrieb:

Apollon schrieb:

EDIT: anders gesagt sind DFAs, NFAs und Reg-Exp gleichmaechtig.

Danke Apollon. Aber ein LALR(1)-Parser ist doch auch ein deterministisch Endlicher Automat, oder nicht? Oder bezeichnet man die Parse-Tabellen, die den Automaten formen, schon als PDA? Hmm eigentlich schon. Also ist eine LR(0) Parser auch ein PDA, und kein DFA?

Ich glaub ich sehe den Wald so langsam...

versuch dir folgende Frage zu beantworten:

Kann ein DFA sich etwas "merken"?

gruss
v R

Korbinian

Vorsicht, der LR(1) braucht 1 lookahead! Das ist zwar immer noch ein deterministischer Automat (gegeben den Lookahead), aber nicht mehr der DFA der fuer jedes Eingabetoken einen definierten Zustand hat (den du aber meinst, der z.B,. LR(0) noch ist). aber mit formalen richtigen aussagen bin ich nicht so fit

Apollon

Herr_Fragemann schrieb:

Apollon schrieb:

EDIT: anders gesagt sind DFAs, NFAs und Reg-Exp gleichmaechtig.

Danke Apollon. Aber ein LALR(1)-Parser ist doch auch ein deterministisch Endlicher Automat, oder nicht?

Determinstisch schon, aber endlich? Bei euch in der Vorlesung gabs bestimmt die "Klammer-Sprache", oder?

Ich finde den Tipp on vR sehr zutreffend.

Ah! Danke mit vRs und Korbinians Antwort sind meine Fragen denke ich geklärt!

Ein Blick nach Wikipedia:

Kellerautomat:
Bei einem Kellerautomaten handelt es sich um einen endlichen Automaten, der um einen Kellerspeicher erweitert wurde.

Deterministisch Endlicher Automat:
Ein deterministischer endlicher Automat (DEA, engl.: DFA=deterministic finite automaton) ist ein endlicher Automat, der unter Eingabe eines Zeichens seines Eingabealphabetes (mögliche Eingaben) von einem Zustand, in dem er sich befindet, in einen eindeutig bestimmten Folgezustand wechselt.

Sagt doch aus, daß zwar beides endliche Automaten sind, wobei der für den Kellerautomat doch die Eigenschaft des Stacks (und stackbasierte Übergänge) und der DEA (DFA) keine Stackeigenschaft besitzt, jedoch beide Automaten endlich sind und deterministisch.

Hab ich also denke ich richtig verstanden?!

Grüße
Herr_Fragemann

virtuell Realisticer

Hallo,

du musst schaerfer zwischen deterministischen und nichtdeterministischen
Automaten unterscheiden. Bei einem PDA handelt es sich zwar um einen endlichen
Automaten, nicht jedoch um einen deterministischen.

Um einen solchen zu bezeichnen, muss man auch explizit von einem DPDA sprechen,
denn ein PDA kann durchaus im hoechstenmasse nichtdeterministisch sein, da
er auch spontane Transitionen besitzen kann.

gruss
v R

da ich das bis jetzt noch immer nicht kapiert habe: was hat ein nfa im computer verloren? ein prozesor rechnet (im allgemeinen) deterministisch. dh, nicht-determinismus kann man nie erreichen.
soweit ich mich erinnern kann, wird determinierend so definiert, dass das ergebnis nur von der eingabe und dem zustand abhängt und fix ist, sofern überhaupt ein ergebnis geliefert wird.

selbst ein parser muss deterministisch sein, da er weder epsilon-übergänge haben darf noch für bestimmte eingabezeichen und zustände undefiniert sein darf. wäre er das, würde er ja zb. eine segfault produzieren.

das problem könnte sein, dass, wie in vielen fällen, die theoretische informatik sich keine gedanken über die praxis macht und einen parser so definiert, dass er im falle eines eingabefehlers einen undefinierten zustand einnimmt, den es aber in der praxis nicht gibt.

noch eine aussage, deren wahrheitsgehalt mich interessiert:
automaten mit keller verhalten sich zu automaten ohne keller wie parser zu regular expressions. stimmt das? ich denke schon, da der keller rekursion ermöglicht, was regex nicht können und dadurch nicht gleichmächtig sind wie vollständige (zb. ebnf-)parser. dh. ein automat mit keller ist mächtiger als einer ohne. der grad an determinismus wird dabei nicht berührt.

besserwisser schrieb:

da ich das bis jetzt noch immer nicht kapiert habe: was hat ein nfa im computer verloren? ein prozesor rechnet (im allgemeinen) deterministisch. dh, nicht-determinismus kann man nie erreichen.

Naja schon, indem der Automat mit einer Menge an Zuständen arbeitet. Ein NFA kann man sich wie ein Konstrukt vorstellen, das aus Übergangszuständen und Weichenzuständen besteht. Ein Übergang wäre eine Transition von z.B. einem Buchstaben, eine Weiche wäre eine so genannte "Epsilon Transition", die wieder auf andere Übergangstransitions oder weitere Epsilon Transitions verweisen.

Darstellung wie im Bild:
http://www.mec.ac.in/resources/notes/notes/compiler/Module1/fa_files/image010.jpg

Über einen "Epsilon Closure" werden nun alle Zustände in einer Liste gesammelt, die zu einem Übergang führen. Wird der Übergang für ein Zeichen durchgeführt, ist dies ein Move, und auf das Ergebnis solch eines Moves muss wiederum ein Epsilon-Closure erfolgen, um alle Folgeübergänge zu finden.

Ergo ist ein nichtdeterministischer Automat im Computer sehr wohl anwendbar.

Gruß
Herr_Fragemann

die zusammenfassung aller zustände in einer epsilon hülle (so heißt das an meiner uni) ist ein teil des algorithmus zur erstellung eines dfa aus einem nfa. damit hat man am pc wiederum einen dfa.
am computer passiert nichts ohne grund, sodass es epsilon übergänge nicht geben kann. man fasst ereignisse, die in den folgezuständen der gesamten epsilon übergänge zu passieren haben, zu einem zustand zusammen. so seh ich das halt. ich lass mir gerne ein argument geben, bei dem ein computer nicht-deterministisch rechnet. (ausgeschlossen sind natürlich hardwarezufallsgeneratoren.)