Informatiker Board | formale Sprachen | deterministischen Automat (DFA) erzeugen

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » deterministischen Automat (DFA) erzeugen

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

deterministischen Automat (DFA) erzeugen

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Spender
Grünschnabel

Dabei seit: 19.07.2012
Beiträge: 4

deterministischen Automat (DFA) erzeugen

Zitatantwort auf diesen Beitrag erstellen

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

21.07.2012 13:26

Nehmen Sie Spender in Ihre Freundesliste auf

HueHang
unregistriert

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.

21.07.2012 13:35

Spender
Grünschnabel

Dabei seit: 19.07.2012
Beiträge: 4

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

21.07.2012 14:41

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Karlito: 21.07.2012 21:34.

21.07.2012 21:34

Nehmen Sie Karlito in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » deterministischen Automat (DFA) erzeugen