Logo Qualitäts- und UnterstützungsAgentur

Startseite Bildungsportal NRW

Orientierungsbereich (Sprungmarken)

Endliche Automaten und formale Sprachen (Unterrichtsvorhaben Q2-II)

Leitfragen: Wie kann man (endliche) Automaten genau beschreiben? Wie können endliche Automaten (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, endlichen Automaten und regulären Grammatiken?

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 eingeführt als Alternative gegenüber einem entsprechenden deterministischen Akzeptor.

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.

Auch andere Grammatiken werden untersucht, entwickelt oder modifiziert. An einem Beispiel werden die Grenzen endlicher Automaten ausgelotet.

Zeitbedarf: 20 Stunden

Sequenzierung des Unterrichtsvorhabens:

Unterrichtssequenzen

Zu entwickelnde Kompetenzen

Beispiele, Medien oder Materialien

1. Endliche Automaten

(a) Vom Automaten in den Schülerinnen und Schülern bekannten Kontexten zur formalen Beschreibung eines endlichen Automaten

(b) Untersuchung, Darstellung und Entwicklung endlicher Automaten

Die Schülerinnen und Schüler

  • analysieren und erläutern die Eigenschaften endlicher Automaten einschließlich ihres Verhaltens auf bestimmte Eingaben (A),
  • analysieren und erläutern Grammatiken regulärer Sprachen (A),
  • zeigen die Grenzen endlicher Automaten und regulärer Grammatiken im Anwendungszusammenhang auf (A),
  • ermitteln die formale Sprache, die durch eine Grammatik erzeugt wird (A),
  • entwickeln und modifizieren zu einer Problemstellung endliche Automaten (M),
  • entwickeln und modifizieren zu einer Problemstellung endliche Automaten (M),
  • entwickeln zur akzeptierten Sprache eines Automaten die zugehörige Grammatik (M),
  • entwickeln zur Grammatik einer regulären Sprache einen zugehörigen endlichen Automaten (M),
  • modifizieren Grammatiken regulärer Sprachen (M),
  • entwickeln zu einer regulären 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 akzeptiert (D).
  • beschreiben an Beispielen den Zusammenhang zwischen Automaten und Grammatiken (D).

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

Ergänzungsmaterialien UV II.1

2. 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

Beispiele:

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

3. Grenzen endlicher Automaten

Beispiele:

Klammerausdrücke, anbn im Vergleich zu (ab)n

Zum Seitenanfang

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