Notizen

Vorlesungsmitschrift Automaten und Formale Sprachen

0 mal verkauft

Kurs
Automaten und Formale Sprachen

Hochschule
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.

[ Mehr anzeigen ]

vorschau 2 aus 12 Seiten

Zum Beispiel

Hochgeladen auf 26. januar 2024
Anzahl der Seiten 12
geschrieben in 2022/2023
Typ Notizen
Professor(en) Mike scherfner
Enthält Alle klassen

3,99 €

In den Einkaufswagen

Speichern

100% Zufriedenheitsgarantie
Sofort verfügbar nach Zahlung
Sowohl online als auch als PDF
Du bist an nichts gebunden

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

Alle Vorteile der Zusammenfassungen von Stuvia auf einen Blick:

Garantiert gute Qualität durch Reviews

Stuvia Verkäufer haben mehr als 700.000 Zusammenfassungen beurteilt. Deshalb weißt du dass du das beste Dokument kaufst.

Schnell und einfach kaufen

Man bezahlt schnell und einfach mit iDeal, Kreditkarte oder Stuvia-Kredit für die Zusammenfassungen. Man braucht keine Mitgliedschaft.

Konzentration auf den Kern der Sache

Deine Mitstudenten schreiben die Zusammenfassungen. Deshalb enthalten die Zusammenfassungen immer aktuelle, zuverlässige und up-to-date Informationen. Damit kommst du schnell zum Kern der Sache.

Häufig gestellte Fragen

Was bekomme ich, wenn ich dieses Dokument kaufe?

Du erhältst eine PDF-Datei, die sofort nach dem Kauf verfügbar ist. Das gekaufte Dokument ist jederzeit, überall und unbegrenzt über dein Profil zugänglich.

Zufriedenheitsgarantie: Wie funktioniert das?

Unsere Zufriedenheitsgarantie sorgt dafür, dass du immer eine Lernunterlage findest, die zu dir passt. Du füllst ein Formular aus und unser Kundendienstteam kümmert sich um den Rest.

Wem kaufe ich diese Zusammenfassung ab?

Stuvia ist ein Marktplatz, du kaufst dieses Dokument also nicht von uns, sondern vom Verkäufer StudentKarsten. Stuvia erleichtert die Zahlung an den Verkäufer.

Werde ich an ein Abonnement gebunden sein?

Nein, du kaufst diese Zusammenfassung nur für 3,99 €. Du bist nach deinem Kauf an nichts gebunden.

Kann man Stuvia trauen?

4.6 Sterne auf Google & Trustpilot (+1000 reviews)

45.681 Zusammenfassungen wurden in den letzten 30 Tagen verkauft

Gegründet 2010, seit 15 Jahren die erste Adresse für Zusammenfassungen

Starte mit dem Verkauf