kopf
brlogo
fensterobenrechts
   
   
fensteruntenblau
   
 

 

Endliche Automaten und Formale Sprachen

 

"Automaten, formale Sprachen und Berechenbarkeit" lautet der Titel eines Vorlesungsskripts zur Theoretischen Informatik (TU München), das man als eine der ersten Antworten findet bei der Suche nach "Automaten Sprachen" im Web.

 

In den Vorgaben Zentralabitur in NRW (hier für 2012) werden Kenntnisse verlangt über Endliche Automaten und formale Sprachen

  • Modellieren kontextbezogener Problemstellungen als deterministische endliche Automaten
  • Darstellung von deterministischen endlichen Automaten als Graph und als Tabelle
  • Formale Sprachen: Reguläre Sprachen und ihre Grammatiken
  • Entwicklung eines Parsers für eine einfache formale Sprache (nur Leistungskurs)
 

Für die Lehrerfortbildung wurden die beiden folgenden Skripte erstellt, die den Themenbereich von zwei Seiten angehen, aber inhaltlich und bez. der Übungsaufgaben aufeinander bezogen sind. Sie eignen sich auch als Unterrichtsmaterial für die 13. Klasse (bzw. Q2), um den Schülern ein Jahr vor dem Abitur einen kleinen Eindruck von der Vorgehensweise an der Universität zu vermitteln.

 

Formale Sprachen - eine Einführung

(von Tim Lethen, z. Zt. Saarlouis)

 

Grammatik1

 

Die Theorie der formalen Sprachen bewegt sich im Wesentlichen vor dem Hintergrund dreier scheinbar unabhängiger Themenfelder. Historisch gesehen war es zunächst die mathematische Logik, in der man versuchte, die gesamte Mathematik auf syntaktische Umformungen formaler Ausdrücke zu reduzieren und somit auch das Beweisen zu formalisieren. Die Versuche waren ausgesprochen erfolgreich: Jede beweisbare Aussage kann durch rein syntaktisches Umformen der Ausdrücke eines hinreichenden Axiomensystems ‚bewiesen' werden. Als Teilbereich der Künstlichen Intelligenz spielt das Erzeugen menschlicher Sprache durch Maschinen eine zentrale Rolle. Auch hier geht es um formales Erzeugen von ‚gültigen' Sätzen in dem Sinne, dass auf den Inhalt, d.h. auf die Bedeutung der Sprache, kein Augenmerk fällt. Beispiele finden sich in Abschnitt 5. Als dritter Bereich ist der Compilerbau zu nennen, in dem man sich ganz wesentlich auf theoretische Ergebnisse aus dem Bereich der formalen Sprachen stützt. Die Erstellung eines Compilers kann fast immer völlig automatisiert werden, wenn die zugrunde liegende (Programmier-) Sprache mit geeigneten Grammatiken. ...

Download der PDF-Datei

 

 

Endliche Automaten

(von Friedhelm vom Hau)

 

Automat

 

Definition

 

Unter einem deterministischen endlichen Automaten versteht man ein Konstrukt bestehend aus

  1. einer (endlichen) Menge von Eingabezeichen (Eingabe-Alphabet)
  2. einer (endliche) Menge von Zuständen,
  3. einer Überführungsfunktion, die für jeden Zustand und für jedes Eingabezeichen den Folgezustand angibt.
  4. einem Anfangszustand Z 0 (im Zustandsgraph durch einen Pfeil dargestellt),
  5. einer Menge von Endzuständen (Doppelkreise im Zustandsgraph)
  6. einer (endliche) Menge von Ausgabezeichen (Ausgabe-Alphabet)
  7. einer Ausgabefunktion, die für jeden Zustand und für jedes Eingabezeichen das Ausgabezeichen angibt.
 

Download der PDF-Datei

 

 
 
Sunday, 19. November 2017 / 20:53:47