Vorlesungsmitschrift Automaten und Formale Sprachen

Zusammenfassung Automaten und Formale Sprachen

Teilgebiete der Informatik

● Theoretische Informatik: mathematische Modelle von Computern und Hilfsmittel zu
ihrer präzisen Beschreibung
● Praktische Informatik: Prinzipien und Techniken der Informatik
● Angewandte Informatik: Verbindet Methoden mit Anwendungsproblemen
● Technische Informatik: physische Struktur und Aufbau von Computern


Formale Sprachen
● Definition: Ein Alphabet A = {a1 , … , an} ist eine nichtleere Menge von endlich vielen
Zeichen (auch Symbole genannt)
● Definition: Eine Folge x = x1…xn von n Zeichen heißt Wort (der Länge n ∈ ℕ). → x0
ist nicht definiert, daher Einführung des leeren Wortes

● Spezialfall: Wort aus null Zeichen → leeres Wort 𝞴 (ist immer Teil einer Sprache)

● Definition Sternhülle: Menge aller Wörter über einem Alphabet A

𝐴* = ⋃ An
𝑛>=0
wobei An = {x1…xn | n >= 0 und xi ∈ A für i = 1, … , n }Definition: Jede Teilmenge L ⊂
A* heißt Sprache über dem Alphabet A.
(die leere Menge ist auch eine Sprache, da sie Teilmenge jeder Menge ist!)


Deterministische Turingmaschine




● T = (E, B, S, so , 𝞭 )
○ E → Eingabealphabet, das alle Zeichen enthält, aus denen die Eingabe
bestehen kann
○ B → Bandalphabet, das alle Zeichen enthält, die auf dem Band stehen
können ( E ⊂ B , Stern für unbeschriebene Bandzellen , beliebige weitere
Zeichen
○ S → endliche Zustandsmenge mit s0 ∈ S
○ s0 → Startzustand
○ 𝞭 → Zustandsübergangsfunktion

, S x B → S x B x {R, L, N}
𝞭 (s, b) = (s’ , b’ , {R, L, N})

Lese/-Schreibkopf befindet sich in Zustand s und liest auf dem Band das
Zeichen b → s’ ist der Folgezustand, b’ überschreibt b auf dem Band,
LS-Kopf bewegt sich nach rechts/ links/ neutral

Ist (s, b) nicht definiert bleibt T stehen!
● löst RECHENprobleme (Verarbeitung der Eingabe liefert ein konkretes Ergebnis,
Bsp: Addition einer Binärzahl mit 1)


Turingmaschine (Akzeptor)
● T = (E, B, S, so , 𝞭 , F)
○ s.o.
○ F ⊆ S → Menge der akzeptierten Endzustände, Eingabe wird akzeptiert
wenn sie sich nach dem anhalten in einem dieser Zustände F befindet,
ansonsten wird die Eingabe nicht akzeptiert
● Definition Akzeptierte Sprache: L(T) ⊂ E* , Eingabe bei der T auf einem akzeptierten
Endzustand endet
● löst ENTSCHEIDUNGSprobleme (Eingabewort wird akzeptiert oder nicht akzeptiert,
bsp: prüfen ob eine Eingabe Teil der akzeptierten Sprache ist)

● Gleichbedeutende Aussagen:
○ T akzeptiert die Sprache L(T)
○ T löst das implizit durch L(T) definierte Entscheidungsproblem
○ Für w ∈ L(T) hält T nach endlich vielen Berechnungsschritten in einem
Endzustand, für w ∉ L(T) hält T nicht in einem Endzustand


Turingmaschine (Konfiguration)
● Gesamtzustand der TM = Konfiguration
○ besteht aus Zustand, Bandinschrift, Position
● durch die Konfiguration können die Rechenschritte der TM verfolgt werden

● Definition Konfiguration: man betrachte T = (E, B, S, so , 𝞭 , F) , die Konfiguration ist
durch den Tripel (v, s, w) ∈ B* x S x B* gegeben
○ s → aktueller Zustand
○ vw → aktuelle Bandinschrift

○ Startkonfiguration: (𝞴 , s0 , w)

● Kodierung der Bandinschrift als vw ermöglicht es, die Position des LS-Kopfes zu
speichern (w schließt das aktuelle Zeichen mit ein)


Übergangsrelation der Konfigurationen einer Turingmaschine
● Die Relation