Formale Sprachen und Grammatiken
Was versteht man in der Informatik unter einem Alphabet?
Erklärung: Ein Alphabet ist jede endliche Zeichenmenge — etwa {0, 1} oder {a, b, …, z, @, .}. Wörter sind endliche Zeichenketten daraus.
Was ist eine formale Sprache?
Erklärung: Eine formale Sprache ist eine Wortmenge über einem Alphabet. Die Regeln — etwa eine Grammatik — entscheiden eindeutig, ob ein Wort dazugehört.
Eine formale Sprache kann unendlich viele Wörter enthalten, obwohl ihre Grammatik nur endlich viele Regeln hat.
Erklärung: Richtig — Wiederholungsregeln erzeugen beliebig lange Wörter. Endlich viele Regeln, unendlich viele Wörter — das ist gerade die Stärke von Grammatiken.
Regel für Münchner Kennzeichen (vereinfacht): „M", Bindestrich, ein bis zwei Buchstaben, ein bis vier Ziffern. Welches Kennzeichen ist wohlgeformt?
Erklärung: Nur die erste Zeichenkette folgt der Reihenfolge der Regel. Formale Regeln prüfen die Form Zeichen für Zeichen — Fast-richtig zählt nicht.
Was ist eine Grammatik im Sinn der theoretischen Informatik?
Erklärung: 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.
Ein Wort gehört genau dann zur Sprache, wenn es sich aus dem Startsymbol mit den Regeln der Grammatik ___ lässt.
Erklärung: Ableitbarkeit ist das Kriterium für Zugehörigkeit — man startet beim Startsymbol und wendet Regeln an, bis das Wort dasteht.
In der EBNF-Notation bedeuten eckige und geschweifte Klammern: [x] und {x}. Was heiĂźt das jeweils?
Erklärung: Option und Wiederholung sind die beiden Bausteine, mit denen EBNF endlich kurze Regeln für unendlich große Sprachen schreibt.
EBNF-Regel für Ganzzahlen: Zahl = Ziffer { Ziffer }. Welche Zeichenkette gehört NICHT zur Sprache?
Erklärung: Die Regel verlangt mindestens eine Ziffer, danach beliebig viele weitere. „7" und „2026" sind ableitbar, das leere Wort nicht.
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.
Erklärung: Richtig — Syntax (Form) und Semantik (Bedeutung) sind getrennte Ebenen. Formale Regeln prüfen nur die Form.
Regel einer Programmiersprache: Zuweisung = Bezeichner "=" Zahl ";". Welche Zeichenkette erkennt der Compiler als Zuweisung an?
Erklärung: 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.
Alphabet {a, b}. Die Sprache L enthält alle Wörter, die mit a beginnen und mit b enden. Welches Wort liegt in L?
Erklärung: 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.
In einer Grammatik heiĂźen die Regeln, mit denen Symbole schrittweise ersetzt werden, ___ (ein Wort).
Erklärung: Produktionsregeln (z. B. Satz → Subjekt Prädikat) ersetzen links stehende Symbole durch rechte Seiten, bis nur noch Zeichen des Alphabets dastehen.
Wozu definiert man E-Mail-Adressen oder Gleitkommazahlen ĂĽber eine formale Sprache statt ĂĽber Beispiele?
Erklärung: Beispiele lassen Grenzfälle offen; eine Grammatik entscheidet jeden Fall. Genau das braucht ein Eingabefeld, das Adressen prüfen soll.
Zwei verschiedene Grammatiken können genau dieselbe Sprache erzeugen.
Erklärung: Richtig — die Sprache ist die Wortmenge, die Grammatik nur ein Regelwerk dafür. Verschiedene Regelwerke können dieselbe Menge erzeugen.