Dfa

Wissenschaft Informatik
#1

Hallo, habe eine Frage bezüglich endlichen Automaten.
man soll ein DFA kreiren, der folgende Sprache akzeptiert:

1)die Teilchzeichenreihe 000 muss akzeptiert werden, Alphabet ist {0,1}

meine LSG ist: Zustände A, B, C, D…

A mit Eingabe 1 in A und mit 0 in B.
B mit Eingabe 0 in C und mit 1 in A.
C mit Eingabe 0 in D und mit 1 in A.
D bleibt mit 1 und 0 in D.

A ist Start und D ist finaler Zustand.

2.)Teilzeichenreihe 011 muss akzeptiert werden:

A mit Eingabe 1 in A und mit 0 in B
B mit 0 in B und mit 1 in C.
C mit 0 in B und mit 1 in D
D mit 0 und mit 1 in D.

Müsste eigentlich richtig sein…vielleicht kann das jmd bestätigen, danke:smile:.

#2

Hallo.

Müsste eigentlich richtig sein…vielleicht kann das jmd
bestätigen

Ja, die sehen richtig aus. Allerdings eine kleine Anmerkung: Soll die Eingabe akzeptiert werden, wenn die Zeichenketten irgendwo in der Eingabe vorkommen? Oder soll nur akzeptiert werden, wenn die Eingabe genau dem entspricht? Oder nur, wenn die Eingabe direkt am Anfang vorkommt?
Bei deiner Lösung würde ja nicht nur 011 akzeptiert, sondern auch 1011 und 01011, …, weil du bei einem falschen Zeichen ja wieder in Zustand A wechselst.
Und wenn noch mehr Zeichen hinter der gesuchten Zeichenkette folgen, fehlen da irgendwie die Zustandswechsel in Zustand D.

Sebastian.

#3

Hi, nein die beiden Sprachen waren Teilzeichenreihe, die irgendwo in dem Strang vorkommen müssen, weder notwendigerweise am Aanfang noch am Ende…daher müsste es dann ja stimmen, oder?

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#4

Wenn ich mich richtig erinnere, läuft der Automat, bis die Eingabe zu Ende ist. Dann müsste im Endzustand der Übergang zum selben Zustand hinzugefügt werden, der für alle möglichen Zeichen genommen wird.

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]