Automaten und formale Sprachen
Grundlagen der theoretischen Informatik
Grundlagen der theoretischen Informatik
Was sind Automaten
technische oder mechanische Geräte, die bei einer Eingabe ein Ergebnis liefern
Beschreibe den Transitionsgraphen
Der Automat hat zwei Zustände q0 und q1.
q0 ist der Initialwert.
Wird eine 0 eingegeben, bleibt er in dem Zustand q0. Wird eine 1 eingegeben, wechselt er in den Zusatnd q1 und bleibt mit jeder weiteren 1 als eingabe in diesem Zustand.
Wird eine 0 eingegen wechelt er in den Zusatnd q0.
Endliche Automaten:
Für was steht Q
Eine endliche nichtleere Menge von Zuständen
Endliche Automaten:
Für was steht Σ?
Für eine endliche nicht leere Menge deren Inhalt das Eingabealphabet darstellt
Endliche Automaten: Für was steht q0
Startzustand des Automaten
Endliche Automaten: Für was steht F
Anzahl zugelassener Endzustände
F ist eine Teilmenge von Zuständen (Q)
Beschreibe das Diagramm
Es gibt 3 Zustände(q0,q1,q2), 2 Eingabe Möglichkeiten(0,1) und einen gültgen Endzustand(q2).
Es können zu Anfang beliebig viele 0er eingeben werden, der Automat bleibt in Zustand q1.
Wenn eine 1 eingegeben wird wechselt der Automat in den zustand q2. nach einer 1 können beliebig viele 1er eingegben werden. Der Automat bleibt in Zustand q2. Wird nach einer 1 eine 0 eingeben muss eine 0 oder eine 1 folgen. Der Automat wechelt in q1. q1 ist kein gültiger Endzustand, daher muß auf eine 0 eine weitere 0 folgen oder eine 1 um in den Endzustand q2 wieder zugelangen.
-
- 1 / 7
-
Flashcards
Was sind Automaten
technische oder mechanische Geräte, die bei einer Eingabe ein Ergebnis liefern
Beschreibe den Transitionsgraphen
Der Automat hat zwei Zustände q0 und q1.
q0 ist der Initialwert.
Wird eine 0 eingegeben, bleibt er in dem Zustand q0. Wird eine 1 eingegeben, wechselt er in den Zusatnd q1 und bleibt mit jeder weiteren 1 als eingabe in diesem Zustand.
Wird eine 0 eingegen wechelt er in den Zusatnd q0.
Endliche Automaten:
Für was steht Q
Eine endliche nichtleere Menge von Zuständen
Endliche Automaten:
Für was steht Σ?
Für eine endliche nicht leere Menge deren Inhalt das Eingabealphabet darstellt
Endliche Automaten: Für was steht q0
Startzustand des Automaten
Endliche Automaten: Für was steht F
Anzahl zugelassener Endzustände
F ist eine Teilmenge von Zuständen (Q)
Beschreibe das Diagramm
Es gibt 3 Zustände(q0,q1,q2), 2 Eingabe Möglichkeiten(0,1) und einen gültgen Endzustand(q2).
Es können zu Anfang beliebig viele 0er eingeben werden, der Automat bleibt in Zustand q1.
Wenn eine 1 eingegeben wird wechselt der Automat in den zustand q2. nach einer 1 können beliebig viele 1er eingegben werden. Der Automat bleibt in Zustand q2. Wird nach einer 1 eine 0 eingeben muss eine 0 oder eine 1 folgen. Der Automat wechelt in q1. q1 ist kein gültiger Endzustand, daher muß auf eine 0 eine weitere 0 folgen oder eine 1 um in den Endzustand q2 wieder zugelangen.
