CL-Blog

Computerlinguistik & Politik

Du durchsuchst gerade das Archiv der Kategorie ‘Endliche Automaten in der CL’.

Kategorie: Endliche Automaten in der CL

2016 28 Jan

EAidCL, 28.1.

Abgelegt unter: Endliche Automaten in der CL | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Generischer Algorithmus zur Determinisierung von gewichteten Automaten
  • Mit dem Algorithmus (Folien S. 137) nicht-determinisierbare Automaten
  • Def. Stochastischer prob. Akzeptor: für jeden Zustand q addieren sich die Gewichte der ausgehenden Übergänge plus ein evtl. vorhandenes Endzustandsgewicht auf 1
  • Stochastische Akzeptoren realisieren Wahrscheinlichkeitsverteilungen auf Sigma*
  • Determinisierung erhält Stochastizität.
  • Theorem: Nicht für jeden nicht-deterministischen prob. Akzeptor gibt es einen äquivalenten deterministischen Akzeptor

Beispiel:

  • Finden Sie (nicht-algorithmisch) einen det. Automaten für diesen Akzeptor (über dem prob. Halbring):
    pfa.dot
  • Zur Erinnerung: Der Support dieses Automaten ist ab*. Jeder Kette abk wird ein Gewicht von 0,5 · ((0,5k · 0,5) + (0,75k · 0,25)) zugewiesen. Beispielsweise erhält die Zeichenkette ab das Gewicht 0,5 · (0,52 + 0,75 · 0,25 ) = 0,21875. Der determ. Akzeptor muss, falls er existiert, ab den gleichen Wert zuweisen.
  • Wenn der det. Automat nicht existieren sollte: was ist intuitiv der Grund dafür? Wie kann man seine Nichtexistenz beweisen?
  • Bemerkung: dass das Beispiel in fsm2 nach determinize dennoch terminiert, hat mit dem Unterlauf der Zahlen zu tun. Es zeigt sich einmal mehr, dass man in der stat. CL nur log-W’keiten verwenden sollte.

Foliensätze

2016 21 Jan

EAidCL, 21.1.

Abgelegt unter: Endliche Automaten in der CL | RSS 2.0 | TB | Kommentare geschlossen

Themen:

Literatur:

2016 7 Jan

EAidCL, 7.1.

Abgelegt unter: Endliche Automaten in der CL | RSS 2.0 | TB | Kommentare geschlossen

Themen:

Literatur

  • Oncina/Seban: Learning stochastic edit-distance transducers
  • Schulz/Mihov: Fast string correction with Levenshtein automata

 

2015 18 Dez

EAidCL, 17.12.

Abgelegt unter: Endliche Automaten in der CL | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Idempotenz und Extremalität von Halbringen
  • Beste Pfade in Automaten: Relaxierung in topologischer Ordnung

Hausaufgabe (per Email an mich)

  • Beweisen Sie, dass a K b  =def   a + b = a eine partielle Ordnung ist (dass K also reflexiv, transitiv und antisymmetrisch ist)

2015 3 Dez

EAidCL, 3.12.

Abgelegt unter: Endliche Automaten in der CL | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Verbmorphologie
  • Halbringe und gewichtete Automaten

Hausaufgabe (bis 10.12., 11:00 per Email)

  • Ist ({true,false},∧,∨,true,false) ein Halbring? Begründen Sie Ihre Ansicht durch Abprüfen der Axiome.

 

2015 26 Nov

EAidCL, 26.11.

Abgelegt unter: Endliche Automaten in der CL | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Morphologieverarbeitung

Materialien:

Obligatorische Hausaufgabe (bis 3.12., 11:30 per Email an mich)

Schreiben Sie Ersetzungregeln für folgende Phänomene

  • die s-Tilgung bei Verben auf x in der Form 2.sg. (neben x betrifft das übrigens noch weitere Verben)
  • die optionale Tilgung von e bei Verben auf er in der Form 1.sg.: ich ändere, ich ändre.
  • die obligatorische Tilgung von e bei Verben auf el in der Form 1.sg.: ich segle
  • Schwa-Einfügungsregeln für möglichst alle Verbformen in unserem Transduktor

Hinweise:

  • Am besten schreiben Sie alle Regeln in eine Datei  und laden sie mit load contextrules.
  • Optionale Ersetzungsregeln erhält man, wenn man den Regelpfeil in Klammern setzt: (->). Optionale Regeln erzeugen stets zwei Ergebnisse: einmal wurde die Ersetzung vorgenommen, einmal nicht.
  • Eine sehr gute Quelle zur dt. Morphologie ist canoo.net.

2015 19 Nov

EAidCL, 19.11.

Abgelegt unter: Endliche Automaten in der CL | RSS 2.0 | TB | Kommentare geschlossen

Themen:

  • Ersetzungs- und Klammerungsregeln
  • Deutsche Morphologie

Material: eaidcl-19.11.2015

Hausaufgabe (bis 26.11. per Email)

  • Schreiben Sie ein fsm2-Skript und zwei Lexikondateien für a) Verbflexive und b) Verbstämme basierend auf morph.sym. Die Verbstämme sollen aus allen möglichen Klassen sein, also latinate wie Präfixverben, regelmäßige wie unregelmäßige Verben. Kodieren Sie mindestens 20 Einträge.
    Hinweise: geben Sie den Dateien die Endung .lex und laden Sie sie mit load lexicon. Die Syntax von Kategorien ist [KATEGORIENAME Merkmal1=Wert1 Merkmal2=Wert2 ...]

 

 

2015 22 Okt

Endliche Automaten in der CL: fsm2

Abgelegt unter: Endliche Automaten in der CL | RSS 2.0 | TB | Kommentare geschlossen

Hier einige Versionen:

Handbuch: fsm2_manual

2010 2 Mai

fsm2-Handbuch

Abgelegt unter: Endliche Automaten in der CL | RSS 2.0 | TB | Kommentare geschlossen


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