Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- Automatentheorie (http://www.informatikerboard.de/board/board.php?boardid=13)
----- Regulärer Ausdruck (http://www.informatikerboard.de/board/thread.php?threadid=1747)

Geschrieben von marie m am 14.12.2013 um 17:05:

  Regulärer Ausdruck

Hi! Ich hätte mal eine Frage... Ich muss ein DFA kreieren von Sprache von den regulären Ausdruck ({{a,b}*,(0,c)*})*.. Könnte ihr sagen welche Sprache das ist?


Geschrieben von Karlito am 15.12.2013 um 14:33:

 

Hallo,

Der Automat lässt sich in dem Fall einfach ablesen. Es gibt einen Startzustand, einen Zustand, für {a,b}* und einen Zustand für {c,0}*. Fehlen nur noch die entsprechenden Transitionen. S. Anhang.

Dieser Automat lässt sich weiter vereinfachen, so dass es nur noch einen Zustand gibt, der alle eingaben Akzeptiert.

Solltest Du noch Fragen dazu haben, kannst du sie gern hier stellen.

VG,

Karlito


Geschrieben von marie m am 15.12.2013 um 15:53:

 

Danke schon mal für deine Antwort!!! smile


Geschrieben von marie m am 15.12.2013 um 16:24:

 

Für den regulären Ausdruck b*{aa, aba, 0}(ab)* ist der Automat der folgende: (S. Anhang) ??


Geschrieben von Karlito am 15.12.2013 um 17:09:

 

Hallo Marie,

nein, ist er nicht, da du die Alternative {aa, aba, 0} nicht beachtest. Außerdem wäre dein Automat kein DFA, da nicht für alle Eingaben eine Transition von jedem Knoten aus exisitieren. Weiterhin ist der Startzustand nicht gekennzeichnet.

Edit: Erstelle zuerst einen NFA.

VG,

Karlito


Geschrieben von marie m am 15.12.2013 um 17:42:

 

Bedeutet die Alternative {aa, aba, 0} dass es jeweils auch nur aa, oder nur aba, oder nur 0 sein kann?


Geschrieben von Karlito am 15.12.2013 um 17:52:

 

Nicht "auch", sondern ausschließlich. Auf b* darf nur eins der drei Möglichkeiten (gleichzeitig) folgen (und muss sogar, da sonst der Finalzustand nicht erreicht wird).

VG,

Karlito


Geschrieben von marie m am 15.12.2013 um 18:13:

 

Ahaa.. Ich habe es nochmal versucht.. (S. Anhang) Ist es jetzt richtig?


Geschrieben von Karlito am 15.12.2013 um 18:47:

 

Hallo Marie,

bis auf die Tatsache, dass der Startzustand noch nicht gekennzeichnet ist, ist der Automat korrekt. Daumen hoch

Eine optimierung könnte man noch einbauen: der zweite Finalzustand ist nicht notwendig. Eine Kante zurück zum ersten Finalzustand mit der Eingabe "b" wäre ausreichend.

Noch zwei Anmerkungen:
- Es ist kein DFA
- Normalerweise sollte man den Zuständen noch Namen geben. (War dir hier sicher nur zu aufwändig)

VG,

Karlito


Geschrieben von marie m am 28.12.2013 um 00:54:

 

Danke für deine Hilfe!!! Daumen hoch


Forensoftware: Burning Board, entwickelt von WoltLab GmbH