Automatensprache < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:48 Mo 19.12.2011 | | Autor: | emulb |
| Aufgabe | 1. Zeichnen Sie ein Zustandsdiagramm für den endlichen Automaten
M = ({z0, z1, z2}, {0, 1}, [mm] \delta [/mm] , z0, {z1, z2})
mit der Zustandsübergangsfunktion :
[mm] \delta(z0, [/mm] 0) = z2, [mm] \delta(z0, [/mm] 1) = z1, [mm] \delta(z1, [/mm] 0) = z0, [mm] \delta(z1, [/mm] 1) = z1, [mm] \delta(z2, [/mm] 0) = z2, [mm] \delta(z2, [/mm] 1) = z1.
L sei die Sprache, die dieser Automat akzeptiert.
2. Geben Sie für jedes der folgenden 5Wörter an, ob es von dem Automaten akzeptiert
wird oder nicht: 01100; 11110; 001100; 010101; 01010. |
zu 1)
also
z0 mit 1 auf z1
z1 mit 1 auf z1
z1 mit 0 auf z0
z0 mit 0 auf z2
z2 mit 0 auf z2
z2 mit 1 auf z1
zu 2) sagen wir start ist bei z0:
01100 geht
11110 geht nicht
001100 geht
010101 geht nicht
01010 geht nicht
spielt es dann eine rolle dass ich bei z0 anfange und bei z2 fertig bin kann ich mir den endpunkt aussuchen??
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:03 Di 20.12.2011 | | Autor: | sandp |
Hey,
Lies dir zuersteinmal die Definition deines Tupels durch, damit du weißt wo du anfängst und wo du endest.
Hab leider gerade keine zeit für eine längere antwort.
Gruss sandp
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 02:19 Sa 24.12.2011 | | Autor: | incubi |
1) stimmt mit den Zustandsübergangsfunktionen überein
2) Es werden alle Wörter akzeptiert, die nicht auf 10 enden. Somit geht auch 010101
Bei deterministischen endlichen Automaten beginnst du im Startzustand. Den Endzustand "aussuchen" kann man nicht, da dieser durch das Eingabewort eindeutig bestimmt wird. Der Automat liest einen Buchstaben, wechselt in den Folgezustand, liest den nächsten Buchstaben, wechselt in den Folgezustand usw - so lange bis kein Input mehr folgt (Wort wurde komplett eingelesen). Befindet sich nun der Automat in einem Endzustand, wird das Wort akzeptiert, andernfalls wird es abgelehnt.
Beispielsweise Eingabewort : 010101
Startzustand : z0
(z0,0)->z2 , verbleibendes Wort : 10101
(z2,1)->z1 , verbleibendes Wort : 0101
(z1,0)->z0 , verbleibendes Wort : 101
(z0,0)->z2 , verbleibendes Wort : 01
(z2,0)->z2 , verbleibendes Wort : 1
(z2,1)->z1 , fertig
Zustand = z1 , z1 ist ein Endzustand -> Wort wird akzeptiert
|
|
|
|
