CL-Blog

Computerlinguistik & Politik

Du durchsuchst gerade das Archiv der Kategorie ‘Formale Sprachen und Automaten’.

Kategorie: Formale Sprachen und Automaten

2017 7 Aug

FSA: Termin der Nachklausur

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Die Nachklausur findet am 12.9., 12:15 statt. Einen Raum gebe ich noch bekannt.

Ich denke, Sie müssen sich dazu anmelden. Bitte sagen Sie mir Bescheid, wenn es Komplikationen gibt.

2017 4 Aug

Musterlösung zur FSA-Klausur

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Hier finden Sie eine Musterlösung zur Klausur von Mittwoch.

Bitte sehen Sie sie sich genau an, um noch mal ein paar Dinge zu lernen.

Hier finden auch noch eine sehr ausführliche Darstellung des Beweises zu Aufgabe 5.

Die Klausur ist erschreckend schlecht ausgefallen (es gab aber zwei Einser), was mich um so mehr erstaunt, da

  • ich Aufgabe 1 bereits im Blogeintrag vom 8.6. thematisiert habe
  • Aufgabe 3 zweimal (ohne Auflösung) als Problem in der VL gestellt wurde
  • ich gesagt habe, dass Induktionsbeweise dran kommen. Wenn ich “Induktionsbeweis Beispiele” google, enthält gleich er erste Treffer den Beweis aus Aufgabe 5.

Bedenken Sie bitte, das CL ein formales Fach ist, welches hohe analytische und zunehmend auch mathematische Fähigkeiten erfordert. Zunächst einmal müssen Sie aber eine für die meisten neue Sprache lernen, die Sprache der Mathematik. Der FSA-Kurs ist dazu (nach MulG) ein Vorbereitungskurs, dann folgen “Computerlinguistische Techniken” und Aufbaumodule, wo das eine immer größere Rolle spielt. Ein weiterführender Master in CL ohne vertiefte Mathematikkenntnisse ist nicht machbar.

Zur Bedeutung der Mathematik in der Informatik lesen Sie bitte auch zwei Beiträge von den Kollegen der Informatik (ab. S.13)

Es hätte vielen von Ihnen übrigens gut getan, die Ü-Blätter zu machen. Diese helfen, die mathematische Ausdrucksweise zu erlernen. Das obligatorisch zu machen, gibt die Studienordnung nicht her, also blieben Markus und mir immer nur Appelle …

2017 26 Jul

FSA, 26.7./27.7.

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Thema: Turing-Maschinen

Materialien:

2017 23 Jul

FSA Übungsblatt #13

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Ein letztes Übungsblatt, u.a. zu Turingmaschinen & Pumpinglemma…

2017 21 Jul

FSA, 19./20.7.

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Typen von kontextsensitiven Grammatiken
  • Längenmonotonie => führt zur Entscheidbarkeit von kontextsensitiven Sprachen
  • Mild-kontextsensitive Sprachen
  • Turing-Maschinen: Definition, Konfiguration, Konfigurationsübergang
  • Platzmäßig eingeschränkte Turing-Maschinen: Linear-beschränkte Automaten als Automatenmodell für kontextsensitive Sprachen
  • Beispiel: TM für Kopiersprache:

    tm-kopiersprache.dot

Materialien:

 

 

 

2017 14 Jul

FSA Übungsblatt #12

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Übungsblatt 12 zu Chomsky-Normalform und CYK. Montag geht es wie gewohnt weiter. In Hinblick auf das demnächstige Semesterende werde ich im Tutorium auch Zeit lassen für Fragen zu älteren Themen, falls Bedarf da ist.

Ein gutes Wochenende!

2017 14 Jul

FSA, 12./13.7.

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

2017 10 Jul

FSA, 5./6.7.

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Chomsky-Normalform
  • Cocke-Younger-Kasami-Parsing
  • Catalan-Zahlen zur Beschreibung des maximalen Ambiguitätsgrads einer kontextfreien Sprache

Materialien

 

2017 6 Jul

FSA Übungsblatt #11

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

2017 29 Jun

FSA, 28.6.

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Thema: Typ2-Grammatik zu Kellerautomat

  • Der zu beweisende Satz: Für jede kontextfreie Grammatik G = (N, Σ, P, S) gibt es einen Kellerautomaten K mit N(K) = L(G)
  • N(K) = L(G) bedeutet: Alle Wörter, die von der Grammatik generiert werden, werden vom Automaten akzeptiert, und umgekehrt
  • Konstruktion von K:
    K = ({q}, Σ, N ∪ Σ, q, δ, S, ∅) mit

    1. Hypothesenbildung 1) (q, a) ∊ δ (q, ε, A) für jede Regel A -> a ∊ P
    2. Verifikation 2) δ (q, a, a) = {(q, ε)} für alle a ∊ Σ
  • Die Konstruktion wird im nachfolgenden Induktionsbeweis (über die Länge der Ableitung) verwendet:
    1a) A =>⁺ w   ==>  (q, w, A) |――* (q, ε, ε)
  • Es muss darüberhinaus auch noch die Rückrichtung 1b)  (q, w, A) |――* (q, ε, ε)  ==> A =>⁺ w gezeigt werden (durch Induktion über die Länge der Folge der Konfigurationsübergänge |――*
  • Ferner gilt es — um den obigen Satz zu beweisen — noch zu zeigen, dass das, was ein beliebig gewählter Kellerautomat (z.B. mit mehr als einem Zustand, mit Endzuständen, mit allg. Delta-Übergängen gemäß der Definition von Kellerautomat) akzeptiert, auch von einer zu findenden kf. Grammatik generiert werden kann. Der Beweis verwendet eine zweite Konstruktion und besteht wieder aus zwei Induktionsbeweisen für die Hin- und Rückrichtung
  • Schrittweise Beispieldarlegung der Gleichheit:

    S => NP VP => ART N VP => Das N VP => Das Mädchen VP => Das Mädchen schläft(q, Das Mädchen schläft, S) |―― (q, Das Mädchen schläft, NP VP) |―― (q, Das Mädchen schläft, ART N VP) |―― (q, Das Mädchen schläft, Das N VP) |―― (q, Mädchen schläft, N VP) |―― (q, Mädchen schläft, Mädchen VP) |―― (q, schläft, VP) |―― (q, schläft, schläft) |―― (q, ε, ε)

  • Man erkennt unschwer, dass die Anzahl der erfolgreichen Schritte des Automaten gleich der Anzahl der Schritte in der Grammatik sowie zusätzlich der Anzahl der Verifikationsschritte ist, d. h. der Länge von w, formal: A =>ⁿ w    ==>    (q, w, A) |――n+|w|  (q, ε, ε)
  • Induktionsbeweis Basisfall:
    Induktionsbasis: n = 1
    A = Interjektion (INT)
    INT -> voll gut amtlich = w
    n = 1, |w| = 3
    (q, voll geil amtlich, INT) |―― (q, voll geil amtlich, voll geil amtlich) |―― (q, geil amtlich, geil amtlich) |―― (q, amtlich, amtlich) |―― (q, ε, ε)
    Anzahl der Schritte = n + |w|
    Damit gilt der Basisfall als bewiesen.
  • Exkurs in die Python-Grammatik (bitte Link setzen)
  • Exkurs Addition von Peano-Zahlen der Form n(n(n(….))) :
    Es seien P, P1, P2 ein Peano-Zahlen. Addition von Peano-Zahlen kann rekursiv wie folgt definiert werden:
    Basisfall:
    P + 0 = P
    Rekursiver Fall:  P1 + n(P₂) = n(P1 + P₂)
    Beispiel: Warum ist 2 und 2 = 4?
    n(n(0)) + n(n(0)) =      (wg. rek. Fall)
    n(n(n(0)) + n(0)) =     (wg. rek. Fall)
    n(n(n(n(0) + 0))) =     (wg. rek. Fall)
    n(n(n(n(0))))                (wg. Basisfall)
    Vgl. auch Primitiv-rekursive Funktionen

2017 28 Jun

FSA, 22.6.

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Konfigurationsübergang bei Kellerautomaten
  • Kellerautomatenrepräsentation in Python:
    # Kellerautomaten in Python
    # Beispiel: KA von Folienseite 225
    
    Q = set(['q0','q1','q2'])	# Zustaende
    Sigma = set(['0','1'])		# Eingabealphabet
    Gamma = set(['0','Z'])		# Kelleralphabet
    q0 = 'q0'					# Startzustand
    Z0 = 'Z'					# Kellerstartsymol
    F = set(['q2'])				# Endzustandsmenge
    delta = { 					# Delta-Funktion als dictionary
      ('q0','0','Z') : set([('q1',('0','Z'))]),
      ('q1','0','0') : set([('q1',('0','0'))]),
      ('q1','1','0') : set([('q2',())]),
      ('q2','1','0') : set([('q2',())]),
      ('q2','','Z') : set([('q0',())]) 	# '' = Epsilon 
    }
    
    # Der Kellerautomat als 7-Tupel
    K = (Q,Sigma,Gamma,delta,q0,Z0,F)
    print(K)

 

2017 27 Jun

FSA Übungsblatt #10

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Übungsblatt 10 dreht sich diesmal um das Implementieren von Automaten in python. Als Lösung einfach die vervollständigte Datei abgeben – Fließtext kann als Kommentar eingefügt werden. Bei Problemen gern melden (die Datei sollte nach dem Runterladen gleich ausführbar sein).

P.S. das .txt-Suffix der Datei kann entfernt werden. Ggf beim Ausführen beachten.

2017 23 Jun

FSA, 21.06.

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Thema: Kellerautomat (engl. pushdown automaton)

Ein Kellerautomat ist ein Automat der kontextfreie Sprachen (Typ 2) akzeptiert

Erweiterung von NEA und DEA, neu: Automat hat Kellerspeicher (auch: Stapel, engl.: stack)

Schema Kellerautomat mit Eingabeband und Stapel

Schema Kellerautomat mit Eingabeband und Stapel

 

Formal: Kellerautomat ist ein 7-Tupel – K = (Q, Σ, Γ, δ, q0, Z0, F)

Vom NEA und DEA bekannt: Q, Σ, δ, q0, F

Neu: Γ = Kelleralphabet, Z0 = Anfangssymbol auf dem Stapel

Das ist anders bei der Übergangsfunktion: δ ist eine Abbildung aus Q × (Σ ∪ {ε}) × Γ in die Menge der endlichen Teilmengen von Q × Γ*

Beispiel: δ(q0, 0, Z) = {(q1, 0Z)}, wobei gilt q0 , q1 ∈ Q, 0 ∈ Σ, Z ∈ Γ, Z0 ∈ Γ*

Bedeutet: Befindet sich der Automat in Zustand q0, befindet sich in der Eingabe das Zeichen 0 und ist Z das oberste Symbol auf dem Stapel, dann ändert sich der Zustand zu q1, wird Z vom Stapel gelöscht und wird der String 0Z auf den Stapel gelegt.

Illustration im Foliensatz auf S. 225

Eigenschaften des Kellerautomaten:

  • Stapel ist ein (unendliches) Gedächtnis; Unterschied zu NEA und DEA
  • Stapel wird von oben beschickt und geleert
  • Eingabe wird nur von links nach rechts gelesen

 

Beispiel für größere Fähigkeiten des Kellerautomaten gegenüber endlichen Automaten

L = {0n 1n | n ≥ 1} ist keine reguläre Sprache; die Regelmenge einer möglichen kontextfreieen Grammatik wäre {N → 0 N 1, N → 0 1}

! Die Regel N → 0 N 1 kann keine Regel in einer regulären Grammatik sein. Denn: In regulären (rechtslinearen) Grammatiken dürfen (auf der rechten Regelseite) keine Terminale (hier: 1) rechts von Nichtterminalen stehen.

Endlicher Automat kann die Sprache nicht umsetzen

Versuch:

Scheiternder Versuch L(K) auf einem endlichen Automaten umzusetzen

Der abgebildete Automat könnte nur die Sprache {0* 1*} akzeptieren, aber nicht dieselbe Anzahl 0 und 1 so wie in L oben. Dafür braucht der Automat ein beliebig großes Gedächtnis => Stapel.

 

Konfiguration des Kellerautomaten:

= “Momentaufnahme” des Automaten

Möglich, weil Automat in diskreten Schritten operiert

Konfiguration ist ein Tripel: (q, w, α) ∈ (Q × Σ* × Γ*), wobei q = aktueller Zustand, w = aktueller String in der Eingabe, α = aktueller Zustand des Stapels

Konfigurationsübergang: (p, ax, Aγ) ⊢k (q, x, αγ)

Illustration eines Konfigurationsübergangs: Zwei aufeinanderfolgende Konfigurationen eines Kellerautomaten

Illustration eines Konfigurationsübergangs: Zwei aufeinanderfolgende Konfigurationen eines Kellerautomaten

2017 19 Jun

FSA Übungsblatt #9

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Hier kommt ein etwas ausführlicheres Übungsblatt zu Epsilon-Entfernung und dem Backtrackingverfahren.

2017 17 Jun

FSA, 15.6.

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Thema: Ableitungen und Parsing

  • Ableitungen relativ zu Grammatiken konstruieren
  • Ableitungsrelationen: ==> als Basisrelation
  • ==>k als Verallgemeinerung davon auf k Schritte
  • ==>* als reflexive und transitive Hülle von ==>
  • Ableiten = Parsen.
  • Ziel: rausfinden ob für einen gegebenen Satz w das Paar (S,w) in ==>* ist (S ist das Startsymbol der Grammatik)
  • M.a.W.: gilt S ==>* w ?
  • Wenn das gilt, dann kann man mit etwas Buchhaltungsinformation aus den Ableitungsschritten (z.B. Liste der angewandten Regeln) einen Syntaxbaum konstruieren
  • Parsing = Suche im (virtuellen) Graphen potentieller Ableitungen = Graph-Suche
  • Problem: Suchgraph kann sehr groß oder sogar infinit sein :
    cf-derivations.dot
  • Demo: Ein Top-Down-Backtracking-Parser als Ableitungssimulator
  • Idee: Linkssatzform liegt von links nach rechts gelesen auf einem Stapel, wir ersetzen immer das Element X zuoberst durch eine rechte Seite alpha einer Regel X –> alpha (X ist ein Nichterminal). Liegt ein Terminal obenauf, vergleichen wir es mit dem ersten Element der verbleibenden Eingabe. Sind beide gleich, so entfernen wir das Element aus der Eingabe und vom Stapel (Verfikationsschritt)

Links:

 

2017 16 Jun

FSA, 14.06.

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Kontextfreie Grammatiken
  • Linksableitung und Doppelpfeil: ==> (ableitbar in einem Schritt)
  • Zweck des Ableitens: 1. prüfen, ob ein Satz von einer Grammatik generiert werden kann 2. Syntaxbäume bauen
  • Ableiten = Parsen
  • Beziehung zwischen Semantik und Struktur: Semantik ist homomorph zur Syntax
  • Bedeutung des Doppelpfeiles: ==>L ⊆ V* × V* (Achtung: ==>L ist verschieden von ==>R)
  • Ableitung ist immer relativ zu einer gegebenen Grammatik
  • Ableitung in 0 Schritten: Reflexivität
  • Ableitung in k Schritten (Transitivität, Zerlegung in einen Schritt und k-1 weitere),
  • Ableitung in beliebig vielen Schritten: ==>L* : Vereinigung aller Relationen ==> für k ab 0 (= reflexive und transitive Hülle)
  • Ziel: S ==>* w zu finden für eine Eingabe w

2017 12 Jun

FSA, 8.6.

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Abgeschlußeigenschaften regulärer Sprachen: Typ-3-Sprachen sind unter Vereinigung, Verkettung, Stern- und Plushülle, Schnitt, Differenz, Komplementierung, Spiegelung und Homomorphismus abgeschlossen.
    NB: Man beachte übrigens, dass die im Skript behandelte Komplementierungsoperation von einem vollständigen Automaten (mit vollständiger delta-Funktion) ausgeht. Hier müssen dann nur noch End- und Nichtendzustände vertauscht werden. In der Informatik geht man meist davon aus, dass endliche Automaten vollständig sind — schon wegen des üblichen Alphabets {0,1}. In der CL gehen wir meist von einer partiellen Delta-Funktion aus. Jeder partielle Automat kann durch die Hinzufügung eines sink states und aller fehlenden Übergänge total gemacht werden, der Automat wird dadurch größer. Nur dass dieser sink state dann kein Endzustand ist und daher nichts zur akzeptierten Sprache beiträgt. Bei der Komplementierung wird er jedoch zu einem Endzustand und führt dann zum Akzeptieren der “fehlenden Strings” in Sigma* – L.
  • Spiegelung bedeutet übrigens das Umdrehen eines Wortes. Bei einer gespiegelten Sprache werden alle Wörter in der Sprache umgekehrt. Frage ist: wie zeigt man, dass Typ-3-Sprachen unter Spiegelung abgeschlossen sind? Antwort: mittels einer Konstruktion! Wie sieht diese aus?
  • Epsilon-Entfernung aus NEAs

Materialien:

2017 11 Jun

FSA Übungsblatt #8

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Hier noch ein Blatt zu regulären Ausdrücken…

Themen:

  • Semantik regulärer Ausdrücke
  • Frege-Prinzip
  • Homomorphismus

Die Thompson-Konstruktion überführt einen regulären Ausdruck in einen endlichen Automaten (in dem ε-Übergänge erlaubt sind). Für jeden der Fälle der Thompson-Konstruktion gibt es damit eine zugehörige „Bedeutung“: Die Extension eines regulären Ausdrucks ist der endliche Automat, der genau die Sprache akzeptiert, die der reguläre Ausdruck repräsentiert:

[[ ]] : RA → ε-NEA

 

Für die verschiedenen Fälle der Thompson-Konstruktion:

Screenshot_20170609_135158

 

Dem liegt das Frege-Prinzip (Kompositionalitätsprinzip) zugrunde:

Die Bedeutung eines komplexen Ausdrucks ist eine Funktion der Bedeutungen der unmittelbaren Teilausdrücke und der Art ihrer syntaktischen Verknüpfung.

Zum Beispiel: [[blauer · Dino]] = [[blau]] [[Dino]]

 

Dieses Prinzip erlaubt es einem, die in der Tabelle gezeigten Überführungen von einer Domäne (reguläre Ausdrücke) in eine andere (endliche Automaten) vorzunehmen. Solche Überführungen bezeichnet man als Homomorphismus.

 

Da wir über die Beliebigkeit von Zeichen gesprochen haben, hier ein netter TED-Talk zum Thema: Terry Moore – Why is ‘x’ the unknown?

Und außerdem ein Video, das sehr schön das Konzept abzählbarer Unendlichkeit illustriert: The Infinite Hotel Paradox. Dass wir darüber geredet haben, ist zwar schon etwas länger her, ich finde es aber sehr interessant, also möchte ich es mit euch teilen.

 

Viel Spaß und schönes Wochenende!

Saskia

 

2017 5 Jun

FSA Übungsblatt #7

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Hier ist Übungblatt 7, Schwerpunkt Thompson’s Construction. Ich empfehle nochmal die Bearbeitung der Blätter, aus eigener Erfahrung weiß ich, dass man den Stoff nicht nur durch Angucken und Zuhören lernen kann. Die Abgabefristen sind nicht so wörtlich zu nehmen, falls noch jemand ältere Blätter bearbeiten will, allerdings werde ich nicht kurz vor der Klausur noch stapelweise feedbacken. Nachwievor gelten die Hinweise: a) auch teilweise Bearbeitung ist ok. b) gerne Verbesserungshinweise geben, falls euch irgendwas an den Blättern abschreckt. Eine gute Woche

Markus

2017 4 Jun

FSA 01.06.

Abgelegt unter: Allgemein,Formale Sprachen und Automaten | RSS 2.0 | TB | Tags:  | Kommentare geschlossen

Themen:

 

-Thompson’s construction

-Vorgehensweise grep

 

Thompson’s construction  (Automaten für jeden Fall der regulären Ausdrücke)

Update (TH): Vertauschung bei Fall 3/4 beseitigt

I

1)  εRA     

Fall 1

2) a ∈ Σ

Fall 2

II

3) (α · β)

Fall 4

(Achtung: Neuer Verkettungspunkt!)

4) (α+β)

Fall 3

(Keine Addition, sondern inklusives Oder/OR)

5) (α*)

Fall 5

III (Salvatorische Klausel)

α=  α·α* (Kein eigener Fall da ableitbar)
α?/a. =  εRA +α (Kein eigener Fall da ableitbar)

 

 

Vorgehensweise grep

Grep wandelt reguläre Ausdrücke in einen Syntaxbaum um und diesen in einen Automaten:

((hi+ha)*·hu)*

hihahu-tree

hihahu

2017 1 Jun

FSA 31.5.

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Themen:

- Äquivalenzbeweis

- Reguläre Ausdrücke

Äquivalenzbeweis (Induktion über die Länge der Wörter w)

zu zeigen: L(A) = L(A’)

<=> {w ∈ Σ*|δnd* (q0, w) ⊆ F} = {w ∈ Σ*|δd* ({q0}, w) ∈ F} bzw. ∀w ∈ Σ*: w ∈ L(A) => w ∈ L(A’) ∧ w ∈ L(A’) => w ∈ L(A)

allg. Behauptung: ∀w ∈ Σ*: δd* (q0, w) = δnd* (q0, w)

Induktionsbasis: |w| = 0 => w = ε

(i) δd* (q0‘, ε) = q0

(ii) q0‘ = q0

(iii) {q0} = δnd*(q0, ε)

=> δd*(q0‘, ε) = δnd* (q0, ε)

Induktionsvoraussetzung (IV)

δd* (q0‘, w) = δnd* (q0, w) gelte für alle Wörter w mit (w) ≤ k (k = endliche, konstante Zahl; beliebig gewählt

–> gilt für jede endliche Zahl k+1)

Induktionsschritt

Es sei |w| = k+1, d.h. w = w’a mit a ∈ Σ und w’ ∈ Σ*

(1) δd* (q0‘, w’a) = δd (δd* (q0‘, w’), a)                    (Def. von δd*)

(2) δd* (q0‘, w’) = δnd* (q0, w’)                                  (IV, da |w’| = k)

(3) δd* (q0‘, w’a) = δd (δnd* (q0, w’), a)                    (aus (1) und (2))

Es sei Z = δnd* (q0, w’)

(4) δd (δd* (q0, w’), a) = Upez δnd (p, a)                 (Def. von δd)

(5) Upez δnd (p, a) = δnd* (q0, w’a)                          (Def. von δnd)

(6) δ* (q0‘, w) = δnd* (q0, w)                                    (aus (3) und (5))

Reguläre Ausdrücke

Def. RA:

1. εRA

2. a ∈ Σ

wenn α und β reguläre Ausdrücke sind, dann sind auch

3. (α · β)

4. (α|β)

5. (α*)

reguläre Ausdrücke.

Wie arbeitet grep?

grep: Ausdruck nehmen –> Parsing (Baum bauen) –> Automat

Bsp.: (((hi|ha)*|hu) · x)*

18871308_1576056362407102_660357680_n        jeder reguläre Ausdruck endet bei den Symbolen (Fall 2)

 

nützliche Literatur:

 

Antonia

2017 1 Jun

FSA Übungsblatt 6

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Hier ist Übungblatt 6 zu Induktionsbeweisen, mit ausführlichem Beispiel.

2017 28 Mai

FSA 24.05.

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Themen:

- Induktionsbeweis

- Verallgemeinerung der Übergangsfunktion δd zu δd*

 

Vollständige Induktion

Um eine Aussage P(n) mit n ∈ ℕ zu beweisen, kann man die vollständige Induktion verwenden. Um eine Aussage mittels vollständiger Induktion zu beweisen, muss man drei Punkte abarbeiten.

    1. Induktionsbasis P(0) – es ist zu zeigen, dass die Aussage für 0 gilt
    2. Induktionsvoraussetzung P(n) – der allgemeine Fall, für den die Aussage gelten soll
    3. Induktionsschritt P(n) → P(n +1) – es ist zu zeigen, dass wenn die Aussage für P(n) gilt, dann gilt sie auch für P(n + 1)

 

Die vollständige Induktion kann man sich auch als Dominoeffekt veranschaulichen.
(“Stoße den ersten Stein um und sorge dafür, dass der n-te Stein auch den (n+1)-ten Stein umwirft.”)

 

Verallgemeinerung von δd zu δd*

δd* ist die Übergangsfunktion eines deterministischen Automaten, die nicht nur ein Alphabetzeichen, sondern einen ganzen String als Argument nimmt.

δd*: Q x ∑* ↦ Q, dabei gilt für alle q ∈ Q:

 

δd* (q, 𝜀) = q – reflexiver Fall

δd* (q, aw’) = δd* (δd (q, a), w’) – transitiver Fall

 

Wenn δd* (q0, w) ∈ F gilt, dann wird das Wort w vom Automaten akzeptiert.
Wenn A ein endlicher Automat ist mit A = ⟨Q, ∑, q0, F, δd⟩, dann gilt: L(A) = {w ∈ ∑* | δd* (q0, w) ∈ F)

 

nützliche Links:

Vollständige Induktion

Induktionsbeweis einfach erklärt

 

Bogdan

2017 22 Mai

FSA Übungsblatt #5

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Ein Übungsblatt zur Determinisierung Endlicher Automaten. Schaut dazu insbesondere in die unter dem Beitrag zur letzten Woche verlinkten Folien.

2017 21 Mai

FSA 17/18.05

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Themen:

- deterministischer endlicher Automat

- nicht-deterministischer endlicher Automat

- Determinisierung von NEAs

 

deterministischer Automat: 

 

 

–> der Automat kann nach jeder Eingabe von seinem aktuellen Zustand aus in genau einen Zustand übergehen

Relation:

Ü ≤ Q x ∑ x Q

Ü = { <qo,a,q1> <a1,b,q2> <q1,n,q3> }

Funktion:

𝛅 : Q x ∑ ↦ Q

𝛅 (q0,a) = q1

𝛅 (q1,b) =q2

𝛅 (q1,n) = q3

 

nicht-deterministischer Automat:

–> der Automat kann in einen oder mehrere Zustände übergehen

Funktion:

𝛅 nd : (Q x ∑) ↦ P(Q)

𝛅 nd (q0,a) = { q1,q2}

 

Determinisierung von endlichen Automaten:

–> zu jedem nicht-deterministischen Automaten gibt es einen deterministischen Automaten

 

Vorgehen:

1. Teilmengen Konstruktion –> zusammenfassen von Zuständen

 

Schritt 1:

Definition eines DEA nach einem NEA ( A = (Q, ∑, q0, F, 𝛅nd) – siehe Folie 4 

Q’ = 2q / Ø (–> Potenzmenge der Zustände ohne leere)

q’0 = {q0} (–> Menge mit Startzustand)

F’ = {S ⊆ Q | S ∩ F ≠ Ø} (–> jede Menge von Zuständen mit einem Endzustand wird selber zu einem Endzustand)

δd(S, l) = S q∈S δnd(q, l), ∀l ∈ Σ, ∀S ⊆ Q (–> Deterministische Übergangsfunktion: Vereinigung von einem Symbol l und einer Zustandsmenge S) 

- siehe Folie 9 (grafische Darstellung)

 

Schritt 2:

Entfernung aller nicht-erreichbaren und ko-erreichbaren Zustandsmengen.

 

–> ko-erreichbare Zustände: Es führt kein Weg zu ihnen aber sie sind Endzustände oder führen zu einem.

–> nicht-erreichbare Zustände: Es führt kein Weg zu ihnen und sie sind keine Endzustände oder führen zu einem.

- siehe Folie 9 (letzte Darstellung)

 

2. Induktionsbeweis

 

Eine Aussage h wird bewiesen, indem h(n0) (Induktionsbasis) und h(n) –> h(n+1) (Induktionsschritt) bewiesen werden.

 

Erreichbarkeitsinvariante

- besserer Weg zur determinisierung von NEAs (weil einfacher und praktischer in der Realität)

- Es werden nur erreichbare Zustände zu Zustandsmengen zusammengefasst

- siehe Folie 12 für Determinisierungsalgorithmus in Form von Pseudocode (Folie 13 Erklärung)

 

siehe Vorlesungsfolien: NFA-Determinisierung

 

nützliche Links: 

http://www.graphviz.org/Home.php - zum Erstellen grafischer Darstellungen von Automaten

https://www.latex-project.org/

 

Marie & Philip

 

 

2017 13 Mai

FSA Übungsblatt #4

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Hier ist Übungsblatt 4. Da ich bisher sehr wenige Einsendungen bekommen habe: falls euch eins der folgenden davon abgehalten hat -  I) auch teilweise bearbeitete Übungsblätter können eingeschickt werden. II) sie werden nicht bewertet III) falls ihr mit der Art der Blätter nicht zufrieden seid, gerne rückmelden.

2017 11 Mai

FSA, 10.05./11.05.

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  1. Revision und Analyse der Chomsky-Hierarchie
  2. Grenzen und Unterschiede zwischen den Sprachtypen
  3. endliche Automaten

Aufgabe: Unter welcher Grammatik sind die natürlichen Sprachen einzuordnen?

  • Unsere Annahme: Deutsch ist eine kontextsensitive Sprache.
  • Methode zur Überprüfung der These: Finde mindestens eine kontextsensitive Regel, die nicht durch eine kontextfreie ersetzt werden kann.
  • Ergebnis der Überprüfung anhand der Adjektivflexion: Scheitern der These
  • Angewandtes Beispiel: ”der große Hund” (bestimmter Artikel → schwache Flexion) und “ein großer Hund” (unbestimmter Artikel → gemischte Flexion)
  • Allgemeine These: Natürliche Sprachen sind weitgehend kontextfrei und gehen teilweise in die Kontextsensivität über.

Einstieg in die Thematik die Automatentheorie

Erkenntnisse aus dem Automatenquiz:

Für endliche, nicht-komprimierte Automaten:
Anzahl der Zustände = Anzahl der Buchstaben +1
Anzahl der Übergänge = Anzahl der Buchstaben
Anzahl der Endzustände = Anzahl der Wörter
Definition endlicher Automat: ein endlicher Automat ist ein 5-Tupel, bestehend aus:

  1. einer endlichen Menge Zustände Q
  2. einem Startzustand q0  Q
  3. der Menge der Endzustände  Q
  4. einem endlichen Alphabet Σ
  5. einer Abbildung aus Q x Σ in Q, also einer Übergangsfunktion δ

Ein erster Ansatz zu den Automaten anhand eines (kleinen) englischen Lexikons - Beispiel aus der VL:

Abb. 2 – engl1: nicht-komprimierter Automat

Bildschirmfoto 2017-05-11 um 21.27.58

Abb. 2 – engl2: präfixkomprimierter Automat

Bildschirmfoto 2017-05-11 um 21.30.32

Abb.3 – engl3: Präfix- und suffixkomprimierter Automat

Bildschirmfoto 2017-05-11 um 21.30.50

Einige Beispiele für die praktische Anwendung endlicher Automaten:
Autocomplete bei Suchmaschinen, Messaging-Apps etc.
Handschriftenerkennung; OCR-Erkennung beim Scannen
Rechtschreibprüfung in Textverarbeitungsprogrammen

 

Klassifizierung von Automaten:

 

Automaten können in zyklische und azyklische unterteilt werden. In zyklischen Automaten gibt es Übergänge, die zum selben oder einem vorherigen Zustand zurückführen, sodass zyklische Automaten mit einer unendlichen Sprache arbeiten.

 

Automaten können auch in deterministische und nicht-deterministische klassifiziert werden. Bei deterministischen Automaten gibt es zu jedem Zustand für ein bestimmtes Alphabetsymbol nur einen Übergang. Bei nicht-deterministischen Automaten gibt es zu einem Zustand für ein Alphabetsymbol mehrere Übergänge, man hat also die Wahl, zu welchem nächsten Zustand übergegangen wird.

 

Literaturempfehlungen und nützliche Links:

Ramandeep & Hieronymus

2017 8 Mai

Übungsblatt #3…

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

… ist hier. Themen sind u.a. Typen und die Chomsky-Schützenberger-Hierarchie.

2017 7 Mai

Raul Rojas: Das Nichts in der Mathematik

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Obwohl wir heute bereits in der Schule mit der leeren Menge konfrontiert werden, war ihre Definition und ihr Platz in der Mathematik und Philosophie über Jahrhunderte umstritten

 

https://www.heise.de/tp/features/Das-Nichts-in-der-Mathematik-3703259.html

2017 3 Mai

FSA, 3./4.5

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Themen  Beispiele für endliche Sprachen:

  • Kreditkartennummern
  • ISBN
  • IBAN

Kleene-Stern

 

Unbenannt5

Chomsky Hierarchie

  • ∑*/die Kleensche Hülle  bildet die Grundlage
  • Die Hierarchie beschreibt 4 Mengen von formalen Sprachen mit einem Regelsystem, also einer Grammatik
  • diese Mengen enthalten sich gegenseitig
  • bezeichnet werden sie mit Typ 0-3
  • außerdem gibt es noch die “dunklen Sprachen”, diese haben kein Regelsystem

Chomsky-Hierarchie.svg   Regeln der Grammatiken Eine Grammatik G besteht aus / ist ein 4-Tupel G=(N,∑,S,–>) :

  1.  Nichtterminalen N
  2. Terminalen, die in ∑ enthalten sind
  3. dem Startsymbol S
  4. der binären Relation —>

Wofür steht der Pfeil  bei den Regeln der Grammatiken?

  • man kann statt    NP —> ART NN     auch schreiben    (NP, ART•NN)
  • der Pfeil stellt also eine binäre Relation dar ( Tupel )
  • eine binäre Relation ist eine Menge, die Paare enthält (also: eine Teilmenge des kartesischen Produkts A X B mit den Mengen A und B)
  • die Notation dafür ist unten links auf dem Tafelbild zu sehen

FullSizeRender

Die 4 Typen nach Chomsky und Schützenberger

  FullSizeRender 2

  • Die “Bedeutung” von —>  variiert in den unterschiedlichen Typen
  • je nach dem, welche Bedeutung —> zukommt, können verschiedene Produktionsformen in der Grammatik aufgestellt werden (Beispiele auf der rechten Tafelseite)
  • jede reguläre Sprache ist auch kontextfrei, Typ 3 ist also in Typ 2 enthalten
  • weitere Erklärungen

Anna & Luzie

2017 2 Mai

FSA Übungsblatt 2

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Hier ist ein zweites Übungsblatt zu Stringalgebra und Kommutativität/Assoziativität. Achtung: Bei der Tutorienankündigung ist mir ein kleiner Fehler unterlaufen, Raumnummer & Zeit stimmen, aber Campus ist natürlich Campus II, Golm.

2017 26 Apr

FSA-Tutorium, erstes Übungblatt

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Liebe FSAler,

montags gibt es wie angekündigt ein Tutorium von 12:15-13:45 in Raum III.5.106. Hier gibt es ein erstes Übungblatt, das vor allem die Mathe-Einführung wiederholt. Bei Abgabe an die darauf angegebene Mailadresse gibt es eine Rückmeldung. Die Blätter sind nicht verpflichtend und werden nicht benotet, machen es aber sicher leichter, mit dem Stoff umzugehen und am Ende zu bestehen. Ich beantworte sofern möglich auch präzise Fragen per Mail, falls die Suchmaschine eures Vertrauens nicht mehr weiterhilft. Übungsblätter erscheinen ab jetzt freitags oder samstags, damit wir im Tutorium schon über den aktuellen Stoff reden können.

viel Erfolg!

Markus

 

 

2017 26 Apr

FSA, 26./27.4.

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • String-Verkettung
  • Längen von Strings
  • Kommutativität, Assoziativität von Operationen
  • Der leere String (epsilon) als neutrales Element der Verkettung
  • Algebraische Strukturen: Halbgruppe, Monoid
  • Boolsche Algebra
  • Dreiwertige Logik
  • Stringmengen-Verkettung
  • Mengendefinition, Zermelo-Strich: M = { Beschreibung der Elemente e | Bedingungen an die Elemente e }; “die Menge aller es, für die gilt
  • Zermelo-Fraenkel-Axiomatisierung der Mengentheorie
  • Rekursive Definitionen: bestehen aus mind. einem trivialen Fall (Rekursionsabbruch) und mind. einem rekursiven Fall
  • Potenzierung von Strings
  • Potenzierung von String-Mengen
  • Menge aller Strings Sigma* über einen gegebenen Alphabet Sigma: unendliche Vereinigung Sigmak für alle k ab 0
  • Definition formale Sprache: jede Teilmenge von Sigma* für ein gegebenes Alphabet Sigma

2017 24 Apr

FSA: Tutorium

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Der Tutor, Markus K., wartet auf Sie heute ab 12Uhr vor Raum 14.009.

2017 21 Apr

FSA, 19./20.4.

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Was sind formale Sprachen? Programmiersprachen, Auszeichnungssprachen, Logiken, Mathematik, …
  • Was sind Automaten? Sprachverarbeitende mathematische Objekte
  • Was ist ein Alphabet? Jede nicht-leere endliche Menge
  • Begriffe und Namen um Nachrecherchieren: John von Neumann, Peano-Axiome, Alan Turing, Enigma-Maschine, Konrad Zuse, logische Schaltung

 

2013 12 Apr

FSA-Tutorium: freiwilliges Übungsblatt

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

Damit der Einstieg nicht so schwer fällt, habe ich euch ein paar Aufgaben zusammengestellt, mit denen ihr die Themen aus der letzten Vorlesung wiederholen könnt (PDF).
 

Musterlösung (mit ausführlichen Rechenschritten) von dem Übungsblatt: PDF

Geht die Lösung noch einmal Schritt für Schritt durch, um zu schauen, ob ihr alles verstanden habt! Wenn ihr dann noch Fragen habt, scheut nicht, mir eine Mail zu schicken!

 

Das erste Tutorium wird am Mittwoch um 14:15 Uhr in Raum 14.009 stattfinden.

2012 12 Apr

Formale Sprachen und Automaten: Literatur

Abgelegt unter: Formale Sprachen und Automaten | RSS 2.0 | TB | Kommentare geschlossen

John E. Hopcroft & Jeffrey Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.
Michael Sipser: Introduction to the Theory of Computation, 2005


CL-Blog läuft unter Wordpress 3.5.1
Anpassung und Design: Gabis Wordpress-Templates
23 Verweise - 0,331 Sekunden.