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)
--- NEA Automat (http://www.informatikerboard.de/board/thread.php?threadid=165)
Geschrieben von Gisa am 20.03.2007 um 23:18:
NEA Automat
Hallo Forum,
hier meine Aufgabe:
Ich habe folgenden NEA Automat konstruiert:
{w|w enthält den Substring 110 oder endet mit 01} Das Alphabet der Sprache ist Sigma = {0,1}
So sieht es aus.
Ist es so richtig?
Grüße
Gisa
Geschrieben von Tobias am 21.03.2007 um 00:16:
Der obere Zweig mit dem Substring 110 schaut gut aus. Beim unteren Zweig stört mich, dass man im Endzustand noch beliebig 0en und 1en einlesen kann. So ist z.B. auch das Wort 0111111....1 möglich, was weder 110 enthält, noch auf 01 endet.
Geschrieben von Gisa am 21.03.2007 um 00:25:
Ok.
Muss ich mir mal anschauen morgen.
Danke für dein Tip.
Grüße
Gisa
Geschrieben von Gisa am 21.03.2007 um 09:00:
So ich habe mal darüber nachgedacht.
Wenn es heisst endet mit 01 dann darf der linke akzptierte Zustand keine Schleife bekommen.
Also:
Danke und Grüße
Gisa
Geschrieben von Tobias am 21.03.2007 um 12:10:
Ja genau, so ist es schonmal richtig. Allerdings kannst du die beiden Epsilon-Transitionen und die Zustände q0 und q5 noch rausschmeißen, indem du q1 als Startzustand nimmst und von q1 eine 0-Transition zu q6 machst.
Geschrieben von Gisa am 21.03.2007 um 13:58:
Stimmt.
Danke dir Tobias :-).
Viele Grüße
Gisa
Geschrieben von Gisa am 22.03.2007 um 18:08:
Hallo Tobias,
hier habe ich noch einen NEA:
{w|w enthält den Substring 111 oder höchstens zweimal die 1}
Meine Lösung dazu:
Ist es denn korrekt?
Grüße
Gisa
Geschrieben von Tobias am 22.03.2007 um 20:43:
Ich machs kurz: 110110
Geschrieben von Gisa am 22.03.2007 um 20:58:
ich glaube dass muss ich mit epsilon lösen
---
Jetzt hab ich es mit epsilon gelöst
Geschrieben von Tobias am 23.03.2007 um 11:46:
Geschrieben von Gisa am 23.03.2007 um 16:34:
RE: NEA Automat
Danke Tobias.
Gruß
Gisa
Forensoftware: Burning Board, entwickelt von WoltLab GmbH
