Flashcards
Endliche Automaten, reguläre Sprachen
Cards in this deck (20)
- 1Endlicher Automat (Konzept)Mathematisches Modell bzw. Abstraktion eines Automaten, der Information Zeichen für Zeichen einliest und das jeweils Gelesene sofort verarbeitet.
Endlicher Automat besitzt endliche Menge von Zuständen und keinerlei Zusatzspeicher. - 2Ablauf eines Arbeitsschritts Aktuelles Zeichen: x Aktueller Zustand: q1) Der Lesekopf liest x
2) Der Schreibkopf schreibt das nächste Zeichen y auf das Ausgabeband
3) Der Zustand wechselt von q nach q'
(evtl. ist q=q')
4) Das Eingabeband wird vorgerückt - 3Anfangszustand/EndzustandAnfangszustand:
- Zustand vor dem Einlesen des ersten Zeichens
Endzustand:
- Es wird kein Zeichen mehr eingelesen
- Seit dem Start verarbeitete Folge wird akzeptiert
- i.d.R. mehrere Endzustände - 4Endlicher Automat (Mathematisch)Ein 6-Tupel A = (I,O,Q,δ,q0,F) mit:
I: Input-Alphabet (endlich)
O: Output-Alphabet (endlich)
Q: Zustandsmenge (endlich)
δ: Übergangsfunktion
δ : Q × (I ∪ {ε}) → Q × (O ∪ {ε})
q0: Anfangszustand
F: Menge der Endzustände
(F ist Teilmenge von Q) - 5Transducer (übersetzender Automat)Berechnet zu einem Eingabewort ein Ausgabewort
(z.B.: Oktalzahl -> Binärzahl) - 6nicht-deterministischer AutomatFür einen Zustand q und ein Inputzeichen x sind mehrere Folgezustände q' möglich.
- 7erkennender AutomatVerwendet kein Ausgabeband sondern akzeptiert einfach Eingabewörter oder nicht.
- 8"akzeptiertes" EingabewortFalls der Automat nach Abarbeitung des Eingabebandes in einem Endzustand ist, so hat er das Eingabewort akzeptiert.
- 9Vergleich: nicht-deterministische vs. deterministische Automaten- Deterministischer Automat benötigt mehr Zustände
- Zu jedem nicht-deterministischen Automaten gibt es einen deterministischen Automaten, der die gleiche Sprache akzeptiert - 10AlphabetEine nicht-leere, endliche Menge von Zeichen.
- 11Reguläre AusdrückeKlasse RA der regulären Ausdrücke über Alphabet A ist definiert durch:
1) Ø є RA und a є RA für a є A
2) s,t є RA => (s|t), (st), (s*) є RA - 12Theorem von KleeneEine Sprache heisst genau dann regulär, wenn sie von einem regulären Ausdruck beschrieben wird.
- 13Eine Sprache wird von einem endlichen Automaten akzeptiert. Was kann man über die Sprache aussagen?Die Sprache ist regulär.
- 14AbschlusseigenschaftenSeien L und M reguläre Sprachen über A.
Dann sind auch
A* - L = {x є A* : nicht x є L} und L ∩ M
reguläre Sprachen. - 15GrammatikEine Grammatik ist ein 4-Tupel (N,T,S,P)
N: endliche Menge von non-terminal Symbolen
T: endliche Menge von terminal Symbolen
S є N: Startsymbol
P: endliche Menge von Produktionen - 16ProduktionEine Produktion hat die Form u→v wobei u,vє(N T)*
und u muss ein Symbol aus N enthalten.
Anmerkung: Es gibt mindestens eine Produktion in P mit u=S. - 17Herleitung
- 18Reguläre GrammatikEine Grammatik heisst regulär, falls alle Produktionen die folgende Form haben:
n → w
Wobei n ein non-terminal Symbol ist und w das leere Wort oder ein ein Wort mit höchstens einem non-terminal Zeichen ist, welches am Schluss stehen muss. - 19Zusammenhang: reguläre Sprache - reguläre Grammatik- Jede reguläre Grammatik erzeugt eine reguläre Sprache.
- Zu jeder regulären Sprache gibt es eine reguläre Grammatik, welche sie erzeugt. - 20ProblemstellungenSei L(G) eine Sprache, die von der Grammatik G erzeugt wird.
- Wortproblem: ist w in L(G) für ein gegebenes Wort w?
- Leerheitsproblem: Ist L(G) leer?
- Äquivalenzproblem: Ist L(G1) = L(G2) für zwei Grammatiken G1 und G2?
Information
- Description
- Endliche Automaten, reguläre Sprachen
- Created by
- Luca Rolshoven · Dec 2016
- Updated
- Jan 10, 2017
- Views
- 18
- Rating