Vorlesungsmitschrift Automaten und Formale Sprachen
8 views 0 purchase
Course
Automaten und Formale Sprachen
Institution
Hochschule Anhalt
Hier findest du die Mitschrift der Vorlesung Automaten und Formale Sprachen aus dem Sommersemester 22 bei Prof. Dr. Mike Scherfner. Es werden die Relevanten Inhalte der Vorlesung für die mündliche Prüfung definiert und zusammengefasst.
● 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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller StudentKarsten. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $4.33. You're not tied to anything after your purchase.
