Formale Systeme (Fach) / Automaten (Lektion)

ok

Diese Lektion wurde von Sogn erstellt.

Lektion lernen

zurück  |  weiter 1 / 2

• Wodurch sind endliche Automaten gekennzeichnet? Endliche Automaten sind gekennzeichnet durch eine endlichen Anzahl an Zuständen und Übergängen zwischen diesen Zuständen, welche abhängig von Struktur und Wort sind.
• Woraus besteht ein Transitionssystem? Ein Transitionssystem ist von der Form A = (Q, Σ, I, ∆, F), wobei• Q eine Menge von Zuständen ist (nicht notwendigerweise endlich!),• Σ ein endliches Alphabet ist,• I ⊆ Q eine Menge von Anfangszuständen ist,• ∆ ⊆ Q × Σ × Q eine Übergangsrelation (Transitionsrelation) ist,• F ⊆ Q eine Menge von Endzuständen ist.
• Wann ist ein Transitionssystem ein NEA? Ein Transitionssystem A = (Q, Σ, I, ∆, F) nennt man nichtdeterministischer endlicherAutomat (NEA), wenn • |Q| < ∞ und• |I| = 1 .
• Was ist ein Pfad? Ein Pfad in einem Transitionssystem A ist eine Folgeπ = (p0, a1, p1)(p1, a2, p2). . .(pn−1, an, pn) mit (pi, ai+1, pi+1) ∈ ∆ für i = 0, . . . , n − 1. π ist ein Pfad von p nach q, wenn p = p0 und q = pn.Die Beschriftung des Pfades π ist das Wort β(π) := a1 . . . an.Die Länge des Pfades π ist n.Für n = 0 sprechen wir vom leeren Pfad, welcher die Beschriftung ε hat.
• Wann heisst eine Sprache erkennbar ? Wenn es einen NEA gibt mit L = L(A).
• Was ist ein NEA mit Wortübergängen und ein ε-NEA? Ein NEA mit Wortübergängen hat die Form A = (Q, Σ, q0, ∆, F), wobei Q, Σ, q0, F wiebeim NEA definiert sind und ∆ ⊆ Q×Σ∗ ×Q eine endliche Menge von Wortübergängenist. Ein ε-NEA ist ein NEA mit Wortübergängen, wobei für alle (q, w, q0) ∈ ∆ gilt: |w| ≤ 1(d.h. w ∈ Σ oder w = ε).
• Wann ist ein NEA ein DEA? Ein NEA A = (Q, Σ, q0, ∆, F) heißt deterministisch (DEA), falls es für alle q ∈ Q, a ∈ Σ genau ein q0 ∈ Q gibt mit (q, a, q0) ∈ ∆. Anstelle der Übergangsrelation ∆ verwenden wir dann die Übergangsfunktionδ : Q × Σ → Q
• Was besagt das Lemma von Rabin/Scott? Zu jedem NEA kann man effektiv einen äquivalenten DEA konstruieren.
• Beweis vom Lemma Rabin Scott! w ∈ L(A) gdw. ∃q ∈ F : q0w−→A qgdw. ∃q ∈ F : q ∈ δ({q0}, w) (?)gdw. δ({q0}, w) ∩ F 6= ∅gdw. δ({q0}, w) ∈ F0gdw. w ∈ L(A0)
• Wann sind zwei Automaten äquivalent? Wenn sie die gleiche Sprache akzeptieren.
• Was ist der Quotientenautomat? Der Quotientenautomat Ae = (Q, e Σ, qe0, δ, e Fe) zu A = (Q, Σ, q0, δ, F) ist definiert durch: • Qe := {qe | q ∈ Q}• δe(q, a e ) := δ^(q, a) • Fe := {qe | q ∈ F}
• Beweis, dass A äquivalent zum Quotientenautomat ist. w ∈ L(A) gdw. δ(q0, w) ∈ Fgdw. δ^(q0, w) ∈ Fegdw. δe(qe0, w) ∈ Fegdw. w ∈ L(Ae)
• Was ist der Index des Quotientenautomaten? Die Anzahl seiner Äquivalenzklassen.
• Satz von Nerode? Eine Sprache L ist erkennbar gdw. 'L hat endlichen Index (d.h. endlich viele Klassen).
• Wie lautet das Pumping Lemma und wofür braucht man es? Es sei L eine erkennbare Sprache. Dann gibt es eine natürliche Zahl n0 ≥ 1, so dassgilt: Jedes Wort w ∈ L mit |w| ≥ n0 lässt sich zerlegen in w = xyz mit• y != ε• xy^kz ∈ L für alle k ≥ 0. Zum Beweis der Erkennbarkeit(oder Nichterkennbarkeit) einer Sprache.
• Wie lautet die verschärfte Version des Pumping Lemmas? Es sei L erkennbar. Dann gibt es eine natürliche Zahl n0 ≥ 1, so dass gilt:Für alle Wörter u, v, w mit uvw ∈ L und |v| ≥ n0 gibt es eine Zerlegung v = xyz mit• y != ε• uxy^kzw ∈ L für alle k ≥ 0
• Wie lauten die sechs Abschlusseigenschaften? Sind L1 und L2 erkennbar, so sind auch• L1 ∪ L2 (Vereinigung)• L1 (Komplement)• L1 ∩ L2 (Durchschnitt)• L1 \ L2 (Differenz)• L1 · L2 (Konkatenation)• L∗1(Kleene-Stern)
• Wie lauten die drei Entscheidungsprobleme? Leerheitsproblem, Wortproblem, Äquivalenzproblem
• Was ist ein regulärer Ausdruck? Eine weitere Beschreibungsmethode einer Sprache, neben Automaten.
• Wann ist eine Sprache erkennbar? (7) Eine Sprache L ⊆ Σ∗ist erkennbar gdw.(1) L = L(A) für einen NEA A.(2) L = L(A) für einen ε-NEA A.(3) L = L(A) für einen NEA mit Wortübergängen A.(4) L = L(A) für ein endliches Transitionssystem A.(5) L = L(A) für einen DEA A.(6) Die Nerode-Rechtskongruenz 'L hat endlichen Index. (7) Es gibt einen regulären Ausdruck
• Definition der regulären Sprache? Wann heisst eine Sprache regulär? Die durch den regulären Ausdruck r definierte Sprache L(r) ist induktiv definiert:• L(∅) := ∅, L(ε) := {ε}, L(a) := {a}• L(r + s) := L(r) ∪ L(s), L(r · s) := L(r) · L(s), L(r∗) := L(r)∗ Eine Sprache L ⊆ Σ∗ heißt regulär, falls es ein r ∈ RegΣ gibt mit L = L(r).
• Was besagt der Satz von Kleene? Für eine Sprache L ⊆ Σ∗sind äquivalent: 1) L ist regulär.2) L ist erkennbar.
• Wie lautet das Ardensche Lemma? Es seien A, B ⊆ Σ∗ und ε /∈ A. Die Gleichung (??) X = A · X ∪ B hat als eindeutige Lösung X = A∗· B.
• Wie lautet die Chomsky-Hierarchie? Grammatiken, Typen Es sei G = (N, Σ, P, S) eine Grammatik. • Jede Grammatik G heißt Grammatik vom Typ 0. • G heißt Grammatik vom Typ 1 (kontextsensitiv), falls jede Produktion von Gdie Form– u1Au2 −→ u1wu2 mit A ∈ N, u1, u2, w ∈ (Σ ∪ N)∗ und |w| ≥ 1 oder– S −→ ε hat.Ist S −→ ε ∈ P, so kommt S nicht auf der rechten Seite einer Produktion vor. • G heißt Grammatik vom Typ 2 (kontextfrei), falls jede Regel von G die FormA −→ w hat mit A ∈ N, w ∈ (Σ ∪ N)∗. • G heißt Grammatik vom Typ 3 (rechtslinear), falls jede Regel von G die FormA −→ uB oder A −→ u hat mit A, B ∈ N, u ∈ Σ∗.
• Definition Grammatik? Eine Grammatik ist von der Form G = (N, Σ, P, S), wobei • N und Σ endliche, disjunkte Alphabete sind. (Man bezeichnet die Symbole aus Nals Nichtterminalsymbole, die Symbole aus Σ als Terminalsymbole), • S ∈ N das Startsymbol ist, • P ⊆ (N ∪Σ)+ ×(N ∪Σ)∗eine endliche Menge von Ersetzungsregeln (Produktionen)
• Was lässt sich über Typ 3 - Sprachen aussagen? Die Typ-3-Sprachen sind genau die regulären/erkennbaren Sprachen, d.h.L3 = {L | L ist regulär}.
• Was ist die Chomsky-Normalform? Jede kontextfreie Grammatik lässt sich umformen in eine äquivalente Grammatik inChomsky-Normalform, d.h. eine Grammatik, die nur Regeln der folgenden Form hat: • A −→ a, A −→ BC mit A, B, C ∈ N, a ∈ Σ• und eventuell S −→ ε, wobei S nicht rechts vorkommt.
• Woraus besteht ein Kellerautomat? Ein Kellerautomat (pushdown automaton, kurz PDA) hat die FormA = (Q, Σ, Γ, q0, Z0, ∆, F), wobei • Q eine endliche Menge von Zuständen ist,• Σ das Eingabealphabet ist,• Γ das Kelleralphabet ist,• q0 ∈ Q der Anfangszustand ist,• Z0 ∈ Γ das Kellerstartsymbol ist,• ∆ ⊆ Q × (Σ ∪ {ε}) × Γ × Γ∗ × Q eine endliche Übergangsrelation ist
• Was ist eine Turingmaschine? Eine Turingmaschine über dem Eingabealphabet Σ hat die Form A = (Q, Σ, Γ, q0, ∆, F),wobei• Q endliche Zustandsmenge ist,• Σ das Eingabealphabet ist,• Γ das Arbeitsalphabet ist mit Σ ⊆ Γ, 6b ∈ Γ \ Σ,• q0 ∈ Q der Anfangszustand ist,• F ⊆ Q die Endzustandsmenge ist und• ∆ ⊆ Q × Γ × Γ × {r, l, n} × Q die Übergangsrelation ist
• Was sind die Eigenschaften von ~A? Äquivalenzrelation Verträglich mit Übergangsfunktion (siehe Lemma 2.9) Kann effektiv bestimmt werden
• Wie funktioniert das Reduzieren einer Grammatik? Alle nicht erreichbaren und nicht-terminierenden Symbole ermitteln und anschließend aus der Grammatik entfernen. Damit erhält man eine äquivalente reduzierte Grammatik Gx.
• Wie ermittelt man eine Epsilon-freie Grammatik? 1) Berechnung einer Grammatik , welche kein A-> ε produziert 2) Einführen einer neuen Startvariable (zB S3) 3) S3 zeigt nun auf ε und auf S. S3 darf nicht mehr rechts stehen. 4) Rest übernehmen
• Wie gibt man eine epsilon-freie Grammatik an? Erlaubt epsilon nur auf rechter seite, wenn das startsymbol auf epsilon zeigt und das startsymbol nie selbst auf der rechten seite steht Dazu führt man ein neues startsymbol ein, welches auf epsilon und zusätzlich auf das alte startsymbol zeigt
• Wie eliminiert man AB Produktionen? A zeigt direkt auf die Produktion von B und nimmt nicht den „Umweg“ über B
• Wie ermittelt man die Terminierenden Symbole einer Grammatik? 1) Alle Symbole (S, T, R..) betrachten, welche rechts nur ein Wort aus dem Alphabet haben 2) Alle Symbole betrachten, welche rechts nur ein Wort oder einen der vorher betrachteten Symbole (S,T,R...) rechts stehen haben 3) Solange wiederholen, bis kein neues mehr erreicht wird Nun hat man die Terminierenden. Um die Nicht-Terminierenden zu ermitteln, betrachtet man alle übrigen Symbole, welche nicht Terminierend sind.
• Wie ermitteln man alle erreichbaren Symbole? 1) Alle Symbole betrachten, die bei S auf der rechten Seite stehen (zB T, U) 2) Alle Symbole betrachten, welche nun neu ermitteln worden sind (T, U), und deren rechte Seite betrachten (zb V) 3) Solange wiederholen, bis kein neues Symbol mehr erreichbar wird.
• Wie bekommt man eine Grammatik ohne N -> ε? A 1) Alle Produktion der Form N -> ε löschen 2) Alle Produktionen, welche vorher auf ε gezeigt haben ersetzen durch den FolgeausdruckBsp. F -> ε        F -> aFb       wird zu:       F -> ab       F -> aFb
• Ermitteln einer Grammatik, welche nicht von Nicht-Terminal auf Nicht-Terminal (S -> T)zeigt? 1) Startsymbol betrachten und schauen ob und auf welches Symbol es abbildet (zb T) 2) T betrachten und schauen worauf es zeigt (zB aSb) 3) S zeigt nun direkt auf aSb 4) S -> T wird entfernt 5) Wiederhole solange bis kein Nicht-Terminal auf ein bloßes Nicht-Terminal zeigt.
• Konkrete Umformung in Chomsky Normalform? 1) Epsilonfreie Grammatik angeben 2) Terminal auf bloße Terminal Abbildungen entfernen 3) Jedes Terminal (a,b,c) durch Xa, Xb, Xc ersetzen 4) Alle Nichtterminalsymbole > 2 zu 2 zusammenfassen (C1, C2)
• Warum heißt Typ 1 kontextsensitiv und Typ 2 kontextfrei? kontextfrei: Die linke Seite jeder Produktion besteht nur aus einem Nichtterminalsymbol A, das daher stets unabhängig vom Kontext im Wort ersetzt werden kann. kontextsensitiv: uAu → uwu. Hier ist die Ersetzung von A durch w abhängig davon, dass der richtige Kontext (u1 links und u2 rechts) vorhanden ist. |w| ≥ 1 sorgt dafür, dass die Produktionen die Wörter nicht verkürzen (Ausnahme S −→ ε, die aber nur zur Erzeugung von ε dient).
• Beweis, dass das Komplement von L erkennbar ist! w ∈ L1 gdw. w /∈ L(A1) gdw. w !∈ L(A)gdw. δ(q0, w) !∈ Fgdw. δ(q0, w) ∈ Q \ Fgdw. w ∈ L(A)
• Beweis Abschluss unter Durchschnitt! Da L1 ∩ L2 dasselbe ist wie = /(/L1 ∪ /L2), folgt dies aus dem Komplement von L und der Vereinigung von L.
• Beweis , L ist erkennbar unter Abschluss Differenz! L1 \ L2 = L1 ∩ /L2. Folgt somit aus der Vereinigung und dem Komplement.
• Welche Form hat eine Konfiguartion beim PDA? Eine Konfiguration von A hat die Form K = (q, w, γ) ∈ Q × Σ∗ × Γ∗
• Wann ist ein Kellerautomat deterministisch? Der PDA A = (Q, Σ, Γ, q0, Z0, ∆) heißt deterministisch, falls die folgenden beiden Bedingungen erfüllt sind: 1) ∀q ∈ Q ∀a ∈ Σ ∪ {ε} ∀Z ∈ Γ existiert höchstens ein Übergang der Form(q, a, Z, . . . , . . .) ∈ ∆. 2) Existiert ein Tupel (q, ε, Z, . . . , . . .) ∈ ∆, so existiert kein Tupel der Form(q, a, Z, . . . , . . .) ∈ ∆ mit a ∈ Σ.
• Wann akzeptiert ein PDA ein Wort mit leerem Keller? A akzeptiert w mit leerem Keller, falls(q0, w, Z0) |-`∗(q, ε, ε) für ein beliebiges q ∈ Q. Die durch A mit leerem Keller akzeptierte Sprache istN(A) := {w ∈ Σ∗| A akzeptiert w mit leerem Keller}.
• Wann ist eine Sprache deterministisch kontextfrei? (PDA) Es sei L ⊆ Σ∗ kontextfrei und R ⊆ Σ∗regulär. Dann ist L ∩ R kontextfrei.
• Wann ist eine Sprache deterministisch kontextfrei? (PDA) Es sei L ⊆ Σ∗ kontextfrei und R ⊆ Σ∗regulär. Dann ist L ∩ R kontextfrei. Eine Sprache heißt deterministisch kontextfrei (dkf), falls sie von einem deterministischen Kellerautomaten (DPDA) akzeptiert wird.
• Wann akzeptiert eine Touringmaschine eine Sprache? Die Sprache L ⊆ Σ∗ heißt Turing-akzeptierbar, falls es eine NTM A gibt mit L = L(A).
• Welche Form hat eine k-Band-TM? Eine k-Band-NTM hat die Form A = (Q, Σ, Γ, q0, ∆, F) mit • Q, Σ, Γ, q0, F wie in Definition ?? und • ∆ ⊆ Q × Γ^k × Γ^k × {r, l, n}^k × Q.

zurück  |  weiter 1 / 2