CL-Blog

Computerlinguistik & Politik

2017 26 Okt

Fortgeschrittene Sprachmodellierung: 26.10.

Abgelegt unter: Aktuelle Kurse | RSS 2.0 | TB | Kommentare geschlossen

Kurs geht ab jetzt in Moodle weiter

2017 6 Sep

RIP Holger Czukay

Abgelegt unter: Allgemein | RSS 2.0 | TB | Kommentare geschlossen

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 3 Aug

PidCL Übung 12

Abgelegt unter: Programmieren für Linguisten | RSS 2.0 | TB | Kommentare geschlossen

Hier ist das zwölfte und letzte Übungsblatt. Sobald dieses abgegeben und korrigiert ist, werde ich euch hier benachrichtigen, sobald die Ergebnisse aller Übungen da sind.

Viel Erfolg!

2017 29 Jul

C++ II: Projektabgabetermin und allgemeine Hinweise

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

  • Hier finden Sie allgemeine Hinweise zur Form Ihres Projekts. Bitte beachten Sie diese genauestens, Nichtbeachtung geht in meine Notenbildung ein.
  • Der Abgabetermin ist der 15.10.2017
  • Noch hat mir niemand ihr/sein gewähltes Projektthema genannt. Die Mitteilung an mich ist aber obligatorisch. Bitte machen Sie dies bis Montag, 31.7.

 

2017 27 Jul

PidCL Übung 11

Abgelegt unter: Programmieren für Linguisten | RSS 2.0 | TB | Kommentare geschlossen

Hier kommt die elfte Übung. Nächste Woche kommt dann die zwölfte und letzte Übung. Deshalb biete ich nächste Woche Montag um 10 im üblichen Raum noch einmal ein Tutorium an. Außerdem könnt ihr ab heute Abend / morgen im Schaukasten die Ergebnisse bis einschließlich Übungsblatt 7 einsehen und ich verlängere hiermit die Abgabefrist für Übungsblatt 11 um einen Tag, aufgrund des späten Erscheinens.

Bis dahin Viel Erfolg,

Marco

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 24 Jul

C++ II, 24.7. (Schluss)

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Thema: Inkrementelle Minimierung von Wortlisten

  • Hash-Funktion für Zustände mit boost::hash_combine
  • Funktionsobjekte mit Nicht-Defaultkonstruktoren
  • Übergabe von Funktionsobjektinstanzen an ihre Container (z.B. unordered_set) per Konstruktor-Aufruf
  • Weitergehende Optimierungen:
    • Gelöschte Zustände und Übergänge werden zunächst inaktiv gesetzt, wir sollten sie wieder verwenden => Man kann das einfach mit zwei Listen machen — eine für Zustände, eine für Übergänge — wo wir StateIDs und Übergangsindices speichern und bei Bedarf wieder benutzen können (vgl. Funktionen new_state() und new_transition() in FSAListRepr. Man verwendet hier am besten eine double ended queue (std::deque), diese hat gute Speicherlokalität.
    • Auch dann können noch Lücken in der Zustandsnummerierung bleiben. Beim Umkopieren in eine Nur-Lesen-Repräsentation kann man diese noch schließen
  • Zu klären ist noch, in welchem Verhältnis der Minimierungsalgorithmus und der fertige Automat stehen. Am besten baut man um die Repräsentation herum eine Klasse ähnlich wie Trie (im Beispielcode DFA genannt). Diese verwendet dien Minimierer dann beim Einlesen einer Wortliste.
  • Testen ist im Kurs etwas zu kurz gekommen. Heutzutage testet man automatisiert und zufallsbasiert (fuzzing). Das folgende Shell-Skript nimmt z.B. zufallsbasiert 1000 Wörter aus der Derewo-Liste und minimiert diese. Gibt es einen Absturz, so erkennt man diesen und speichert die das Problem generierende Liste. Statt einer vorhandenen Liste wie Derewo kann man das Eingabematerial auch nach einer W’keitsverteilung erzeugen, ggf. sogar durch einen Markov-Zufallsprozess. Das lässt man dann ein paar Stunden laufen und fühlt sich gleich besser.
    while :
    do 
    	shuf -n 1000 derewo.txt > wl.list
    	./build-dawg wl.list
    	if [ $? -eq 139 ]; then
    		echo "CRASH"
    		cp wl.list crash.list
    		exit 1
    	fi
    done
  • Auch Äquivalenztests kann man auf diese Weise machen: man erzeugt eine zufällige Wortliste und  einen DWAG daraus. Dann gibt man von diesem die Wörter wieder sortiert aus. Beide Listen vergleicht man per diff und beendet das Testskript wieder, wenn sie nicht gleich sind

Weitere interessante Dinge:

  • Die Boost-Bibliotheken bieten zahlreiche nützliche Klassen, z.B. Mengen etc. auf Vektor-Basis (boost::container::flat_set), dynamische Bit-Mengen (boost::dynamic_bitset), Ringpuffer (boost::circular_buffer), Prüfsummen (boost::crc), Hashing (boost::hash), Python-Wrapping von C++-Klassen (boost::python) und vieles mehr. Einfach mal reinsehen
  • Portables Befehlszeilenparsing kann man gut mit tclap machen (von Bibliotheken wie boost::program_options rate ich ab)
  • Hocheffiziente Tokenisierer, auch für natürlichsprachliche Eingaben, macht man mit re2c.

Programmcode:

 

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

PidCL, 20.7.

Abgelegt unter: Programmieren für Linguisten | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Dateien öffnen (open), lesen (readline(), readlines(), for … in … ) und schreiben (write()), schließen (close)
  • Korpusverarbeitung: Extraktion der Wortformen je Lemma aus dm DeReKo-Korpus:
    korpus = open('DeReKo-2014-II-MainArchive-STT.100000.freq','r')
    
    # Dictionary anlegen
    wortformen_pro_lemma = dict()
    
    # Alle Zeilen im Korpus durchgehen
    for zeile in korpus :
    	# Zeile entlang der Tabulatoren auftrennen
    	spalten = zeile.split()
    	# Wenn alles korrekt ist, erhalten wir 4 Teile:
    	# 0=Wortform, 1=Lemma, 2=POS, 3=Frequenz
    	# Zunächst aber testen, ob wir auch 4 Spalten haben
    	if len(spalten) == 4 :
    		lemma = spalten[1]
    		wortform = spalten[0]
    		if lemma in wortformen_pro_lemma :
    			# Das Lemma kam bereits vor 
    			# => aktuelle Wortform zur Liste für dieses Lemma hinzufügen
    			wortformen_pro_lemma[lemma].append(wortform)
    		else :
    			# Lemma wurde noch nicht gesehen 
    			# Für das neue Lemma eine Liste mit der ersten Wortform anlegen
    			wortformen_pro_lemma[lemma] = [ wortform ]
    
    korpus.close()
    print(wortformen_pro_lemma)

2017 21 Jul

C++ II: Katalog der Programmierprojekte [UPDATE]

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Hier finden Sie einen Katalog von Programmierprojekten. Für das Abschlussprojekt können Sie jedes mit C++ II gekennzeichnete Projekt auswählen. Bitte teilen Sie mir Ihre Entscheidung bis Ende nächster Woche mit. Dann folgt auch noch ein Dokument mit allgemeinen Hinweisen zur Bearbeitung der Projekte.

Hinweis: Update: ich habe noch zwei weitere, komplexere Projektthemen hinzugefügt.

 

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 19 Jul

PidCL Übung 10

Abgelegt unter: Programmieren für Linguisten | RSS 2.0 | TB | Kommentare geschlossen

Hier kommt die zehnte Übung.

Viel Spaß und bis kommenden Montag,

Marco

2017 17 Jul

C++ II, 17.7.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Thema: Implementierung des inkrementellen Minimierungsalgorithmus’ von Daciuk et al

  • Goldene Regel: Mache aus jedem Algorithmus eine eigene Klasse (also ein Funktionsobjekt). Der Konstruktor dieser Klasse führt den Algorithmus dann aus.
  • std::stringstream: Streams im Speicher
  • Fortgeschrittene Verwendung Hash-Container (wie unordered_set)
  • Hash-Container basieren auf Äquivalenz ihrer Elemente, nicht auf Gleichheit
  • Funktionsobjekte mit Referenzen auf externe Daten.Wichtig: die von Funktionsobjekten realisierten Funktionen müssen zeitinvariant sein, dh. unabhängig vom Aufrufszeitpunkt immer das gleiche Ergebnis liefern. In der Regel stellt man das sicher, indem die Datenelemente in den Funktionen const, also unveränderlich sind (meist als const-Referenzen). Nun kann sich aber die Variable, auf die sich die Referenz bezieht, zwischen den Funktionsaufrufen ändern (dies ist bei der Automatenminimierung der Fall). Dann muss dennoch die Zeitinvarianz der durch das Funktionsobjekt realisierten Funktion gewährleistet sein.

Programmcode:

 

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

Stellungnahme von einigen Gewerbetreibenden im Hamburger Schanzenviertel

Abgelegt unter: Politisches | RSS 2.0 | TB | Kommentare geschlossen

2017 14 Jul

FSA, 12./13.7.

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

2017 12 Jul

PidCL Übung 9

Abgelegt unter: Allgemein,Programmieren für Linguisten | RSS 2.0 | TB | Kommentare geschlossen

Hier kommt die neunte Übung.

Viel Erfolg und bis Montag!

2017 10 Jul

C++ II, 10.7.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Thema: Hashing

  • Hash-Funktionen: sollen zeitinvariant, deterministisch, effizient sein und gut streuen. Hier finden Sie einige Beispiele. Eine gute Hash-Funktion ist CityHash.
  • Hash-Funktionen bestehen meist aus 3 Bausteinen:
    • der Verrechung des aktuellen Datenblocks in das Hash-Register (mit bitlogischen Operationen wie xor),
    • einer Mix-Phase (Durcheinanderwürfeln der Bits des Hash-Registers mit Verschiebe und Rotationsoperationen
    • einer Normalisierungsphase am Ende
  • Hash-Funktionen in C++: für viele eingebauten Datentypen wie string sind Hash-Funktionen im hash-Template-Funktionsobjekt schon definiert (Beispiel: std::hash<std::string>
  • Für benutzerdefinierte Klassen muss man sich ein eigenes Hash-Funktionsobjekt definieren. Dies passiert in 3 Schritten:
    • Definieren einer size_t hash() const Funktion in der Klasse und Auswahl einer geeigneten Hash-Funktion. Diese kann durchaus auf vorhandenen Hash-Funktion wie std::hash<string> basieren.
    • Definieren eines Funktionsobjekts, welches diese hash()-Funktion “wrappt”:
      struct MyClassHash {
        size_t operator()(const MyClass& x) const
        {
          return x.hash();
        }
      };
    • Funktionsobjekt dem Container bekannt machen:
      typedef std::unordered_set<MyClass,MyClassHash> MyClassSet;
  • Hier finden Sie einige Benchmarks zum Vergleich von Hash-Funktionen
  • Hashing mit offenen Listen noch mal erklärt
  • Tabellenhashing mit Sondierung
  • Interessant: die Sondierungs-Funktion (in Python) j = ((5*j) + 1) mod 2**k gibt bei allen 2^k Aufrufen jeweils einen neuen Wert zwischen 0 und 2**k-1 aus (“besucht” also jeden Wert in diesem Intervall genau ein Mal), unabhängig vom ersten Wert von j. Nehmen Sie z.B. k =3 und probieren Sie es aus!
  • Andere Sondierungsmethoden: linear, quadratisch
  • Dictionaries in Python: Hierzu ein Video und die kommentierte Implementierung in C.

Programmcode:

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 3 Jul

C++ II, 3.7.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Funktionsobjekte:
    • Klassen, die nur (beliebige) Funktionen definieren.
    • Meistens ohne Instanzvariablen (daher auch ohne Benutzerkonstruktor), manchmal mit Instanzvariablen (die dann in der Regel const-Zeiger oder const-Referenzen sind)
    • In C++ wird gerne in Funktionsobjekten der Funktionsaufrufoperator operator() definiert. Rückgabewert und Argumente hängen von der Verwendungsweise ab; z.B. ist der Rückgabewert bei Vergleichsobjekten wie std::equal, std::less usw. immer bool, und operator() hat immer zwei Argumente.
  • Extensionale Typisierung (“Duck typing“)
  • In C++ über Templatisierung realisierbar
  • Repräsentationstausch durch Kombination von Templates und speziellen Konstruktoren

Programmcode:

2017 2 Jul

PidCL Übung 8

Abgelegt unter: Programmieren für Linguisten | RSS 2.0 | TB | Kommentare geschlossen

Hier ist das achte Übungsblatt.

Viel Spaß bei der Bearbeitung und zögert nicht bei Fragen dem morgigen Tutorium beizuwohnen.

2017 30 Jun

FSA, 29.6.

Abgelegt unter: Allgemein | RSS 2.0 | TB | Kommentare geschlossen

Thema: Typ2-Grammatik zu Kellerautomat Fortsetzung

Der zu beweisende Satz: Zu jeder KFG gibt es einen KA oder anders: Typ2-Sprachen ∊ KA-Sprachen

Induktionsbeweis Teil 2:
Länge der Ableitung n = 1 wurde erfolgreich als Induktionsbasis  bewiesen

Die Induktionsvoraussetzung ist:
Die Behauptung gelte für alle Ableitungen mit höchstens Länge k:
A =>ᵏ w   ==>   (q, w, A) |――k+|ʷ| (q, ε, ε)
Hier ist k im Gegensatz zu n als eine (beliebig gewählte) Konstante zu verstehen, zu der bei der Anzahl von Schritten des Automaten noch die Länge von w hinzukommt

Der Induktionsschritt:
x ∊ N ∪ Σ*

A =>k+1 w
A =>¹ X₁X₂…Xₗ  =>k w₁w₂…wₗ = w
Also: eine k+1-schrittige Ableitung wird in einen ersten Schritt und k restliche zerlegt.
An dieser Stelle kommt eine wichtige Eigenschaft von kontextfreien Sprachen zur Anwendung: das Adjazenzkriterium: benutzt der erste Schritt einer Ableitung von A eine Regel A –> X1X2…Xl (für X entweder aus N oder Σ*), dann ist jedes Xi für einen der l Teile von w verantwortlich in dem Sinne Xi ==>+ wi oder Xi == wi (also Xi ==>0 wi). Leitet Xi+1i wi+1 ab, so sind wi und wi+1 unmittelbar adjazent.
Beispiel: S => NP VP =>* die Katze  mag den Kater

Weiter läuft der Beweis über die Konstante k, anhand derer die gleiche Anzahl der Schritte gezeigt werden muss:
(q, w, A) |―― (q, w, x₁x₂…xₗ) |――ᵏ⁺ˈʷˈ (q, ε, ε)
also
(q, w, A) |―― (q, w₁w₂…wₗ, x₁x₂…xₗ)
|――* (q, w₁w₂…wₗ, x₁x₂…xₗ)
|――* (q, w₂…wₗ, x₂…xₗ)
|――* (q, wₗ, xₗ)
|――* (q, ε, ε)
wobei die Anzahl der letzten 4 Schritte k ergibt.

Damit ist Satz “1a) A =>⁺ w => (q, w, A) |――* (q, ε, ε)” bewiesen.
Beweise für 1b, sowie 2a und 2b (siehe gestriges Protokoll) sind den Folien zu entnehmen.

Notwendig für die Beweise ist die Universelle Instanziierung

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 27 Jun

C++ II: Literatur

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Literatur

  • Für die Erweiterung unseres Trie-Klasse in Richtung DAWGs (“Directed acyclic word graphs”) lesen Sie bitte Abschnitte 1-3 dieses Artikels. Wir werden dies ab übernächster Woche anfangen zu implementieren.
  • Dieser Artikel beschreibt Techniken, wie man den Speicherverbrauch von Tries und DAWGs reduzieren kann.

 

2017 27 Jun

C++II, 26.6.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Besprechung der HA

  • Vorwärtsdeklaration lässt typedef-Benutzung vor der kompletten Klassendefinition zu (diese erfolgt unten -> übersichtlicher)
  • Eine eingebettete Klasse (hier Iterator) kennt nicht die Instanzvariablen der Klasse, in die sie eingebettet ist; also müssen alle nötigen Daten übergeben werden (per Konstruktor etc.)
  • Ungültigen Zustand zurückgegeben:
    1. Wert zurückgeben, von dem wir wissen, dass der Iterator ihn nicht verarbeitet: ein ganz großer Wert wie unsigned(-1) oder eine andere ganz große Zahl
    2. std::numeric_limits<unsigned>::max() aus der STL führt Punkt 1 eleganter aus; max() ist dabei eine Klassenfunktion der Klasse numeric_limits<unsigned>.
    3. Flexibelste Lösung: Klassenfunktion InvalidState() definieren . Wird mit static gekennzeichnet und kann ohne Instanz aufgerufen werden.
      => Der Code ist lesbarer, verständlicher und die Methode kann schnell global geändert werden.
  • Header verschiedener Repräsentationen muss unbedingt verschieden sein, damit keine falschen Datenstrukturen in den Trie eingelesen werden
  • böswillige Manipulation der Binärdateien kann bspw. durch Prüfsummen getestet werden
  • header-String soll nun nicht mehr vor der Klassendefinition stehen, damit er nicht für jeden sichtbar ist => private Funktion definieren, die den String enthält und zurückgibt

Ergänzung/Verbesserung des Trie

  • Startindex für Übergänge setzen: In der Schleife über die Zustände wird nach dem push_back() aller ausgehender Übergänge, die neue transition-Vector-Größe bestimmt und die Anzahl der gerade hinzugefügten Übergänge abgezogen.
    • Nur wenn q mindestens einen Übergang hat (Defaultwert -1 muss dann nicht verändert werden)
    • Überlegungen wie diese gleichen einem Induktionsbeweis: Korrektheit der Anweisungen für trivialen Fall (Startzustand) zeigen und dann zeigen, dass es für die nächsten Schritte (in der Schleife) nicht falsch wird.
  • Trie sortieren: Schnellere Suche, in der Folge keine weitere Sortierung bspw. bei auto_complete() nötig.
    • Übergänge pro Zustand sortieren => states.size()-mal muss sortiert werden
    • Über states-Vector iterieren und Übergangsblöcke herausfinden (! nur wenn Startindex nicht -1)
    • Man kann mit Vector-Iteratoren rechnen (Random Access Iterator) => Ab transitions.begin() kann mit + weitergezählt werden um die Intervallgrenzen eines Übergangsblocks zu bestimmen.
    • Um Übergänge zu vergleichen muss im struct der Transition der <Operator überladen werden.
    • Für Tupel-Sortierung gilt generell: Es wird spaltenweise sortiert mit if-Bedingungen. (Für uns reicht der einfache Vergleich der char-Symbole)
    • Guter Stil: Beim Überladen eines Operators innerhalb der Deklaration keinen anderen Operator benutzen.
    • Andere Möglichkeit wäre der Vergleich über Funktionsobjekte: Das sind Klassen wie bspw. class Compare im std::set Hier kann der Standardwert std::less<Key> angepasst werden.
  • Der Optimierer erkennt öfters verwendete gleiche Ausdrücke im Syntaxbaum und rechnet deren Wert nur einmal aus. Also keine Sorge um Effizienz: Der Ausdruck wird nur einmal berechnet.

Programmcode:

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 21 Jun

Netzpolitik.org über das neue Staatstrojanergesetz

Abgelegt unter: Politisches | RSS 2.0 | TB | Kommentare geschlossen

2017 20 Jun

PidCL Übung 7

Abgelegt unter: Programmieren für Linguisten | RSS 2.0 | TB | Kommentare geschlossen

Hallo liebe (Computer)Linguisten,

Hier die siebte Übung. Diesmal als Python-Skript: uebung7.py - und auch in dieser Form abzugeben.

Wie üblich, bis Ende der Woche.

Viel Erfolg,

Marco

2017 20 Jun

C++ II, 19.6: Hausaufgabe

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Hausaufgabe (bitte machen bis nächsten Sonntag Abend)

  1. Erweitern Sie FSAVectorRepr um einen Iterator (anolog dem in FSAListRepr). Natürlich muss FSAVectorRepr::outgoing_transitions_of() auch implementiert werden.
    Hinweis: Da wir die FSAVectorRepr noch nicht effektiv befüllen können (man kann damit ja keinen Trie aufbauen), muss man zum Testen tricksen. Sie könnten FSAVectorRepr z.B. im Defaultkonstruktor von Hand mit einigen (korrekten) Zuständen und Übergängen befüllen und in der Trie-Klasse temporär die Listen- durch die Vektor-Repräsentation austauschen. Zum Test des Iterators eignet sich dann z.B. Trie::as_dot().
    Noch ein Hinweis: der Iterator hier muss auf andere Weise feststellen, ob er am Ende ist (wir haben ja keine Endmarke -1 mehr). FSAVectorRepr hat aber die Information, wieviele Übergänge ein gegebener Zustand hat.
  2. Stellen Sie die read() und write()-Funktionen von FSAVectorRepr fertig (in Analogie zu FSAListRepr). D.h., schreiben Sie auch einen Vorspann-String, anhand dem Sie beim Wiedereinlesen feststellen können, ob Sie auch wirklich eine binäre Vektor-Repräsentation vor sich haben.
  3. Stellen Sie Trie::auto_complete() so um, dass eine set<string> zurückgegeben wird. Variante: verwenden Sie vector<string> und sortieren Sie vor der Rückgabe.

Bitte Programm syntaxfehlerfrei übersetzbar und funktional.

Programmcode (aktualisiert wegen Syntaxfehler :-;):

2017 19 Jun

C++ II, 19.6

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen

  • Besprechung der HA
    • nochmal der Hinweis: prüfe korrekte Vektorindizierung (intern mit asserts, bei Interaktion mit dem Benutzer mit if-Abfragen)
  • Return Value Optimization (RVO): Vermeidung eines Kopierkonstruktoraufrufs durch return Konstruktor();
  • rekursive Funktionen am Beispiel der Trie::auto_complete_at_state()
    • rekursive Aufrufe werden auf dem Stack gespeichert (mit den Parametern des Aufrufs und lokalen Variablen wie bspw. Iteratoren)
    • Wert von auto_complete_at_state(pref,q) bekommt man, wenn man für jeden ausgehenden Übergang q -a-> p den Befehl auto_complete_at_state(pref+a,p) ausführt und deren Ergebnisse zusammenführt. Die Rekursion terminiert, wenn Zustände ohne ausgehende Übergänge erreicht werden.
  • sentinel:  grob gesagt ein spezieller Wert, der ‘Ende’ signalisiert
    • in unserem Trie-Kontext: statt zeitraubende if-Abfragen ob gültiger Vektorindex (current_index!=-1) könnte man die nullte Zelle des Vektors benutzen: diese verweist auf sich selbst (vec[0].next_index=0) und ändere jede -1 in vec[x].next_index=-1 in die Null.
  • std::set: als binärer Suchbaum implementierbar
    • verlangt Definition einer totalen Ordnung über den Elementen (üblicherweise ‘kleiner’)
    • bei einem balancierten binären Suchbaum wie bspw. Rot-Schwarz- oder AVL-Bäumen hat die Suche logarithmische Zeitkomplexität
    • Nachteile: nicht speicherlokal, viel Verwaltung, Rebalancing evtl. aufwendig. Daher prüfe vorher, ob nicht auch ein Vektor als Datenstruktur infrage käme
    • bietet verschiedene Iteratoren (const, nicht_const, reverse_iterator…)
    • mit std::set::find() prüfbar, ob ein Element in der Menge ist. Rückgabe ist ein Iterator, der auf dieses Element zeigt, falls es existiert,  sonst der von std::set::end() zurückgegebene Iterator
  • WICHTIG: dereferenziere nie einen ein_objekt.end()-Iterator! Prüfe daher vor der Dereferenzierung ,wo immer nötig,  ob der Iterator aktuell noch auf ein gütliges Element zeigt.
  • Sortieren:
    • wenn Elemente schon in einer set gespeichert sind, kann diese unter Benutzung von Iteratoren mit einem speziellen Konstruktoraufruf in einem Vektor abspeichern: StringVector sv(menge.begin(),menge.end()); (man kann auch Iteratoren von anderen Containern für die Initialisierung eines Vektors benutzen)
    • STL bietet auch Algorithmen, u.a. std::sort an, das nach #include <algorithm> verfügbar ist.
      • Beispielaufruf: std::sort(vec.begin(),vec.end()); // implizit mit operator< sortiert
      • an diesem Beispiel zeigt sich, dass Iteratoren das Bindeglied zwischen Containern und Algorithmen sind: die Eingabe von std::sort sind Iteratoren (nicht Container).

 

Nachdenkaufgabe:

Wie könnte eine totale Ordnung aussehen, nach der man Tries sortieren könnte?

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 17 Jun

PidCL, 17.6.

Abgelegt unter: Programmieren für Linguisten | RSS 2.0 | TB | Kommentare geschlossen

Python

Themen

  • Typen und Operationen auf Konstanten oder Variablen dieser Typen
    • + – * / ** auf int und float
    • +, *, len(), split() auf Strings
    • Hinweis: len() ist unter Python 2.x byte-orientiert und unter Python 3.x unicode-orientiert
  • Typkonvertierungen: jeder Typname ist auch eine Funktion gleichen Namens, mit dieser kann man (mit Einschränkungen) zwischen Typen konvertieren.
    Beispiele:

    int('0012345')
    str(12345)
    str(False)
    bool('')
  • Neuer Typ: list:
    • kann Konstanten oder Variablen aller anderen Typen in einer geordneten Folge  speichern
    • Syntax von Listen: [ E_0, E_1, ... ,E_k-1 ]
    • Die obige Liste hat die Länge k, die Zählung beginnt bei 0; das letzte Element hat die Position k-1
    • Listenindizierung: ist l eine Liste, dann ist l[i] das i-te Element von l, ab 0 gezählt
    • len() auf Listen
    • Slicing auf Listen: mit l[a:b] (mit a und b als Zahlen) konstruiert eine Teilliste von l mit den Elementen ab Position a bis ausschließlich Position b; a und/oder b können auch weggelassen werden, dann wird für a 0 und für b len(l) benutzt
  • Slicing geht auch auf Strings

 

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 14 Jun

PidCL Übung 6

Abgelegt unter: Allgemein | RSS 2.0 | TB | Kommentare geschlossen

Hier kommt die sechste der zwölf Übungen.

Viel Erfolg!

2017 13 Jun

Sprachkritik: HierMagKritisiertWerden

Abgelegt unter: Allgemein,Politisches | RSS 2.0 | TB | Kommentare geschlossen

Ein interessantes Blog eines Hamburger Journalistik-Profs zu Fragen von Fake News, Framing, Narrativen und dgl.:

HMKW – HierMagKritisiertWerden

2017 13 Jun

C++ II, 13.6.

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Besprechung der HA
  • Binäres Lesen und Schreiben von Repräsentationen; Vor- und Nachteile;
  • Iteratoren in der STL
  • typedef-Schlüsselwort zum Definieren neuer Typnamen
  • Iterator: Zeigerabstraktion
    • Iteratoren implementieren typischerweise Funktionen zum Erzeugen, Vergleichen, Weitersetzen und Dereferenzieren
    • Iteratoren haben privilegierten Zugriff auf ihren Container
    • Iteratoren verbergen jedoch die internen Implementierungsdetails der Container und stellen eine logische Sicht auf den Container her
    • Iteratoren haben stets einen internen Zustand; sie “wissen” also, wo sie gerade “sind” im Container

Nachdenk-Hausaufgabe:

  • Denken Sie über die Implementierung eines Übergangsiterators nach. Wir er sich verhalten könnte, können Sie dem Konstruktor von FSAVectorRepr entnehmen.
  • Dieser Iterator wird auch an anderen Stellen benötigt:
    • bei Trie::as_dot()
    • bei Trie::auto_complete()

Programmcode:

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 9 Jun

PidCL, 8.6.

Abgelegt unter: Programmieren für Linguisten | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Scratch:
    • Variablen, Zuweisung, Veränderung, arithmetische Operationen
    • Schleifen und Berechnungen
    • Verschachtelte Schleifen: Beispiel: Addition aller Zahlen im Einmaleins-Quadrat:
      embedded-for-loops
    • Die innere Schleife läuft 10x für jeden Durchgang der äußeren Schleife; insgesamt werden also 100 Additionen auf die Variable Summe ausgeführt.
  • Python
    • Die Python-Shell
    • Rechnen
    • Datentypen (bis jetzt): int, float, str, bool

2017 6 Jun

PidCL Übung 5

Abgelegt unter: Programmieren für Linguisten | RSS 2.0 | TB | Kommentare geschlossen

Hallo,

Hier ist das fünfte Übungsblatt. Im fünften Übungsblatt werdet ihr ein Scratch-Programm erstellen, das selbst zufällige Melodien erzeugt. Damit ihr einen Anhaltspunkt habt, wie es am Ende klingen soll - Hier eine Hörprobe des fertigen Programms zum Grundton 36.

Viel Erfolg!

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


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