 Automat zur Sprache |
Theo_Info_12
unregistriert
 |
|
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 15:00 |
|
|
NixJava
unregistriert
|
|
Du hast ein Alphabet ![[latex]\Sigma = \{0,1\}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\Sigma = \{0,1\}) und eine Sprache ![[latex]L = \{100, 010, 001\} \subseteq \Sigma^*[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L = \{100, 010, 001\} \subseteq \Sigma^*)
| 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]](http://www.matheboard.de/latex2png/latex2png.php?\{0,1\}^*) umgehen können.
Weil du ![[latex]q_2[/latex]](http://www.matheboard.de/latex2png/latex2png.php?q_2) als akzeptierenden Zustand definiert hast, würde dein Automat auch die Wörter 10 und 01 akzeptieren.
|
|
|
03.12.2017 20:04 |
|
|
Theo_Info_12
unregistriert
|
|
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 21:33 |
|
|
NixJava
unregistriert
|
|
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]](http://www.matheboard.de/latex2png/latex2png.php?w \not\in L) .
|
|
|
03.12.2017 22:02 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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 |
|
|
Theo_Info_12
unregistriert
|
|
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 07:55 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Nein. Von jedem Zustand müsste eine Kante abgehen, sobald eine Eingabe erfolgt, die nicht akzeptiert wird.
|
|
|
04.12.2017 08:11 |
|
|
Theo_Info_12
unregistriert
|
|
| 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 13:49 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
04.12.2017 14:19 |
|
|
|
