Theoretische Informatik: Reguläre Sprachen und endliche Automaten

Theoretische Informatik: Reguläre Sprachen und endliche Automaten

Gymnasium | Mittlere Schulformen

Informatik & Medienbildung

11. | 12. | 13. Klasse

10 - 15 Unterrichtsstunden

Beschreibung

Die theoretische Informatik bildet mit endlichen Automaten und formalen Sprachen das Grundgerüst für moderne Programmiersprachen. Mit dieser Unterrichtseinheit können sich ihre Schülerinnen und Schüler die Grundlagen dieses Themengebiets mithilfe von handlungsorientierten Situationen und differenzierten Aufgaben erarbeiten. Unterstützt wird die Erarbeitung durch das verlinkte Hilfematerial und eine interaktive Software zur Erstellung von endlichen Automaten. Ein Kahoot!-Quiz dient als Gesamtlernzielkontrolle.
Leseprobe ansehen
# theoretische informatik
# formale sprachen
# reguläre sprachen und grammatiken
# deterministische endliche automaten
# nichtdeterministische endliche automaten, deterministische kellerautomaten

Kompetenzen

Klassenstufe:Sek. II
Dauer:10–15 Unterrichtsstunden
Lernziele:Die Lernenden … 1. entwerfen Zustandsdiagramme endlicher Automaten zur Erkennung von korrekten Eingaben, 2. unterscheiden deterministische und nichtdeterministische endliche Automaten und wandeln diese ineinander um.
Kompetenzen:Modellieren und Implementieren
Themenbereiche:Theoretische Informatik, Formale Sprachen, Reguläre Sprachen und Grammatiken, deterministische und nichtdeterministische endliche Automaten, deterministische Kellerautomaten

Inhaltsangabe

Benötigt

  • Tablet/Laptop/PC pro Schüler/in oder pro Schülerpaar
  • Internetzugang

Einstieg

Thema:Endliche Automaten mit Ausgabe
M 1Wie kann man einen Automaten formal beschreiben?
M 2Formale Definition für endliche Automaten mit Ausgabe
M 3Übungsaufgaben: Mealy-Automaten

Erarbeitung

Thema:Endliche deterministische und nichtdeterministische Automaten
M 4Wie können E-Mail-Adressen automatisiert überprüft werden?
M 5Übungsaufgaben: Deterministische endliche Automaten
M 6Reguläre Sprachen und Grammatiken
M 7Übungsaufgaben: Reguläre Sprachen und Grammatiken
M 8Nichtdeterministische Automaten – Mit welchen Regeln lässt sich eine Firewall umsetzen?
M 9Äquivalenz von NEA und DEA – Die Potenzmengenkonstruktion

Vertiefung (optional)

Thema:Grenzen endlicher Automaten und regulärer Sprachen
M 10Grenzen endlicher Automaten und regulärer Sprachen
M 11Endliche Kellerautomaten – Wie kann man korrekte Klammerausdrücke erkennen?

Sicherung

M 12Bist du fit in regulären Sprachen und endlichen Automaten?
Benötigt:Kahoot!-Quiz:https://raabe.click/Kahoot-Lernerfolgskontrolle

Erklärung zu den Symbolen

0,00 €

Für Schulen & Fachschaften

Egal ob einzelne Fachschaft oder komplette Schule: Mit unseren flexiblen Abo-Modellen finden wir den richtigen Weg, um den Unterricht von Ihnen und Ihres Kollegiums einfach zu gestalten.