42

Formale Syteme 2020 (Fach) / Automaten und Grammatiken (Lektion)

Diese Lektion wurde von Sogn erstellt.

Lektion lernen

Diese Lektion ist leider nicht zum lernen freigegeben.

zurück  |  weiter 1 / 1

• Ist jede erkennbare Sprache auch gleichzeitig kontextfrei ? Warum? Ja, da man für zu jeder Kontextfreien Grammatik einen Automaten angeben kann.
• Wie lauten die Abschlusseigenschaften für kontextfreie Sprachen? Die Vereinigung zweier Grammatiken ist abgeschlossen.Wir vereinigen erst zwei Grammatiken miteinander (Σ1 ∪ Σ2, N1 ∪ N2, ...).Wir führen ein neues Startsymbol ein, welches auf S1 aus Grammatik 1 und auf S2 aus Grammatik 2 zeigt. Somit lassen sich alle Symbole aus der jeweiligen Grammatik erreichen.Gleiches gilt für die Konkatenation.Kleene-Stern ist ebenfalls abgeschlossen.Dafür führen wir ebenfalls ein neues Startsymbol S ein, welches auf S1S zeigt. So lässt sich die Grammatik beliebig oft wiederholen. Hinzu kommt noch S-> ε, für n = 0.
• Warum ist eine Grammatik unter Komplement und Durchschnitt nicht abgeschlossen? 1) Die Sprachen {anbncm|n≥1,m≥1} ={anbn|n≥1}·{c}+und {ambncn|n≥1,m≥1}={a}+·{bncn|n≥1} sind in L2: • {anbn|n≥1} ∈ L2und {bncn|n≥1} ∈ L2 • {a}+ ∈ L3 ⊆ L2 und {c}+ ∈ L3⊆L2 • L2 ist unter Konkatenation abgeschlossen. Wäre L2 unter Komplement abgeschlossen, so auch unter ∩, da L2 unter ∪abgeschlossen ist. Widerspruch.
• Welche Werkzeuge gibt es um formale Sprachen zu definieren? DEAs(ε)- NEAsReguläre AusdrückeKontextfreie GrammatikKellerautomatenTuringmaschinen
• Wann akzeptiert ein Kellerautomat ein Wort? Über Endzustände oder leere Keller, beide sind gleichmächtig.
• Wie ist ein Kellerautomat aufgebaut? Ein nichtdeterministischer Kellerautomat besteht aus Q: endliche Menge von Zuständen Σ: Eingabealphabet Γ: Kelleralphabet δ: Übergangsrelation Q0: Anfangszustand Z0: Kellerstartsymbol F: Endzustände 
• Ist jede Teilmenge einer nicht-regulären Sprache ebenfalls nicht regulär? Nein, da stets gilt ∅ ist Teilmenge von L, aber ∅ ist regulär.
• Was besagt der Satz von Myhill/Nerode? Eine Sprache L ist erkennbar gdw. 'Lhat endlichen Index (d.h. endlich viele Klassen). Die Anzahl der Nerode-Äquivalenzklassen ist endlich gdw. die zugehörige Sprache regulär ist.
• Wie beweist man, dass eine Sprache kontextfrei ist? Durch angeben eines Kellerautomaten oder einer kontextfreien Grammatik. Der Gegenbeweis erlangt man durch das Pumping-Lemma für Grammatiken.Ebenfalls kann man die Abschlusseigenschaften für kontextfreie Grammatiken nutzen.
• Wie lautet die Chomsky-Hierarchie? Typ 0: allgemein (TM-Maschinen) Typ 1: kontextsensitiv (TM-Maschinen mit linearer Bandbeschränkung) Typ 2: kontextfrei (Kellerautomat, kontextfreie Grammatik) Typ 3: einseitig linear/erkennbar/regulär (endliche Automaten, reguläre Ausdrücke)
• Anzeige
• Wann ist ein Transitionssystem ein NEA? Wenn es lediglich einen Startzustand enthält und endlich ist.
• Wann ist ein NEA ein DEA? Ist ein NEA deterministisch, so nennt man ihn DEA. DEAS sind deterministisch, da sie nur in eine einzige Richtung funktionieren. Im Gegensatz zum NEA gibt es beim DEA einen Pfad für jedes Symbol, beginnend mit dem Anfangszustand. Bei DEAs braucht jedes Symbol eine Funktion je Zustand. Daher gibt es auch sogenannte Papierkorbzustände, welche nicht akzepierte Wörter ausscheiden.
• Wie lautet das Lemma von Rabin, Scott ? Zu jedem NEA kann man effektiv einen äquivalenten DEA konstruieren. Somit akzeptieren DEAs und NEAs diesselbe Klasse von Sprachen. Für die Umwandlung benötigt man die Potenzmengenkonstruktion.
• Was besagt der Satz von Kleene? Für eine Sprache L ⊆ Σ∗sind äquivalent: 1) L ist regulär.2) L ist erkennbar.
• 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
• Wie lautet das Pumping-Lemma? 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 das Ardensche Lemma? Es seien A, B ⊆ Σ∗ und ε /∈ A. Die Gleichung X1 = A · X ∪ B hat als eindeutige Lösung X = A∗· B.
• 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
• Unter welchen Eigenschaften bleiben Typ3 Sprachen abgeschlossen? •L1∪L2(Vereinigung) •L1(Komplement) •L1∩L2(Durchschnitt) •L1\L2(Differenz) •L1·L2(Konkatenation) •L∗(Kleene-Stern)
• Wie lauten die Rechenregeln bei regulären Ausdrücken? Um Klammern zu sparen, lassen wir Außenklammern weg und vereinbaren, •dass ∗ stärker bindet als · •dass · stärker bindet als + (oder) • · lassen wir meist ganz wegfallen
• Wie lautet die Semantik der regulären Ausdrücke? L(∅) :=∅,  L(ε) :={ε},  L(a) :={a} L(r+s) :=L(r)∪L(s),  L(r·s) :=L(r)·L(s),  L(r∗) :=L(r)∗
• Wie lautet das Pumping-Lemma für kontextfreie Sprachen? (Typ II) Es sei G eine kontextfreie Grammatik, die •ε-frei, •keine Regeln der FormA→B enthält, •m nichtterminale Symbole enthält, •nur rechte Regelseiten der Länge ≤k hat. Es sein=km+1.Dann gibt es für jedes z∈L(G) mit |z|> n eine Zerlegung z=uvwxy mit: •vx6=ε und |vwx|≤n, •uviwxiy∈L(G) für alle i≥0.
• Wie beweist man die Abschlusseigenschaft Vereinigung erkennbarer Sprachen? Man stelle sich zwei Automaten A und A' vor.Man baut sich einfach einen neuen Zustand vor die beiden Automaten und verbindet beide Automaten mit einem Epsilon-Übergang, also einen Epsilon-NEA.Somit akzeptiert der neue Automat die Sprach L1 v L2. -> L1 u L2 ist erkennbar
• Wie beweist man die Abschlusseigenschaft Komplement erkennbarer Sprachen? Umwandlung in einen DEA, Vertauschung von Anfangs- und Endzuständen
• Wie beweist man die Abschlusseigenschaft Differenz erkennbarer Sprachen? L1 ∩ L2 = ¬(¬L1 ∩ ¬L2)
• Wie beweist man die Abschlusseigenschaft Durchscnitt und Differenz erkennbarer Sprachen? Durchschnitt L1 ∩ L2 = ¬(¬L1 ∩ ¬L2) Differenz L1/L2 = L1 ∩ ¬L2
• Beweis Abschlusseigenschaft Konkatenation erkennbarer Sprachen? Will man zwei Sprachen konkatenieren, verbindet man einfach beide Sprachen mit Epsilon Übergängen. (Bzw. Die Automaten). Dabei bekommen alle Endzustände von L1 einen Epsilon-Übergang zu den Startknoten des L2. Reihenfolge beachten.
• Beweis Abschlusseigenschaft Kleene Stern von erkennbaren Sprachen? Neuer Zustand q0 (Endzustand) Epsilonübergang von q0 zum Automaten epsilonübergänge zurück vom Endzustand zu q0
• Woraus besteht ein Transitionssystem? Q Menge von Zuständen ∑ Alphabet I Anfangszustand Δ Übergangsrelation F Endzustand
• Warum heissen NEAs nicht deterministisch? Da es für ein Symbol sogar zwei(oder mehr) oder gar keine Pfade geben kann. Somit wird das Wort akzeptiert solange einer dieser Pfade einen Endzustand erreicht.
• Anzeige
• Was sind Nachteile der Potenzmengenkonstruktion? Die Zustandszahl wird exponentiell vergrößert Lösung : Minimierung der DEAs
• Warum konstruiert man einen Produktautomat? Da der Abschluss unter Komplement die Potenzmengenkonstruktion benötigt und diese exponentiell sein kann, weshalb man direkt einen NEA für zB. L1 ∩ L2 konstruiert.
• Wie ist der Produktautomat definiert? A = (Q1 x Q2, ∑, (q01, q02), Δ, F1 x F2 )
• Warum heißt Typ 2 kontextfrei und Typ 1 kontextsensitiv? Auf der linken Seite steht bei Typ nur ein Nichtterminalsymbol, weshalb jenes immer unabhängig vom Kontext ersetzt werden kann. Bei kontextsensitiv ist die Ersetzung von N und a abhängig vom Kontext (u1 links und u2 rechts).
• Wann heißt eine Grammatik reduziert? Wenn alle Elemente von N erreichbar und terminierend sind, somit sind alle Nicht-terminierenden und Nicht-erreichbaren entfernt.
• Wie erzeugt man eine reduzierte Grammatik? 1. Eliminieren Nicht-terminierender Symbole 2. Eliminieren unerreichbarer Symbole
• Wie lässt sich eine Epsilonfreie Grammatik erreichen? 1) Eliminieren alle A - > ε 2) Ersetzen aller vorher durch A - > ε terminierenden Regeln durch alle möglichen Terminierungen
• Wie lautet die Chomsky Normalform? Eine Grammatik, welche nur die Regeln A -> a A -> BC evtl. S -> ε, wobei S nicht rechts vorkommt akzeptiert.
• Wie erreicht man die Chomsky-Normalform? 1) ε-freie Grammatik erstellen 2) Kettenregeln entfernen 3) Für jedes Terminal a ein Xa einführen
• Wann ist ein Kellerautomat deterministisch? Wenn es für jede Konfiguartion nur eine Folgekonfiguartion gibt, d.h. es gibt nur Möglichkeit für eine Konfiguration.Man schaut ob es in einem Zustand mehrere Übergänge (auch auf sich selbst!) gibt, welche sowohl das selbe Symbol, als auch das selbe STACK Symbol lesen. Bsp. (qo, a, A, AA, q1) und (q0, a, A , ε, q2) ODER Man schaut bei Epsilonübergängen, ob dessen oberstes STACK Symbol dasselbe ist wie eines in einem Eingabesymbol. (Z0, ε) und (Z0, a) zB.
• Wann heisst eine Sprache deterministisch kontextfrei? Nur wenn sie von einem Deterministischen Kellerautomaten erkannt wird.
• Wie wandelt man einen ε-NEA in einen NEA um? Zustände anschauen, welche mit ε auf einen Zustand n zeigen -> alles übernehmen, was n auch kann Zustände anschauen, welche auf einen Zustand n zeigen, welcher dann mit ε auf einen zeigt -> Zustand n kann übersprungen werden

zurück  |  weiter 1 / 1