Formale Sprachen und Grammatiken

Formal Languages and Grammars

Informatik Klasse 12 14 Aufgaben
InformatikFormale SprachenKerncurriculum

Autokennzeichen, E-Mail-Adressen oder Gleitkommazahlen folgen exakten Bildungsregeln — eine formale Sprache ist die Menge aller Wörter über einem Alphabet, die solche Regeln erfüllen. Eine Grammatik definiert sie durch Produktionsregeln (EBNF mit Option und Wiederholung), und ob ein Wort ableitbar — also wohlgeformt — ist, lässt sich systematisch prüfen. Die Trennung von Syntax und Bedeutung erklärt, warum ein Compiler einen fehlenden Strichpunkt nie „gemeint verstehen" kann.

Ermöglicht (1)

Endliche Automaten
Klasse 12
›
Leicht
Multiple Choice #1 15s ▶ Testen

Was versteht man in der Informatik unter einem Alphabet?

  • ● Eine endliche Menge von Zeichen, aus denen Wörter gebildet werden
  • ○ Die Buchstaben von A bis Z
  • ○ Eine sortierte Liste aller erlaubten Wörter
Ein Alphabet ist jede endliche Zeichenmenge — etwa {0, 1} oder {a, b, …, z, @, .}. Wörter sind endliche Zeichenketten daraus.
Multiple Choice #2 15s ▶ Testen

Was ist eine formale Sprache?

  • ● Die Menge aller Wörter, die nach festgelegten Regeln gebildet werden dürfen
  • ○ Eine besonders höfliche Ausdrucksweise
  • ○ Ein Programm, das Texte übersetzt
Eine formale Sprache ist eine Wortmenge über einem Alphabet. Die Regeln — etwa eine Grammatik — entscheiden eindeutig, ob ein Wort dazugehört.
Wahr / Falsch #3 15s ▶ Testen

Eine formale Sprache kann unendlich viele Wörter enthalten, obwohl ihre Grammatik nur endlich viele Regeln hat.

✓ Wahr
Richtig — Wiederholungsregeln erzeugen beliebig lange Wörter. Endlich viele Regeln, unendlich viele Wörter — das ist gerade die Stärke von Grammatiken.
Multiple Choice #4 20s ▶ Testen

Regel für Münchner Kennzeichen (vereinfacht): „M", Bindestrich, ein bis zwei Buchstaben, ein bis vier Ziffern. Welches Kennzeichen ist wohlgeformt?

  • ● M-AB 123
  • ○ M-123 AB
  • ○ MA-B 123
Nur die erste Zeichenkette folgt der Reihenfolge der Regel. Formale Regeln prüfen die Form Zeichen für Zeichen — Fast-richtig zählt nicht.
Multiple Choice #5 18s ▶ Testen

Was ist eine Grammatik im Sinn der theoretischen Informatik?

  • ● Ein Satz von Produktionsregeln, die beschreiben, wie gültige Wörter erzeugt werden
  • ○ Eine Sammlung von Rechtschreibtipps
  • ○ Ein Wörterbuch aller gültigen Wörter
Eine Grammatik ERZEUGT die Sprache — jedes ableitbare Wort gehört dazu, jedes andere nicht. Deshalb braucht sie kein Wörterbuch, das alle Wörter aufzählt.
Lückentext #6 15s ▶ Testen

Ein Wort gehört genau dann zur Sprache, wenn es sich aus dem Startsymbol mit den Regeln der Grammatik ___ lässt.

✓ Antwort: ableiten
Ableitbarkeit ist das Kriterium für Zugehörigkeit — man startet beim Startsymbol und wendet Regeln an, bis das Wort dasteht.
Wahr / Falsch #7 15s ▶ Testen

Der Satz „Der Kühlschrank singt leise Theoreme" ist grammatisch wohlgeformt. Das zeigt: Ein Wort oder Satz kann zur Sprache gehören und trotzdem inhaltlich unsinnig sein.

✓ Wahr
Richtig — Syntax (Form) und Semantik (Bedeutung) sind getrennte Ebenen. Formale Regeln prüfen nur die Form.
Multiple Choice #8 15s ▶ Testen

Regel einer Programmiersprache: Zuweisung = Bezeichner "=" Zahl ";". Welche Zeichenkette erkennt der Compiler als Zuweisung an?

  • ○ x = 5
  • ● x = 5;
  • ○ 5 = x;
Eine Programmiersprache ist eine formale Sprache: Nur Zeichenketten, die sich exakt aus den Regeln ableiten lassen, gehören dazu. „x = 5“ ohne Strichpunkt ist nicht ableitbar — auch wenn klar ist, was gemeint war. „Gemeint“ ist Semantik, geprüft wird Syntax. Bei „5 = x;“ stehen Zahl und Bezeichner an den falschen Stellen.
Multiple Choice #9 20s ▶ Testen

Alphabet {a, b}. Die Sprache L enthält alle Wörter, die mit a beginnen und mit b enden. Welches Wort liegt in L?

  • ● aab
  • ○ ba
  • ○ a
aab beginnt mit a und endet mit b. „ba" beginnt falsch, „a" endet nicht mit b — Zugehörigkeit ist eine Ja/Nein-Frage entlang der Regeln.
Lückentext #10 12s ▶ Testen

In einer Grammatik heißen die Regeln, mit denen Symbole schrittweise ersetzt werden, ___ (ein Wort).

✓ Antwort: Produktionsregeln
Produktionsregeln (z. B. Satz → Subjekt Prädikat) ersetzen links stehende Symbole durch rechte Seiten, bis nur noch Zeichen des Alphabets dastehen.
Multiple Choice #11 18s ▶ Testen

Wozu definiert man E-Mail-Adressen oder Gleitkommazahlen über eine formale Sprache statt über Beispiele?

  • ● Damit ein Programm für JEDE Zeichenkette eindeutig entscheiden kann, ob sie gültig ist
  • ○ Damit die Adressen kürzer werden
  • ○ Damit sich Menschen die Schreibweise besser merken können
Beispiele lassen Grenzfälle offen; eine Grammatik entscheidet jeden Fall. Genau das braucht ein Eingabefeld, das Adressen prüfen soll.
Mittel
Multiple Choice #1 20s ▶ Testen

In der EBNF-Notation bedeuten eckige und geschweifte Klammern: [x] und {x}. Was heißt das jeweils?

  • ● [x]: x darf einmal vorkommen oder wegfallen; {x}: x darf beliebig oft (auch null-mal) wiederholt werden
  • ○ [x]: x ist Pflicht; {x}: x kommt genau einmal vor
  • ○ [x]: x wird wiederholt; {x}: x entfällt immer
Option und Wiederholung sind die beiden Bausteine, mit denen EBNF endlich kurze Regeln für unendlich große Sprachen schreibt.
Multiple Choice #2 20s ▶ Testen

EBNF-Regel für Ganzzahlen: Zahl = Ziffer { Ziffer }. Welche Zeichenkette gehört NICHT zur Sprache?

  • ● die leere Zeichenkette
  • ○ 7
  • ○ 2026
Die Regel verlangt mindestens eine Ziffer, danach beliebig viele weitere. „7" und „2026" sind ableitbar, das leere Wort nicht.
Wahr / Falsch #3 15s ▶ Testen

Zwei verschiedene Grammatiken können genau dieselbe Sprache erzeugen.

✓ Wahr
Richtig — die Sprache ist die Wortmenge, die Grammatik nur ein Regelwerk dafür. Verschiedene Regelwerke können dieselbe Menge erzeugen.