Informatik (Fach) / Automaten und Sprachen (Lektion)

info halt

Diese Lektion wurde von fiadora erstellt.

Lektion lernen

Diese Lektion ist leider nicht zum lernen freigegeben.

zurück  |  weiter 1 / 1

• Was versteht man unter Berechenbarkeit? 1. Welche Probleme können von einem Computersystem uberhaupt berechnet werden? ¨2. Welche Eigenschaften muss ein Computer besitzen, der alle lösbaren Probleme berechnen kann?
• Wie definiert man Berechenbarkeit? intuitive Vorstellung --> mit Stift und Papier lösbar Turing-Berechenbarkeit: kann von einer Turing-Maschiene berechnet werden Algorithmische Ansätze:  die Berechenbarkeit eines Problems wird durch programmtechnische Strukturen(loop, while und goto) definiert.
• Was besagt die Church-Turing These? Die drei Begriffe der Berechenbarkeit sind äquivalent.⇒ Fur jedes intuitiv berechenbare Problem gibt es eine Turingmaschine, die dieses berechnet. ¨⇒ Jede Turingmaschine stellt ein berechenbares Problem dar.
• Was bedeutet handhabbar? große Eingabewerte müssen in vertretbarer Zeit gelöst werden können Algorithmen mit polynomialer Laufzeit sind handhabbar. Algorithmen mit exponentieller Laufzeit sind nicht handhabbar
• Wie wird eine formale Sprache definiert? • Man wählt eine Menge von Zeichen als Alphabet.• Durch Aneinanderhängen von Buchstaben aus dem Alphabet werden Wörter gebildet.• Eine Teilmenge aus der gesamten Wortmenge definiert eine formale Sprache.
• Was ist Entscheidbar, semi-entscheidbar und nicht entscheidbar? • Entscheidbar: Es gibt einen Algorithmus, der das Wortproblem fur alle Wörter berechnen kann.• Semi-Entscheidbar: Es gibt einen Algorithmus, der das Wortproblem nur fur die Wörter der          Sprache berechnen kann.• Nicht Entscheibar: Das Wortproblem kann weder fur die Sprache noch für die                                Komplementmenge berechnet werden.
• Was ist ein Automat? Ein Automat ist ein Akzeptor fur eine formale Sprache. Er erh ¨ ¨alt als Eingabeein Wort und pruft, ob das Wort zur Sprache geh ¨ ¨ort oder nicht.
• Was ist eine Grammatik? Grammatiken erzeugen Sprachen. Sie definieren Produktionsregeln, aus denendie W¨orter der Sprache gebildet werden. Hierbei werden schrittweiseVariablen mit Hilfe der Regeln durch Buchstaben ersetzt.
• Was ist Äquivalenz? ⇒ Zu jeder Sprachklasse gibt es Grammatiktypen, die die Sprachen der Klasse erzeugen.⇒ Zu jeder Sprachklasse gibt es Automatentypen, die die Sprachen der Klasse akzeptieren.
• Was ist ein Alphabet? Eine nichtleere endliche Menge Σ := {a1, a2, . . . , ak} von Buchstaben
• Was sind Wörter? Eine geordnete, endliche Folge von Zeichen wi aus einem Alphabet Σ:w = w1w2 . . . wnDas leere Wort wird mit (epsilon) bezeichnet.
• Sind w, y zwei Wörter über dem Alphabet Σ, dann heißt y (Präfix, Infix und Suffix) • Präfix von w, wenn gilt w = yz fur ein Wort z.• Infix von w, wenn gilt w = xyz fur zwei Wörter x, z.• Suffix von w, wenn gilt w = xy fur ein Wort  x.
• Was ist eine Konkatenation? die Operation · bezeichnet die Verkettung zweier W¨orter v und w v · w = (v1v2 . . . vm) · (w1w2 . . . wn) = v1v2 . . . vmw1w2 . . . wn
• Was sind Potenzen? w(hoch n) bezeichnet die n-fache Konkatenation von w mit sich selbst. w(hoch n) =w · w . . . w (n-mal)
• Was ist das inverse Wort? w(hoch R) besteht aus den Buchstaben von w in der umgekehrten Reihenfolge. w(hoch R) = (w1w2 . . . wn)(hoch R) = wn wn−1 . . . w1.
• Was ist die Kleenesche Hülle? L* besteht aus allen Wörtern, die durch eine endliche Konkatenation von Wörternaus L entstehen.
• Was ist eine Grammatik? Tupel G = (Σ, N, P, S)
• Was bedeutet der Tupel Tupel G = (Σ, N, P, S)? • einem Alphabet Σ.• einer Menge N von Variablen mit N ∩ Σ = ∅.• einer Menge P von Produktionsregeln l → r mit l ∈ (Σ ∪ N)* \ Σ*und r ∈ (Σ ∪ N)*.• einer Startvariablen S ∈ N.
• Was macht das Automatenmodell der regulären Sprachen/endliche Automaten aus? • Eingabeband: Einseitig unbeschr¨anktes Band mit einem Lesekopf.Auf dem Band ist das Eingabewort gespeichert.• Zustandsspeicher S: Ein Register, in dem der aktuelle Zustandgespeichert wird. Der Automat kann lesend und schreibend aufden Zustandsspeicher zugreifen.• Ubergangsfunktion ¨ δ: Berechnet aus dem aktuellen Zustandswertund dem Eingabezeichen einen Folgezustand.
• Was ist ein deterministischer Automat? Fur jede Kombination aus Zustandswert und Eingabezeichen gibt es ¨maximal einen Folgezustand.
• Was ist ein nicht deterministischer Automat? Fur einen Zustandswert und ein Eingabezeichen gibt es mehrere ¨Folgezust¨ande aus denen der Automat frei ausw¨ahlen darf.
• Wie ist der Tupel A = (Σ, S, δ, s0, F) für einen deterministischen endlichen Automaten definiert? • Σ ein Eingabealphabet.• S eine endliche Menge von Zust¨anden.• δ : S × Σ −→ S eine partielle Funktion der Zustandsubergänge.• s0 ∈ S der Startzustand.• F ⊆ S die Menge der Endzust¨ande.
• Was ist eine erweiterte Übergangsfunktion? berechnet den Zustand, den der Automat erreicht, wenn er imZustand s startet und das Wort w einliest
• Wann sind zwei Automaten äquivalent? wenn sie die gleiche Sprache besitzen L(A) = L(A')
• Was ist eine reguläre Sprache? Sprache die von einem DEA akzeptiert wird
• Was ist ein Vollständiger Automat? Ein Automat mit einer totalen Ubergangsfunktion heißt vollständiger Automat. Für die Simulationvon Automaten mit Computerprogrammen werden oft vollst¨andige Automaten benöötigt.
• Was sind nutzlose Zustände? Zust¨ande, die vom Startzustand nicht erreicht werden, sind nutzlos und k¨onnen entfernt werden.
• Was sind äquivalente Zustände? Zwei Zust¨ande s und s'sind äquivalent, falls der Automat ein Wort w beginnend in s genau dannakzeptiert, wenn er es beginnend in s' akzeptiert, δ*(s, w) ∈ F ⇔ δ*(s', w) ∈ F
• Was ist der Markierungsalgorithmus? Der Markierungsalgorithmus bestimmt äquivalente Zustandspaare eines endlichen Automaten.
• Wie ist die Vorgehensweise beim Markierungsalgorithmus? 1. Bilde eine Tabelle aller Zustandspaare (s, t) mit s != t und markiere alle Paare (s, t) mit einemEndzustand und einem Nicht-Endzustand.2. Teste fur jedes nicht markierte Zustandspaar ( s, t) und jedes Zeichen a ∈ Σ, ob die Folgezustände (s', t') = (δ(s, a), δ(t, a)) markiert sind. Falls ja, dann wird das Paar (s, t) markiert.3. Wiederhole Schritt 2, bis es keine Anderungen mehr gibt. ¨4. Nicht markierte Zustandspaare (s, t) sind äquivalent und werden zusammengefasst.
• Was besagt das Pumping Lemma? Zu einer regulären Sprache L gibt es eine Zahl n ∈ N, so dass jedes Wort w der Länge |w| ≥ n zerlegt werden kann in w = xyz mit: (i) |y| > 0.(ii) |xy| ≤ n. so dass fur alle Zahlen k ∈ N0 gilt: xykz = x yy . . . yz ∈ L
• Wie wird das Pumping Lemma angewendet? Das Pumping-Lemma ist nur eine notwendige Bedingung fur reguläre Sprachen. Man kann mit dem Pumping-Lemma daher nur prufen, ob eine Sprache nicht regul ¨ ¨ar ist.
• Was sind nicht-deterministische Zustandsübergänge? Die Konstruktion wird einfacher, wenn wir nicht-deterministische Zustandsubergänge zulassen. Der Automat hat jetzt beim Einlesen eines Zeichens zwei oder mehrere Möglichkeiten fur einen Zustandsubergang und wählt nicht-deterministisch einen der m¨oglichen Folgezustände
• Was ist ein epsilon-Übergang? der Automat kann seinen Zustand wechseln, ohne dass er ein Eingabezeichen liest
• Was ist die epsilon-Hülle? ist die Menge aller Zustände, die der Automat ohne Einlesen einesZeichens a ∈ Σ erreichen kann
• Was meint man mit der Äquivalenz von DEA und NEA? Zu jedem NEA gibt es einen äquivalenten DEA
• Was ist ein regulärer Ausdruck? • Reguläre Ausdrücke sind Muster zur Beschreibung von regulären Sprachen.• Ein regulärer Ausdruck wird induktiv mit Hilfe von drei Operationen (Konkatenation, Selektionund Wiederholung) gebildet.
• Was sind elementare RA? Jedes Zeichen a ∈ Σ, sowie epsilon und ∅ sind RA und definieren die Sprachen L(a) = {a}; L(epsilon) = {epsilon}; L(∅) = {}
• Was ist mit: Reguläre Ausdrücke und endliche Automaten sind äquivalent, gemient? Zu jedem endlichen Automaten A gibt es einen RA R mit L(R) = L(A).Zu jedem RA R gibt es einen endlichen Automaten A mit L(A) = L(R).
• Wie wandelt man einen Automaten um? Erstelle einen äquivalenten Automaten A' mit genau einem Endzustand Entferne schrittweise alle Zustände bis auf s0 und sf und ersetze die Beschriftungen durch RA Bestimme aus dem reduzierten Automaten den RA R = ((R00)*R0f (Rff )* Rf0)*(R00)*R0f (Rff )*.
• Was meint man mit der Abgeschlossenheit von regulären Sprachen? Sind L und M zwei regul¨are Sprachen uber dem Alphabet Σ, dann gilt: ¨a) Vereinigung: L ∪ M ist regulär.b) Durchschnitt: L ∩ M ist regulär.c) Komplement: L = Σ* \ L ist regulär.d) Differenz: L \ M ist regulär.e) Konkatenation: L ◦ M ist regulär.f) Kleenesche Hulle: L* ist regulär.g) Die Sprachen Σ und Σ*  sind regulär. Für Teilmengen von regulären Sprachen lassen sich keine Aussagen machen: a) Ist L regulär mit L ⊂ M, dann folgt nicht zwingend, dass auch M regulär ist.b) Ist M regulär mit L ⊂ M, dann folgt nicht zwingend, dass auch L regulär ist
• Was ist eine Typ-3-Grammatik? Zu den Typ-3-Grammatiken gehören die rechts- und linkslinearen Grammatiken. Bei diesen Grammatiken wird in jedem Ableitungsschritt rechts bzw. links ein Terminalzeichen angehängt.
• Was ist eine lineare Grammatik? Eine lineare Grammatiken besitzt Produktionsregeln der Form A → r mit A ∈ N mit(i) r = z mit z ∈ Σ.(ii) r = zB oder r = Bz mit B ∈ N und z ∈ Σ.(iii) r = epsilon.Lineare Grammatiken sind nicht äquivalent zu den Typ-3 Grammatiken und definieren daher eine größere Sprachklasse

zurück  |  weiter 1 / 1