Class notes

Vorlesungsmitschrift Automaten und Formale Sprachen

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.

[Show more]

Preview 2 out of 12 pages

View example

Uploaded on January 26, 2024
Number of pages 12
Written in 2022/2023
Type Class notes
Professor(s) Mike scherfner
Contains All classes

theoretische informatik
automaten
formale sprachen
turingmaschine
kellerautomaten
äquivalenzrelation
moore automat
mealy automat
nichtdeterminismus
grammatiken

Institution
Hochschule Anhalt
Education
Angewandte Informatik
Course
Automaten und Formale Sprachen

$4.44

Add to cart

Save

100% satisfaction guarantee
Immediately available after payment
Both online and in PDF
No strings attached

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

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.44. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

66184 documents were sold in the last 30 days

Founded in 2010, the go-to place to buy study notes for 15 years now

Start selling