Automatentheorie
-
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-> Sich 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
-
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 110aber 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
-
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
-
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:
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äß?
-
Das hängt ja wohl ganz von der Definition ab.