Termine

• Di. 11:30-13:00 Uhr, Raum M13.11
• Fr. 09:45-11:15 Uhr, Raum M13.11

Dozent

• Stefan Evert, Raum 2/10, eMail: evert@ims.uni-stuttgart.de
  (Sprechstunde: Di. 13:00-14:00)

Kursprogramm

• Einführung: was sind formale Sprachen?
• Definition formaler Sprachen und ihre elementaren Eigenschaften
• reguläre Sprachen
  • reguläre Ausdrücke¹ und reguläre Sprachen
  • endliche Automaten und reguläre Sprachen
• kontextfreie Sprachen
  • kontextfreie Grammatiken und Sprachen
  • Normalformen und Parser für kontextfreie Grammatiken
  • Kellerautomaten und kontextfreie Sprachen
• Bemerkungen zu kontextsensitiven Sprachen
• Typ-0-Sprachen
  • Turing-Maschinen und das Halteproblem
  • Typ-0-Sprachen und Turing-Maschinen
• die Chomsky-Hierarchie
• Anwendungen
  • Anwendungen von regulären Ausdrücken und endlichen Automaten
  • Transducer und ihre Anwendung in der Computerlinguistik
  • Anwendungen von kontextfreien Grammatiken
• formale Sprachen und natürliche Sprache
  • zu welcher Sprachklasse gehören natürliche Sprachen?
  • Substitution und Homomorphismen
  • Erweiterungen der kontextfreien Grammatiken

Organisatorisches

• Scheinerwerb:
  • Regelmäßige Teilnahme an der Vorlesung
  • Bearbeitung der schriftlichen Übungsaufgaben
  • Abschlußklausur in der letzten (oder vorletzten) Semesterwoche
• Übungsaufgaben:
  • Die Übungsaufgaben dienen zur Vorbereitung der Klausur. Im Verlauf des Semesters werden insgesamt ca. sechs Übungsblätter ausgegeben.
  • Die Aufgaben sind schriftlich zu bearbeiten. Sie können in Arbeitsgruppen mit maximal drei Teilnehmern bearbeitet werden. Jede Arbeitsgruppe braucht nur eine Ausfertigung der Lösungen abzugeben.
  • Bearbeitungszeit: jeweils eine Woche (es zählt der auf dem Übungsblatt genannte Abgabetermin!). Verspätet abgegebene Lösungen können im Normalfall nicht gewertet werden.
  • Lösungen zu den Aufgaben werden ca. eine Woche nach der Abgabe im Seminar vorgestellt und besprochen.
  • Für die Zulassung zur Abschlußklausur ist mindestens die Hälfte der erreichbaren Punktzahl bei den schriftlichen Aufgaben erforderlich.

¹ Larry Wall über reguläre Ausdrücke: “Regular expressions were invented by computational linguists who love to write examples like /aa*b*(cd)*ee/. While these are conducive to reasoning about pattern matching in the abstract, they aren't so good for pattern matching in the concrete. In real life, most atoms are longer than a or b. In real life, tokens are more recognizable if they are separated by whitespace. In the abstract, /a+/ is reducible to /aa*/. In real life, nobody wants to repeat a 15 character token merely to satisfy somebody's idea of theoretical purity. So we have shortcuts like the + quantifier to say "one or more".”