Automatentheorie

Was ich zunächst für trivial erachtet habe, bereitet mir nun ungemeine Probleme,
kann mir jemand so einfach wie möglich erklären wie ich allgemein aus einer regulären Grammatik einen äquivalenten nicht-deterministischen Automaten erzeugen kann?
Bei der Erklärung möge bitte auf ausschweifende Theorie verzichtet werden, mit dem Algorithmus in Schönings Theoretische Informatik - kurz gefasst komme ich leider nicht zurecht,
die einfachen Beispiele die wir hatten helfen mir leider nicht weiter da diese zu einfach sind (die würde ich durch raten zusammenbekommen)

Ein guter Link ist natürlich auch willkommen

Danke im Voraus

naja, wie sieht eine Ableitung in einer regulären Grammatik typischerweise aus ?

S -> x_1 S_1 -> x_1 x_2 S_2 -> ... -> x_1 x_2 ... x_{n-1} S_{n-1} -> x_1 x_2 ... x_2

in jedem Schritt kommt nur ein Nichtterminal S_i vor, das kann man also als Zustand auffassen.

Die Zustandsfolge obiger Ableitung wäre also:

S -> S_1 -> S_2 -> ... -> S_{n-1}

Der NFA soll auf diesem Weg die Eingabe x_1 ... x_n verbrauchen, was liegt also näher als
die folgende Pfeilbeschriftung:

S --x_1--> S_1 --x_2--> S_2 --x_3--> ... --x_{n-1}--> S_{n-1}

Damit das Wort akzeptiert wird, muß ein Übergang in den akzeptierenden Endzustand
stattfinden: Dazu nehmen wir einen Extra-Zustand X dazu und fügen für jede
Regel

N --> t

einen Pfeil von N nach X hinzu, der mit t beschriftet ist.

Es entsteht so folgender Weg durch den Automaten:

S --x_1--> S_1 --x_2--> S_2 --x_3--> ... --x_{n-1}--> S_{n-1} --x_n--> X

- der Automat verbraucht dabei x_1 x_2 ... x_n und landet im Endzustand X. Voila.

Daß man für die Regel S --> epsilon einen Pfeil S --> X vorsehen muß usw
macht man sich leicht klar.

Nun nennt man S den Startzustand, X den Endzustand (bzw {S, X}, falls ein Pfeil S --> X),
die Terminale der Grammatik werden zu den Pfeilbeschriftungen, und der so konstruierte
Automat läuft genau die Ableitung im Beispiel oben ab, wobei sein aktueller Zustand
das jeweils auftretende Nichtterminal S_i ist.

oder in 1 Satz: das im Ableitungsschritt vorkommende einzige Nichtterminal faßt man als aktuellen Zustand eines Automaten auf, mit folgender Korrespondenz:

A --- t ----> B  für  A --> t B
A --- t ----> X  für  A --> t

(X = Endzustand des Automaten)

oder in 1 Satz: das im Ableitungsschritt vorkommende einzige Nichtterminal faßt man als aktuellen Zustand eines Automaten auf, mit folgender Korrespondenz:

Code:
A --- t ----> B für A --> t B
A --- t ----> X für A --> t
Code:
A --- t ----> B für A --> t B
A --- t ----> X für A --> t

(X = Endzustand des Automaten)

wahnsinn, das hätte ich mir in meinen kühnsten träumen zu hoffen nicht gewagt.
kurz, präzise, verständlich
die beste antwort die ich bisher in diesem forum bekommen habe
danke

gibt es eine ähnliche Möglichkeit
um Keller-automaten zu kreieren?

entweder aus der Sprache oder aus der Grammatik heraus?

SG1

nochmal dazu schrieb:

gibt es eine ähnliche Möglichkeit
um Keller-automaten zu kreieren?

entweder aus der Sprache

Wie meinst Du das? Irgendwie muss die Sprache ja gegeben sein.

oder aus der Grammatik heraus?

Ja. Idee: Der Kellerautomat führt eine Linksableitung eines Wortes durch. Treten dabei Nonterminale am Anfang der Satzform auf werden diese ausgegeben (da diese sich ja nicht mehr ändern können), der Rest der Satzform landet auf dem Keller. Dadurch hat man immer das als nächstes zu bearbeitende Nonterminal oben auf dem Keller.

das geht ähnlich: es reicht ein Kellerautomat mit 1 Zustand z.

Prinzip: man kann in einer gegebenen CFG jedes (überhaupt ableitbare)
Wort ableiten, indem man stets das am weitesten links stehende Nichtterminal
ersetzt.

Daher reicht ein Stack (Zugriff auf den TOS = top of stack) zur Simulation
aus.

Das aktuell abgeleitete Wort wird dabei in den Zellen des Stacks gespeichert.

Stackalphabet (SA) = { Terminale und Nichtterminale der CFG }
Eingabealphabet (EA) = { Terminale der CFG }

Anfangs liegt nur S auf dem Stack

Fall 1.

TOS = N (Nichtterminal N), und es gebe in der CFG eine Ableitung

N --> a_1 ... a_m (alle a_i aus SA)

=> ersetze spontan (dh. ohne ein Zeichen des Eingabeworts zu verbrauchen!)
den TOS N durch a_1 ... a_m (Stack wächst um m-1 Elemente)

Fall 2.

TOS = t (Terminal t) und aktuelles Eingabezeichen = t

=> verbrauche t aus der Eingabe und POPpe t

Ein Wort wird akzeptiert, wenn der Stack leer und die Eingabe verbraucht ist.

In 1 Satz:

der Kellerautomat bildet auf seinem Stack Linksableitungen der CFG nach,
indem

1. Ableitungen N -> a_1 ... a_m (N=Nichtterminal, a_i beliebig)

ohne Verbrauch von Eingabezeichen stattfinden

2. falls TOS = t *und* nächstes Eingabezeichen = t (t = Terminal)

das Zeichen t aus der Eingabe und vom Stack entfernt wird; akzeptiert wird dann,
wenn Stack = leer und Eingabe = verbraucht.

Wichtig hierbei, daß man in einer CFG jedes Wort durch Linksableitung ableiten
kann, und daß man deshalb nur Zugriff auf den TOS braucht. Deshalb reicht
ein *Stack* zur Simulation aus.

ich versuche grad folgende aufgabe die ich gefunden habe zu lösen:

geben sie einen echt-nichtdeterministischen Automaten an der den regulären Ausdruck

{101}{110}

akzeptiert.

Ich habe mir da etwas einfallen lassen, bin mir aber nicht sicher obs stimmt:

Zustände : S,A,B,V
Endzustände: S
S -1-> V
V -0-> A
V -1-> B
A -1-> S
B -0-> S

ich bin mir aber nicht sicher als wie allwissend ich einen nea einschätzen darf.
akzeptiert dieser nea jetzt das was ich eigentlich möchte oder vielmehr

{101 | 110}

?

weils mir wichtig ist

Bashar

Was will der Künstler uns mit der Notation {...} sagen?

o, tut mir leid, bei uns an der uni ist das der standard

{e} bedeutet dass beliebig viele (auch null) mal e kommen kann, also e^n , n>=0

| steht für alternierung, also (a|b) bedeutet entweder ein a oder ein b

{a|b} ist demnach eine beliebig lange kette aus a und b beispielsweise abbabbaabab

was also die frage ist:

weiß der automat, was ich will dass er erkennen soll, oder versucht er auf jeden fall zu erkennen?

zB erkannt werden soll:
101 101 110

aber nicht:

101 110 101

.......
ich weiß also nicht ob ich meinen nea etwas zu "mächtig" gestaltet habe und das was er erkennen soll nur eine teilmenge von dem ist was meiner erkennt

Bashar

shisha schrieb:

{e} bedeutet dass beliebig viele (auch null) mal e kommen kann, also e^n , n>=0

Ah gut, wie in der EBNF (da hätte man eigentlich auch drauf kommen können), also das was anderswo als e* geschrieben wird.

Dein Automat erkennt -- unter der Voraussetzung, dass man S als Endzustand deklariert -- {101|110}, außerdem ist er deterministisch. Einen NEA für {101}{110} (ohne epsilon-Übergänge) würde ich so bauen:

Zustände A,B,C,D,E,F, Endzustände sind A und D, Anfangszustand A
Eingabealphabet: {0,1}
Übergänge:

A -1-> B
A -1-> E
B -0-> C
C -1-> A
C -1-> D
D -1-> E
E -1-> F
F -0-> D

so, ich habe 2 weitere kleine probleme:

Betrachten Sie folgende Sprache L f(; ); [; ]g, wobei L aus der Menge der korrekten Klammerausdr
ucken besteht.

), ( ) ( ), ( ) [ ], ( ( ) ).

Dagegen sind folgende Worter beispielsweise nicht in L: ) (, ( (, ( ], ( [ ) ].

diese aufgabe habe ich im internet gefunden.

(2 Punkte) Geben Sie eine kontextfreie Grammatik G an, die L erzeugt.

Ich wäre jetzt folgendermaßen vorgegangen:

Einen Kellerautomaten aufstellen.

Das stellt kaum ein Problem dar, nur wie bekomme ich die Grammatik heraus, die in meinem Zustandsdiagramm steckt?

(2 Punkte) Zeigen Sie, dass das Wort ( [ ) ] nicht in L(G) enthalten ist

wie zeigt man sowas?

wäre folgendes eine geeignete kontextsensitve Gramatik:

S -> ()   | []   | {}
     (S)  | [S]  | {S}
     (S)S | [S]S | {S}S

?

wenn ich mich nicht irre, dürfte das jede mögliche korrekte klammerung ermöglichen.

stopp:

es fehlt noch:

()S | []S | {}S

C++ Forumbot

Dieser Thread wurde von Moderator/in rüdiger aus dem Forum Themen rund um den PC in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

geht einfacher:

$\footnotesize$ S\rightarrow \varepsilon\ |\ SS\ |\ (S)\ |\ [S]\ |\ {S}$$

sog. Dyck-3-Sprache.

([)] ist deshalb nicht drin, weil der Inhalt '...' von (...) irgendwie aus S hervorgegangen sein müßte und S ->* [ nicht möglich ist, wegen der Wort-Invariante: #linke Klammern = #rechte Klammern.

ist das überhaupt noch kontextfrei?

wegen der epsilon regel

|a| <= |b|

haben wir unter kontextfrei stehen, epsilonregln sind dann später dazugenommen worden...

aber jetzt rein definitionsgemäß?

SG1

Das hängt ja wohl ganz von der Definition ab.