Tut 2 Flashcards
Basisoperationen
Klammer > Interation > Produkt > Summe
Was ist der Unterschied zwischen einem deterministischen und einem nichtdeterministischen endlichen Automaten?
- Deterministisch: von jedem Zustand für jedes Eingabesymbol genau ein Folgezustand
- Nichtdeterministisch: von jedem Zustand pro Eingabesymbol eine endliche Menge an Folgezustände (kann auch leer sein)
- Ein deterministischer Automat ist ein Spezialfall eines nichtdeterministischen Automaten
Überführung n-det EA in det EA (NEA -> DEA)
Regulärer Ausdruck
- aus NEA ablesbar
- (Wege zum Endzustand) (alle Zyklen, die vom Endzustand wieder zum Endzustand gehen itieriert)^*
Aufwand für das “Wortproblem” - ist ein Worte element einer Sprache für Wort element E?
beide linear:
- DEA: O(|w|)
- NEA: O(|S| |w|)
Reguläre Sprache
Reguläre Sprachen können von endlichen Automaten erkannt werden und von regulären Ausdrücken beschrieben werden.
Kellerautomat
- 𝐾𝐴 = (𝐸, 𝑆, 𝐾, 𝛿, 𝑠0, 𝑘0, 𝑠𝑒 )
- 3-Tupel = Konfiguration
- LIFO
- gibt Info, ob Wort akzeptiert wird
- wenn leere Wort akzeptiert wird s0 = Endzustand
NKA
- gleich wie bei DKA außer Zustandsübergangsfunktion
- Dieses führt zu einem Endzustand, wenn das Wort ein Teilwort enthält, das zu einem Endzustand führt.
- Lambda-Übergang von s0 aus möglich
Satz - Sprachklassen
< = Teilmenge! immer L_*(E)
DEA < NEA < DKA < NKA < Menge aller Sprachen
Beispiel Umkehrpunkt Palindrome
Spracherkennungsaufwand KA
DKA: linear
NKA: Backtracking mit O(n3) möglich
Übergangsrelation
Umformen in CNF
- Mache G lambdafrei
- Eliminiere reine Umbenennungen (A -> B; ersetzen durch Produktionen)
- Forme P um, sodass jede rechte Seite entweder nur ein Terminalsymbol oder beliebig viel Nonterminalsymbole enthält
- Forme P um, sodass rechts maximal 2 Nonterminalsymbole stehen.
GNF
erlaubt nur Regeln:
N x TN*
jede rechtslineare lambdafreie Grammatik = GNF
