Automatentheorie

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.