Logo Qualitäts- und UnterstützungsAgentur

Startseite Bildungsportal NRW

Orientierungsbereich (Sprungmarken)

Grundlagen von Automaten und formalen Sprachen sowie die Modellierung und Implementierung eines Parsers zu einer formalen Sprache

Leitfrage:Wie kann man (endliche) Automaten genau beschreiben? Wie können endliche Automaten und Kellerautomaten (in alltäglichen Kontexten oder zu informatischen Problemstellungen) modelliert werden? Wie können Sprachen durch Grammatiken beschrieben werden? Welche Zusammenhänge gibt es zwischen formalen Sprachen, Automaten und Grammatiken? Wie kann ein Parser für eine einfache formale Sprache entwickelt werden?

Vorhabenbezogene Konkretisierung:

Anhand kontextbezogener Beispiele werden endliche Automaten entwickelt, untersucht und modifiziert. Dabei werden verschiedene Darstellungsformen für endliche Automaten ineinander überführt und die akzeptierten Sprachen endlicher Automaten ermittelt. An einem Beispiel wird ein nichtdeterministi¬scher Akzeptor als Alternative zu einem entsprechenden deterministischen Akzeptor eingeführt. Auch die Umwandlung eines nichtdeterministischen Automaten in einen deterministischen Automaten wird thematisiert.

Anhand kontextbezogener Beispiele werden Grammatiken regulärer Sprachen entwickelt, untersucht und modifiziert. Der Zusammenhang zwischen regulären Grammatiken und endlichen Automaten wird verdeutlicht durch die Entwicklung von allgemeinen Verfahren zur Erstellung einer regulären Grammatik für die Sprache eines gegebenen endlichen Automaten bzw. zur Entwicklung eines endlichen Automaten, der genau die Sprache einer gegebenen regulären Grammatik akzeptiert. Zu einer einfachen regulären Sprache wird ein Parser in Form eines Java-Programms entwickelt.

Auch nicht-reguläre Grammatiken werden untersucht, entwickelt oder modifiziert. An einem Beispiel werden die Grenzen endlicher Automaten ausgelotet. Mit Blick auf diese Einschränkungen endlicher Automaten wird die Idee eines Automaten mit Speicher thematisiert und zu einem Kellerautomaten weiterentwickelt.

Zeitbedarf: 30 Stunden

Sequenzierung des Unterrichtsvorhabens:

Unterrichtssequenzen

Zu entwickelnde Kompetenzen

Beispiele, Medien, Materialien

4. Endliche Automaten

(e) Erarbeitung der formalen Beschreibung eines endlichen Automaten auf der Grundlage von Automaten in bekannten Kontexten

(f) Untersuchung, Darstellung und Entwicklung endlicher Automaten

(g) Umwandlung nichtdeterministischer endlicher Automaten in deterministische endliche Automaten

Die Schülerinnen und Schüler

  • analysieren und erläutern die Eigenschaften endlicher Automaten und Kellerautomaten einschließlich ihres Verhaltens auf bestimmte Eingaben (A),
  • analysieren und erläutern Grammatiken regulärer und kontextfreier Sprachen (A),
  • erläutern die Grenzen endlicher Automaten und regulärer Sprachen im Anwendungszusammenhang (A),
  • ermitteln die formale Sprache, die durch eine Grammatik erzeugt wird (A),
  • entwickeln und modifizieren zu einer Problemstellung endliche Automaten oder Kellerautomaten (M),
  • entwickeln zur akzeptierten Sprache eines Automaten die zugehörige Grammatik (M),
  • entwickeln zur Grammatik einer regulären oder kontextfreien Sprache einen zugehörigen endlichen Automaten oder einen Kellerautomaten (M),
  • modifizieren Grammatiken regulärer und kontextfreier Sprachen (M),
  • entwickeln zu einer regulären oder kontextfreien Sprache eine Grammatik, die die Sprache erzeugt (M),
  • stellen endliche Automaten in Tabellen oder Graphen dar und überführen sie in die jeweils andere Darstellungsform (D),
  • ermitteln die Sprache, die ein endlicher Automat oder ein Kellerautomat akzeptiert (D),
  • beschreiben an Beispielen den Zusammenhang zwischen Automaten und Grammatiken (D),
  • entwickeln iterative und rekursive Algorithmen unter Nutzung der Strategien „Modularisierung“, „Teilen und Herrschen“ und „Backtracking“ (M).

Beispiele:

Cola-Automat, Geldspielautomat, Roboter, Zustandsänderung eines Objekts „Auto“, Akzeptor für bestimmte Zahlen, Akzeptor für Teilwörter in längeren Zeichenketten, Akzeptor für Terme

5. Untersuchung und Entwicklung von Grammatiken regulärer Sprachen

(a) Erarbeitung der formalen Darstellung regulärer Grammatiken

(b) Untersuchung, Modifikation und Entwicklung von Grammatiken

(c) Entwicklung von endlichen Automaten zum Erkennen regulärer Sprachen die durch Grammatiken gegeben werden

(d) Entwicklung regulärer Grammatiken zu endlichen Automaten

(e) Entwicklung eines Parsers für eine einfache reguläre Sprache

Beispiel:

reguläre Grammatik für Wörter mit ungerader Parität, Grammatik für Wörter, die bestimmte Zahlen repräsentieren, Satzgliederungsgrammatik

6. Grenzen endlicher Automaten

Beispiele:

Klammerausdrücke, a^n b^n im Vergleich zu (ab)^n

7. Entwicklung eines Kellerautomaten als Antwort auf die Grenzen endlicher Automaten

(a) Erweiterung eines DEA um eine einzelne Speichervariable zum Zählen von Eingabezeichen (z.B. Klammern) und Problematisierung dieses Ansatzes

(b) Entwicklung eines Automaten mit Kellerspeicher

(c) Anwendung eines Kellerautomaten zur Syntaxüberprüfung auf Grundlage von nicht-regulären Grammatiken

(d) Implementierung eines Kellerautomaten zur Syntaxüberprüfung (Backtracking)
Zum Seitenanfang

© 2024 Qualitäts- und UnterstützungsAgentur - Landesinstitut für Schule