Automat zur Sprache

03.12.2017, 15:00

Theo_Info_12

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!

03.12.2017, 20:04

Auf diesen Beitrag antworten »

NixJava

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.

03.12.2017, 21:33

Auf diesen Beitrag antworten »

Theo_Info_12

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...

03.12.2017, 22:02

Auf diesen Beitrag antworten »

NixJava

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]$ .

04.12.2017, 07:55

Auf diesen Beitrag antworten »

Karlito

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

04.12.2017, 07:55

Auf diesen Beitrag antworten »

Theo_Info_12

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?

04.12.2017, 08:11

Auf diesen Beitrag antworten »

Karlito

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

04.12.2017, 08:21

Auf diesen Beitrag antworten »

Karlito

Sieht dann aus wie im Anhang.

04.12.2017, 13:49

Auf diesen Beitrag antworten »

Theo_Info_12

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?

04.12.2017, 14:19

Auf diesen Beitrag antworten »

Karlito

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

Neue Frage »

Antworten »

Automat zur Sprache

Verwandte Themen