deterministischen Automat (DFA) erzeugen

Neue Frage »

Auf diesen Beitrag antworten »
Spender deterministischen Automat (DFA) erzeugen

Gegeben sei die Sprache L = {a(bc)^nd|n>=0}

Der DFA sollte dann so aussehen:

--> a --> b<-->c (Schleife zw. b und c) --> d (mit 2 Kreisen als Terminalsymbol)

So weit richtig?


ES dankt
der Spender
 
Auf diesen Beitrag antworten »
HueHang

Jein, denn der Deterministische Automat muss für jede Eingabe einen Folgezustand haben, d.h. was passiert, wenn ich nachdem ich ein "a" eingelesen habe noch ein "a" lese.
Auf diesen Beitrag antworten »
Spender

es soll ja ein deterministische endlicher Automat erstellt werden.

Warum noch ein a? Die Sprache kann doch nur ein a bereitstellen?!

Bei 2a wäre das Wort eben kein Bestandteil der Sprache also keine Teilmenge.

Es dankt
der Spender
Auf diesen Beitrag antworten »
Karlito

Zitat:
Original von Spender
Warum noch ein a? Die Sprache kann doch nur ein a bereitstellen?!


Es kommt darauf an, wie bei euch DFA definiert sind. Lt. der Definition, welche ich kenne und auf welche sich sicher auch HueHang bezieht, ist vorgegeben dass es für jede Eingabe und jeden Zustand genau eine Transition geben muss. Für ungültige Eingaben führt man einen "Müllkorbzustand" ein, welcher nur Eingänge hat, kein Finalzustand ist und für alle weiteren Eingaben reflexiv auf sich selbst verweist.

D.h. es muss einen Zustand [latex]q_{Muelll}[/latex] geben, es sei denn, es ist in der Vorlesung definiert, dass alle nicht angegebenen Transitionen zu einem solchen Zustand führen.

VG,

Karlito
 
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »