Informatiker Board | Druckvorschau: Automat zur Sprache

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)
----- Automat zur Sprache (http://www.informatikerboard.de/board/thread.php?threadid=3806)

Geschrieben von Theo_Info_12 am 03.12.2017 um 15:00:

Automat zur Sprache

Ich habe eine Verständnis Frage zum Thema Sprachen und Automaten. Also eine Sprache besteht aus Wörtern, für die Wörter gilt jetzt mal, dass sie nur aus einer eins und zwei nullen bestehen, das bedeutet ja, die Wörter 001, 010 und 100 sind akzeptierend für eine State Maschine.

Wenn ich diese Maschine jetzt konstruieren möchte habe ich mir überlegt:

q0 -> 1 -> q1 -> 0 -> q2 -> 0 -> q3 (akzeptierend)
q0 -> 0 -> q4 -> 1 -> q2 -> 0 -> q3 (akzeptierend)
q0 -> 0 -> q4 -> 0 -> q5 -> 1 -> q2 (akzeptierend)

Anfangszustand ist dann q0, ich habe dann alle Fälle abgehakt, ist das soweit richtig?
Sowas wie 00001 kann und darf dann ja nicht auftreten...

Danke schon mal im voraus!

Geschrieben von NixJava am 03.12.2017 um 20:04:

Du hast ein Alphabet $[latex]\Sigma = \{0,1\}[/latex]$ und eine Sprache $[latex]L = \{100, 010, 001\} \subseteq \Sigma^*[/latex]$

Zitat:

Sowas wie 00001 kann und darf dann ja nicht auftreten...

Das verstehe ich nicht. Dein Automat muss mit allen Wörtern aus $[latex]\{0,1\}^*[/latex]$ umgehen können.

Weil du [latex]q_2[/latex]

als akzeptierenden Zustand definiert hast, würde dein Automat auch die Wörter 10 und 01 akzeptieren.

Geschrieben von Theo_Info_12 am 03.12.2017 um 21:33:

Ja, aber nur die Wörter 100, 010 und 001 dürfen in einen finalen Zustand übergehen.

Kleine Korrektur:
q0 -> 1 -> q1 -> 0 -> q2 -> 0 -> q3 (akzeptierend)
q0 -> 0 -> q4 -> 1 -> q2 -> 0 -> q3 (akzeptierend)
q0 -> 0 -> q4 -> 0 -> q5 -> 1 -> q3 (akzeptierend)

Ist das richtig?

Weil ich eigentlich sowas aussagen möchte, lehne alle anderen Wörter außer 100,010 und 001 ab...

Geschrieben von NixJava am 03.12.2017 um 22:02:

Gut, das sind jetzt die drei akzeptierenden Pfade. Was passiert, wenn z.B. as Wort 0010 eingegeben wird? Du brauchst noch einen nicht-akzeptierenden "Müll"-Zustand, in dem man bei allen weiteren Eingaben verharrt, wenn $[latex]w \not\in L[/latex]$ .

Geschrieben von Karlito am 04.12.2017 um 07:55:

Hallo NixJava und Theo_Info_12,

es gibt verschiedene Definitionen für endliche Automaten. In manchen Definitionen ist gegeben, dass alle nicht angegebenen Transitionen in den "Müll-Zustand" gehen. Bei NEAs ist es mir zum Beispiel nicht bekannt, dass sowas geforder ist und bei DEAs wird das manchmal einfach angenommen. Das kommt ein wenig auf den Dozenten an. Im Allgemeinen halte ich es bei DEAs auch für sinnvoll einen solchen Zustand anzugeben, da man dann schön kontrollieren kann, ob es auch von jedem Zustand aus für jedes Zeichen des Eingabealphabets auch einen Übergang gibt.

Besten Gruß,

Karlito

Geschrieben von Theo_Info_12 am 04.12.2017 um 07:55:

D.h. von meinem Endzustand aus (q3) müsste ich dann eine weitere Kante und einen Zustand hinzufügen, auf den dann 0 oder 1 eingetragen wird. richtig?

Geschrieben von Karlito am 04.12.2017 um 08:11:

Nein. Von jedem Zustand müsste eine Kante abgehen, sobald eine Eingabe erfolgt, die nicht akzeptiert wird.

Geschrieben von Karlito am 04.12.2017 um 08:21:

Sieht dann aus wie im Anhang.

Geschrieben von Theo_Info_12 am 04.12.2017 um 13:49:

Zitat:

Original von Karlito
Nein. Von jedem Zustand müsste eine Kante abgehen, sobald eine Eingabe erfolgt, die nicht akzeptiert wird.

Stimmt ist Logisch! Danke!

@Karlito, wie hast du das Bild erzeugt, erinnert mich etwas an R?

Geschrieben von Karlito am 04.12.2017 um 14:19:

graphviz -> dot

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:

digraph G {
	graph [layout=dot rankdir=LR]
	node [shape=none] qs [label=""]
	node [shape=doublecircle] q3
	node [shape=circle] 

	qs -> q0
	q0 -> q1 [label="1"]
	q1 -> q2 [label="0"]
	q2 -> q3 [label="0"]
	q0 -> q4 [label="0"]
	q4 -> q2 [label="1"]
	q4 -> q5 [label="0"]
	q5 -> q3 [label="1"]

	q1 -> qm [label="1"]
	q2 -> qm [label="1"]
	q3 -> qm [label="1"]
	q3 -> qm [label="0"]
	q5 -> qm [label="0"]
	qm -> qm [label="0"]
	qm -> qm [label="1"]

}

Beste Grüße,

Karlito