🧠 Thema 7: Theoretische Informatik – formale Sprachen und Automatentheorie

Überblick

In diesem Themenbereich geht es darum, wie Computer Eingaben nach klaren Regeln verarbeiten, Muster erkennen, Ausgaben erzeugen und Sprachen formal beschreiben können.

Du solltest nach der Wiederholung erklären können,

• was formale Sprachen sind,
• warum natürliche Sprache für Computer schwieriger ist als formale Sprache,
• wie endliche Automaten Wörter erkennen,
• worin sich akzeptierende Automaten und Mealy-Automaten unterscheiden,
• was deterministisch und nichtdeterministisch bedeutet,
• wie man einfache Automaten testet und als Übergangstabelle beschreibt,
• wie man einen NEA mithilfe der Potenzmengenkonstruktion in einen DEA überführt,
• wie Grammatiken Wörter oder Sätze erzeugen,
• wie Grammatiken und Automaten zusammenhängen,
• und warum endliche Automaten manche Sprachen nicht erkennen können.

Leitfrage

Wie kann ein Computer mit endlich vielen Zuständen entscheiden, ob eine Eingabe gültig ist – und wo liegen die Grenzen dieses Modells?

Automaten im Alltag

Abb.: Automaten können als Blackbox betrachtet werden: Man beobachtet Eingabe und Ausgabe, aber nicht unmittelbar die Verarbeitung im Inneren.

Automaten begegnen dir im Alltag häufig: bei Ticketautomaten, Aufzügen, Ampeln, Waschmaschinen, Paketstationen, Getränkeautomaten, Loginformularen oder Prüfprogrammen für Codes.

Ein Automat verarbeitet Eingaben nicht „frei“, sondern nach vorher festgelegten Regeln. Er befindet sich immer in einem bestimmten Zustand. Eine Eingabe kann dann einen Zustandsübergang auslösen.

Merke

Ein Automat setzt sich aus Zuständen und Zustandsübergängen zusammen. Er befindet sich zu jedem Zeitpunkt in genau einem aktuellen Zustand.

Beispiel: Ticketautomat als akzeptierender Automat

Abb.: Vereinfachtes Automatenmodell: Nur eine sinnvoll abgeschlossene Eingabefolge führt in den Endzustand.

Ein vereinfachter Ticketautomat kann so modelliert werden:

Zustand	Bedeutung
q0	Automat wartet auf Geld
q1	Geld wurde eingeworfen
q2	Ticket wurde bestätigt
q3	Ticket wird gedruckt
q4	Ticket wurde entnommen; Vorgang ist abgeschlossen

Eine Eingabefolge wird akzeptiert, wenn der Automat nach dem vollständigen Lesen der Eingabe in einem Endzustand landet.

Beispiele:

Eingabefolge	Ergebnis
Münze → Bestätigen → Drucken → Entnahme	akzeptiert
Bestätigen → Münze → Entnahme	abgelehnt
Münze → Entnahme	abgelehnt

Wichtig

Das Modell ist bewusst vereinfacht. Ein echter Automat müsste zusätzlich mit Abbruch, falschen Münzen, Karten, Zeitüberschreitung, Störungen oder Wechselgeld umgehen.

Formale Sprachen

Eine formale Sprache ist eine Menge von Wörtern, die nach genau festgelegten Regeln aus Zeichen eines Alphabets gebildet werden.

Alphabet, Wort und Sprache

Begriff	Bedeutung	Beispiel
Alphabet	Menge erlaubter Zeichen	Σ = {a, b}
Wort	endliche Folge von Zeichen aus dem Alphabet	abba
leeres Wort	Wort ohne Zeichen	ε
Sprache	Menge erlaubter Wörter	L = {a, ab, abb}

Merke

In der theoretischen Informatik bedeutet „Sprache“ nicht unbedingt Deutsch, Englisch oder Französisch. Eine Sprache kann auch aus gültigen Inventarcodes, gültigen Dateinamen, zulässigen Emoticons oder syntaktisch korrekten Programmtexten bestehen.

Beispiele formaler Sprachen

Sprache	Beschreibung
Wörter über {0,1} mit gerader Anzahl an 1	z. B. ``, 11, 1010
vierstellige Inventarcodes	genau vier Ziffern, z. B. 1010, 9020, 8010
einfache Variablennamen in Python	Buchstabe oder _ am Anfang, danach Buchstaben, Ziffern oder _
Dateinamen mit Endung .zip	z. B. archiv.zip, fotos2026.zip
einfache Emoticons	z. B. :), :-D, ;-)

Wichtig

Ob ein Wort zu einer formalen Sprache gehört, hängt nur von den festgelegten Regeln ab. Es geht nicht darum, ob ein Wort „schön“, „sinnvoll“ oder alltagssprachlich passend klingt.

Natürliche Sprache, Syntax und Semantik

Natürliche Sprachen wie Deutsch sind vieldeutig, unvollständig, kontextabhängig und oft trotzdem verständlich.

Formale Sprachen müssen dagegen eindeutig, präzise und maschinell überprüfbar sein.

Natürliche Sprache	Formale Sprache
kann mehrdeutig sein	soll eindeutig sein
lebt von Kontext, Betonung und Weltwissen	folgt expliziten Regeln
Fehler werden oft trotzdem verstanden	kleine Fehler können die Verarbeitung verhindern
Bedeutung kann unterschiedlich interpretiert werden	Syntax muss exakt passen

Mehrdeutigkeit in natürlicher Sprache

Ich warte neben der Bank.

„Bank“ kann ein Sitzmöbel oder ein Geldinstitut sein.

Wir essen jetzt Opa!
Wir essen jetzt, Opa!

Die Zeichensetzung verändert die Bedeutung stark.

Syntax und Semantik

Begriff	Bedeutung	Beispiel
Syntax	Ist die Eingabe formal korrekt aufgebaut?	print("Hallo") ist syntaktisch korrekt
Semantik	Was bedeutet oder bewirkt die Eingabe?	Es wird der Text Hallo ausgegeben

Ein Programm kann syntaktisch korrekt sein, aber semantisch etwas Falsches tun.

alter = 17
print("Du bist", alter + 10, "Jahre alt.")

Der Code ist formal ausführbar. Inhaltlich könnte die Ausgabe aber falsch oder unerwünscht sein.

Merke

Automaten und Grammatiken prüfen zunächst vor allem formale Strukturen. Ob eine Eingabe inhaltlich sinnvoll ist, ist eine zusätzliche Frage.

Endliche Automaten

Abb.: DEA für Wörter mit gerader Anzahl an `1`: Eine `1` wechselt den Zustand, eine `0` nicht.

Ein endlicher Automat ist ein Modell, das Eingaben Zeichen für Zeichen verarbeitet und dabei zwischen endlich vielen Zuständen wechselt.

Am Ende entscheidet der Automat, ob die Eingabe akzeptiert oder abgelehnt wird.

Grundidee

Ein Automat besitzt:

• eine endliche Menge von Zuständen,
• ein Eingabealphabet,
• einen Startzustand,
• Übergangsregeln,
• akzeptierende Endzustände.

Er liest ein Wort von links nach rechts. Nach jedem Zeichen wechselt er je nach aktuellem Zustand und gelesenem Zeichen in einen neuen Zustand.

Merke

Ein endlicher Automat hat kein unbegrenztes Gedächtnis. Er „merkt“ sich nur seinen aktuellen Zustand.

Zustandsdiagramm und Übergangstabelle

Ein Automat kann als Zustandsdiagramm dargestellt werden. Dabei gilt:

Darstellung	Bedeutung
Kreis	Zustand
Pfeil ohne vorherigen Zustand	Startzustand
doppelt umrandeter Kreis	akzeptierender Endzustand
Pfeil zwischen Zuständen	Zustandsübergang
Beschriftung am Pfeil	Eingabe, die den Übergang auslöst

Zusätzlich kann derselbe Automat als Übergangstabelle beschrieben werden.

aktueller Zustand	Eingabe 0	Eingabe 1
q0	q0	q1
q1	q1	q0

Die Tabelle zeigt denselben Informationsgehalt wie das Diagramm: aktueller Zustand plus Eingabe ergeben den Folgezustand.

Formales 5-Tupel eines endlichen Automaten

Ein endlicher Automat kann als 5-Tupel beschrieben werden:

EA = (Q, Σ, δ, q0, E)

Bestandteil	Ausgesprochen	Bedeutung
Q	Zustandsmenge	alle möglichen Zustände
Σ	Sigma	Eingabealphabet
δ	Delta	Übergangsfunktion bzw. Übergangsrelation
q0	Startzustand	Zustand, in dem die Verarbeitung beginnt
E	Endzustände	akzeptierende Zustände

Aussprache

Σ spricht man „Sigma“, δ spricht man „Delta“. Beim Erklären ist wichtiger, dass du die Bedeutung erklären kannst, als dass du die Symbole perfekt formal notierst.

Beispiel: Wörter mit gerader Anzahl an 1

Wir betrachten Wörter über dem Alphabet:

Σ = {0, 1}

Der Automat soll akzeptieren, wenn die Anzahl der 1-Zeichen gerade ist.

Zustand	Bedeutung
q0	bisher gerade Anzahl an 1 gelesen
q1	bisher ungerade Anzahl an 1 gelesen

q0 ist Startzustand und Endzustand. Das leere Wort ε wird daher ebenfalls akzeptiert.

Wort	Ablauf	Ergebnis
0	q0 → q0	akzeptiert
1	q0 → q1	abgelehnt
101	q0 → q1 → q1 → q0	akzeptiert
111	q0 → q1 → q0 → q1	abgelehnt

Merke

Ein Automat erkennt nicht „die Bedeutung“ eines Wortes. Er prüft, ob das Wort nach seinen Regeln in einem akzeptierenden Zustand endet.

📝 Übung: Automat testen

Teste folgende Wörter:

a
b
ab
ba
abb
baba

Bearbeite:

1. Notiere die Zustandsfolge für jedes Wort.
2. Entscheide jeweils: akzeptiert oder abgelehnt?
3. Formuliere die Sprache des Automaten in einem Satz.

Lösungshinweis

Akzeptiert werden Wörter, die mit b enden.

a     → abgelehnt
b     → akzeptiert
ab    → akzeptiert
ba    → abgelehnt
abb   → akzeptiert
baba  → abgelehnt

Deterministische endliche Automaten: DEA

Start → q0 --Ziffer--> q1 --Ziffer--> q2 --Ziffer--> q3 --Ziffer--> q4*
Weitere Ziffern oder falsche Zeichen führen in einen Fehlerzustand.

Ein deterministischer endlicher Automat ist ein endlicher Automat, bei dem für jeden Zustand und jedes Eingabezeichen genau ein Folgezustand festgelegt ist.

Merke

Deterministisch bedeutet: Bei gleicher Eingabe und gleichem Zustand ist der nächste Schritt eindeutig festgelegt.

Eigenschaften eines DEA

Eigenschaft	Erklärung
eindeutige Übergänge	pro Zustand und Eingabezeichen genau ein Folgezustand
kein Raten	der Automat hat immer nur einen möglichen Weg
gut implementierbar	lässt sich direkt mit Tabellen, if-Abfragen oder Schleifen programmieren
effizient prüfbar	jedes Zeichen wird einmal verarbeitet

Beispiel: Schul-ID-Prüfung

Eine einfache Regel könnte lauten:

Eine gültige Schul-ID besteht aus dem Muster S-DDD, zum Beispiel S-123.

Der Automat zählt nicht im mathematischen Sinn unbegrenzt, sondern besitzt feste Zustände für die bereits gelesenen Bestandteile.

Abb.: Ein DEA kann einfache feste Muster wie eine Schul-ID zuverlässig prüfen.

Zustand	Bedeutung
q0	noch kein Zeichen gelesen
q1	S wurde gelesen
q2	Bindestrich wurde gelesen
q3	eine Ziffer wurde gelesen
q4	zwei Ziffern wurden gelesen
q5	drei Ziffern wurden gelesen; akzeptierend
qF	Fehlerzustand

Dabei sind die Kanten bewusst präzise beschriftet:

• S bedeutet: Die Eingabe beginnt mit dem festen Anfangszeichen.
• - bedeutet: Danach muss ein Bindestrich folgen.
• 0–9 bedeutet: Es wurde eine Ziffer gelesen.
• Falsche Zeichen oder zusätzliche Zeichen führen in den Fehlerzustand.
• Akzeptiert wird nur dann, wenn die Eingabe genau dem Muster entspricht.

Merke

Für Validierungen mit fester Länge und festem Zeichenvorrat eignet sich ein DEA sehr gut.

Vollständiger und unvollständiger Automat

Ein DEA heißt vollständig, wenn für jeden Zustand und jedes Zeichen des Eingabealphabets ein Übergang definiert ist.

Fehlerzustände werden oft als Fehlersenke modelliert: Ist der Automat dort angekommen, kommt er nicht mehr zu einem akzeptierenden Zustand zurück.

In manchen Darstellungen werden nicht zielführende Übergänge weggelassen. Dann wirkt das Diagramm übersichtlicher, ist aber formal nicht mehr vollständig.

Weitere DEA-Beispiele

Teilwort 010 erkennen

Abb.: Korrektes vollständiges DEA-Modell für das Teilwort `010`: In jedem Zustand gibt es für `0` und `1` genau einen Folgezustand.

Ein Automat kann auch prüfen, ob ein bestimmtes Teilwort irgendwo vorkommt.

Beispiele:

Wort	enthält 010?
010	ja
1010	ja
0110	nein
00010	ja

Die Zustände bedeuten dabei:

Zustand	Bedeutung
q0	vom Muster 010 passt aktuell kein Anfang
q1	zuletzt wurde ein passender Anfang 0 gelesen
q2	zuletzt wurde ein passender Anfang 01 gelesen
q3	das Teilwort 010 wurde bereits gefunden

Die Übergänge sind deterministisch: Von jedem Zustand gibt es für 0 und für 1 genau einen Folgezustand.

Beispiel: gerade Anzahl von Warnzeichen

Ein anderes Beispiel für einen endlichen Automaten ist eine einfache Protokollprüfung: Ein Wort über dem Alphabet {!, ok} ist gültig, wenn eine gerade Anzahl an Warnzeichen ! vorkommt.

Der Automat muss nicht die ganze Eingabe speichern. Er merkt sich nur, ob bisher eine gerade oder ungerade Anzahl an Warnzeichen gelesen wurde.

gerade --!--> ungerade
ungerade --!--> gerade
gerade --ok--> gerade
ungerade --ok--> ungerade

Das zeigt die zentrale Idee endlicher Automaten: Zustände speichern nur die Information, die für die Entscheidung nötig ist.

📝 Übung: Eigene Validierung entwerfen

Entwirf grob einen Automaten für Mediencodes einer Schulbibliothek nach folgendem Muster:

zwei Großbuchstaben + Bindestrich + drei Ziffern

Beispiele:

BU-105
CD-042
VR-999

Nicht gültig:

B-105
BU105
bu-105
BU-10A
BU-1057

Bearbeite:

1. Gib das Alphabet bzw. die benötigten Zeichenklassen an.
2. Beschreibe die Zustände in Worten.
3. Markiere den akzeptierenden Zustand.
4. Erkläre, warum ein DEA hier ausreicht.

Lösungshinweis

Man kann Zustände für „0 Zeichen gelesen“, „1 Großbuchstabe“, „2 Großbuchstaben“, „Bindestrich gelesen“, „1 Ziffer“, „2 Ziffern“, „3 Ziffern“ und einen Fehlerzustand verwenden. Der Zustand nach genau zwei Großbuchstaben, Bindestrich und drei Ziffern ist akzeptierend.

Nichtdeterministische endliche Automaten: NEA

Abb.: NEA für das Teilwort `aba`: Bei `q0` und Eingabe `a` sind zwei Folgezustände möglich.

Ein nichtdeterministischer endlicher Automat kann bei gleichem Zustand und gleicher Eingabe mehrere mögliche Folgezustände besitzen.

Das bedeutet nicht, dass der Computer „zufällig“ arbeitet. Es ist ein theoretisches Modell: Ein Wort wird akzeptiert, wenn mindestens ein möglicher Pfad nach dem vollständigen Lesen in einem Endzustand landet.

DEA und NEA im Vergleich

Aspekt	DEA	NEA
Folgezustand	eindeutig	mehrere Möglichkeiten möglich
Übergänge	Funktion	Relation
Darstellung	oft größer	oft kompakter
Implementierung	direkt	meist Umwandlung in DEA oder Simulation mehrerer Zustände
Akzeptanz	ein eindeutiger Pfad endet akzeptierend	mindestens ein möglicher Pfad endet akzeptierend

Merke

Ein NEA kann kompakter sein, weil er mögliche Wege nicht schon im Diagramm vollständig auseinanderziehen muss.

Übergangstabelle mit Mengen

Bei einem NEA stehen in der Übergangstabelle oft Mengen von Zuständen.

Beispiel für den NEA, der aba irgendwo erkennt:

Zustand	Eingabe a	Eingabe b
q0	{q0, q1}	{q0}
q1	∅	{q2}
q2	{q3}	∅
q3	{q3}	{q3}

∅ bedeutet: Von diesem Zustand aus gibt es mit dieser Eingabe keinen passenden Übergang.

Epsilon-Übergänge

Manche NEA verwenden zusätzlich Epsilon-Übergänge. Ein ε-Übergang ist ein Übergang ohne Eingabezeichen.

Das bedeutet: Der Automat darf automatisch in einen anderen Zustand wechseln, ohne ein Zeichen des Eingabewortes zu verbrauchen.

Wichtig

ε ist hier nicht „ein normales Zeichen“, das in der Eingabe steht. Es bezeichnet einen Übergang ohne gelesene Eingabe.

📝 Übung: NEA nachvollziehen

Ein NEA über {a,b} erkennt Wörter, in denen irgendwo aba vorkommt.

Teste:

aba
baba
aabb
abab
bbb

Bearbeite:

1. Welche Wörter werden akzeptiert?
2. Warum darf baba akzeptiert werden, obwohl es nicht mit a beginnt?
3. Warum ist ein NEA für solche Suchmuster oft übersichtlich?

Lösungshinweis

Akzeptiert werden aba, baba und abab, weil jeweils irgendwo das Teilwort aba vorkommt.

baba wird akzeptiert, weil der Automat in q0 weiterlaufen kann, bis ein möglicher Start des Musters gefunden wird.

Potenzmengenkonstruktion

Abb.: Prinzip der Potenzmengenkonstruktion: mögliche NEA-Zustände werden zu Sammelzuständen eines DEA.

Jeder NEA kann in einen äquivalenten DEA überführt werden. Das geschieht mithilfe der Potenzmengenkonstruktion, auch Teilmengenkonstruktion genannt.

Die Grundidee:

• Ein NEA kann mehrere mögliche aktuelle Zustände haben.
• Der DEA fasst diese Möglichkeiten zu einem neuen Sammelzustand zusammen.
• Ein DEA-Zustand kann also eine Menge von NEA-Zuständen sein, z. B. {q0, q1}.

Vorgehen

1. Beginne mit der Startzustandsmenge, z. B. {q0}.
2. Berechne für jedes Eingabezeichen alle möglichen Folgezustände.
3. Jede neu auftretende Zustandsmenge wird ein neuer DEA-Zustand.
4. Wiederhole das, bis keine neuen Zustandsmengen mehr entstehen.
5. Markiere alle Zustandsmengen als akzeptierend, die mindestens einen akzeptierenden NEA-Zustand enthalten.

Mini-Beispiel

Gegeben sei ein NEA:

NEA-Zustand	a	b
q0	{q0, q1}	{q0}
q1	∅	{q2}
q2	{q2}	{q2}

Startzustand: q0
Endzustand: q2

Ein Beginn der Potenzmengenkonstruktion:

DEA-Zustand	a	b
{q0}	{q0, q1}	{q0}
{q0, q1}	{q0, q1}	{q0, q2}
{q0, q2}	{q0, q1, q2}	{q0, q2}
{q0, q1, q2}	{q0, q1, q2}	{q0, q2}

Akzeptierend sind alle Zustandsmengen, die q2 enthalten.

Merke

Die Potenzmengenkonstruktion macht den Automaten deterministisch. Dafür kann die Anzahl der Zustände steigen.

Mealy-Automaten

Ein Mealy-Automat ist ein Automat mit Ausgabe. Er entscheidet nicht nur am Ende „akzeptiert“ oder „abgelehnt“, sondern erzeugt während der Verarbeitung eine Ausgabe.

Bei einem Mealy-Automaten hängt die Ausgabe vom aktuellen Zustand und vom gelesenen Eingabezeichen ab.

Unterschied zu akzeptierenden Automaten

Aspekt	Endlicher Automat	Mealy-Automat
Hauptzweck	Eingaben erkennen	Eingaben verarbeiten und Ausgaben erzeugen
Ergebnis	akzeptiert oder abgelehnt	Ausgabezeichen oder Ausgabeaktionen
Endzustände	wichtig	nicht zwingend im gleichen Sinn
typische Anwendung	Validierung, Mustererkennung	Steuerungen, Bedienfelder, Rückmeldungen

Merke

Ein akzeptierender Automat beantwortet die Frage: „Gehört diese Eingabe zur Sprache?“
Ein Mealy-Automat beantwortet eher: „Welche Ausgabe entsteht bei dieser Eingabe?“

Formales Tupel eines Mealy-Automaten

In dieser Lernseite wird ein Mealy-Automat als 7-Tupel notiert:

M = (Q, Σ, q0, δ, λ, Ω, E)

Bestandteil	Ausgesprochen	Bedeutung
Q	Zustandsmenge	alle möglichen Zustände
Σ	Sigma	Eingabealphabet
q0	Startzustand	Zustand, in dem die Verarbeitung beginnt
δ	Delta	Übergangsfunktion
λ	Lambda	Ausgabefunktion
Ω	Omega	Ausgabealphabet
E	Endzustände	je nach Modellierung mögliche Endzustände

Aussprache

λ spricht man „Lambda“, Ω spricht man „Omega“.

Beispiel: Schließfach-Code als Mealy-Automat

Abb.: Vollständiger Mealy-Automat für den Code `274`: Falsche Ziffern führen aus jedem Zwischenzustand in den Fehlerzustand.

Ein Schließfach öffnet sich beim Code 274. Nach jeder richtigen Ziffer gibt es eine Rückmeldung. Bei einer falschen Ziffer führt das Modell in einen Fehlerzustand:

Ausgabe	Bedeutung
L1	erste Ziffer richtig
L2	zweite Ziffer richtig
öffnen	Code vollständig richtig, Fach öffnet
Fehler	falsche Eingabe

Die Kantenbeschriftung folgt dem Muster:

Eingabe / Ausgabe

Beispiel:

2 / I

Das bedeutet: Wenn im aktuellen Zustand die Eingabe 2 kommt, wechselt der Automat in den nächsten Zustand und gibt L1 aus.

In diesem Modell führt jede falsche Ziffer sofort in den Fehlerzustand qF. Nach dem Öffnen (q3) wird jede weitere Eingabe ebenfalls als Fehler behandelt. Das ist eine Modellierungsentscheidung, damit das Eingabeverhalten vollständig und eindeutig beschrieben ist.

📝 Übung: Mealy-Automat nachvollziehen

Betrachte den Schließfach-Automaten mit Code 274.

Bearbeite:

1. Welche Ausgaben entstehen bei der Eingabe 274?
2. Welche Ausgabe entsteht, wenn die Eingabe mit 2, dann 9 beginnt?
3. Warum ist das Modell ein Mealy-Automat und kein bloßer akzeptierender Automat?
4. Welche Vereinfachungen enthält dieses Modell?

Lösungshinweis

Bei 274 entstehen die Ausgaben L1, L2, öffnen.

Bei 29 entsteht zuerst L1, dann Fehler. Danach bleibt der Automat in der Fehlersenke.

Das Modell ist ein Mealy-Automat, weil es während der Verarbeitung Rückmeldungen erzeugt und nicht nur am Ende akzeptiert oder ablehnt.

Grammatiken

Eine Grammatik beschreibt, wie gültige Wörter oder Sätze einer Sprache gebildet werden können.

Sie besteht aus:

• Nichtterminalsymbolen,
• Terminalsymbolen,
• einem Startsymbol,
• Produktionsregeln.

Formal kann eine Grammatik als 4-Tupel beschrieben werden:

G = (N, T, S, P)

Bestandteil	Bedeutung
N	Menge der Nichtterminalsymbole
T	Menge der Terminalsymbole
S	Startsymbol
P	Menge der Produktionsregeln

Terminale und Nichtterminale

Begriff	Bedeutung	Beispiel
Terminalsymbol	kommt im fertigen Wort/Satz vor	la, le, lu
Nichtterminalsymbol	Platzhalter, der noch ersetzt werden muss	S, A, B
Produktion	Regel zur Ersetzung	S → laA
Startsymbol	Ausgangspunkt der Ableitung	S

Merke

Terminale sind die fertigen Zeichen, Wörter oder Silben. Nichtterminale sind Bauplanteile, die noch weiter ersetzt werden.

Ableitung einer Silbensprache

Abb.: Ableitung: `S → laA → laleB → lalelu`.

Eine einfache Sprache kann aus dreisilbigen Wörtern bestehen. Erlaubte Silben sind la, le, lu. Die letzte Silbe muss lu sein.

N = {S, A, B}
T = {la, le, lu}
Startsymbol = S

P:
S → laA | leA | luA
A → laB | leB | luB
B → lu

Das Wort lalelu lässt sich ableiten:

S
→ laA
→ laleB
→ lalelu

Das Wort lale lässt sich mit dieser Grammatik nicht fertig ableiten, weil am Ende noch ein Nichtterminal stehen müsste bzw. die letzte Silbe lu fehlt.

📝 Übung: Grammatik anwenden

Gegeben ist folgende Grammatik:

<Satz> → <Nominalphrase> <Verbalphrase>
<Nominalphrase> → <Name> | <Artikel> <Nomen>
<Verbalphrase> → <Verb> | <Verb> <Nominalphrase>
<Name> → Mila | Oskar | Zeynep
<Artikel> → der | die | das
<Nomen> → Roboter | Ball | Rucksack | Tablet
<Verb> → findet | bewegt | trägt | holt

Bearbeite:

1. Nenne alle Nichtterminalsymbole.
2. Nenne mindestens fünf Terminalsymbole.
3. Leite den Satz Mila findet das Tablet ab.
4. Erzeuge einen syntaktisch korrekten, aber inhaltlich ungewöhnlichen Satz.
5. Erkläre, warum eine Grammatik syntaktisch korrekte, aber semantisch seltsame Sätze erzeugen kann.

Lösungshinweis

Nichtterminalsymbole sind z. B. <Satz>, <Nominalphrase>, <Verbalphrase>, <Name>, <Artikel>, <Nomen>, <Verb>.

Eine mögliche Ableitung:

<Satz>
→ <Nominalphrase> <Verbalphrase>
→ <Name> <Verbalphrase>
→ Mila <Verbalphrase>
→ Mila <Verb> <Nominalphrase>
→ Mila findet <Nominalphrase>
→ Mila findet <Artikel> <Nomen>
→ Mila findet das Tablet

Ein syntaktisch korrekter, aber ungewöhnlicher Satz wäre z. B. der Ball trägt das Tablet oder der Rucksack bewegt den Roboter.

Reguläre Grammatiken und Automaten

Abb.: Eine reguläre Grammatik und ein DEA können dieselbe Sprache beschreiben.

Eine reguläre Grammatik ist besonders eingeschränkt. Bei einer rechtsregulären Grammatik steht links genau ein Nichtterminal. Rechts steht entweder:

N → ε
N → T
N → TN

Das bedeutet vereinfacht:

• Ein Nichtterminal kann verschwinden.
• Ein Nichtterminal kann durch ein Terminal ersetzt werden.
• Ein Nichtterminal kann durch ein Terminal und ein folgendes Nichtterminal ersetzt werden.

Merke

Eine Sprache ist regulär, wenn sie durch eine reguläre Grammatik erzeugt werden kann. Äquivalent gilt: Eine Sprache ist regulär, wenn es einen endlichen Automaten gibt, der sie erkennt.

Verbindung zur Wortanalyse

Ein DEA erkennt ein Wort, indem er eine Zustandsfolge durchläuft.

Eine Grammatik erzeugt ein Wort, indem sie Produktionsregeln anwendet.

Beide Perspektiven können dieselbe Sprache beschreiben:

Automat	Grammatik
erkennt gültige Wörter	erzeugt gültige Wörter
Zustände und Übergänge	Nichtterminale und Produktionen
Wort wird gelesen	Wort wird abgeleitet

Chomsky-Hierarchie und Grenzen

Abb.: Reguläre Sprachen sind die am stärksten eingeschränkte Klasse innerhalb der Chomsky-Hierarchie.

Die Chomsky-Hierarchie ordnet formale Sprachen danach, welche Art von Grammatik sie erzeugen kann.

Typ	Sprachklasse	Grobe Einordnung
Typ 3	regulär	durch endliche Automaten erkennbar
Typ 2	kontextfrei	kann z. B. Klammerstrukturen beschreiben
Typ 1	kontextsensitiv	stärker, aber komplexer
Typ 0	rekursiv aufzählbar	sehr allgemeine Klasse

Für Thema 7 ist vor allem wichtig:

• Endliche Automaten erkennen reguläre Sprachen.
• Manche Sprachen benötigen mehr Speicher als ein endlicher Automat besitzt.
• Kellerautomaten besitzen zusätzlichen Stapelspeicher und können bestimmte kontextfreie Sprachen erkennen.

Grenzen endlicher Automaten

Endliche Automaten haben nur endlich viele Zustände. Deshalb können sie sich nicht beliebig viel merken.

Ein typisches Grenzbeispiel ist eine Sprache mit korrekt geschachtelten Klammern. Beispiele sind:

()
(())
(()())
((()))

Abb.: Beliebig geschachtelte Klammern benötigen ein Gedächtnis wie einen Stapel.

Die Regel lautet: Jede öffnende Klammer muss später wieder geschlossen werden, und die Reihenfolge muss stimmen.

Ein endlicher Automat kann diese Sprache nicht allgemein erkennen, weil er sich für beliebig tiefe Verschachtelung merken müsste, wie viele Klammern noch offen sind. Dafür reicht eine feste endliche Anzahl von Zuständen nicht aus.

Merke

Ein endlicher Automat besitzt kein unbegrenztes Gedächtnis. Für beliebig tief geschachtelte Strukturen braucht man ein stärkeres Modell, z. B. einen Kellerautomaten.

Kellerautomat

Ein Kellerautomat besitzt zusätzlich einen Speicher, der wie ein Stapel funktioniert.

Vereinfacht:

1. Für jede öffnende Klammer wird ein Symbol auf den Stapel gelegt.
2. Für jede schließende Klammer wird ein Symbol vom Stapel genommen.
3. Am Ende wird akzeptiert, wenn der Stapel passend leer ist und nie zu früh eine schließende Klammer erscheint.

Modell	Gedächtnis
endlicher Automat	nur aktueller Zustand
Kellerautomat	aktueller Zustand plus Stapel
Turingmaschine	allgemeineres Speicherband

📝 Übung: Grenzen erkennen

Beurteile, ob ein endlicher Automat für die folgenden Validierungen grundsätzlich ausreicht.

Validierung	Reicht ein endlicher Automat?	Begründung
eine Schul-ID hat das Muster S-DDD
ein Wort endet mit ing
ein Klammerausdruck enthält beliebig tief korrekt geschachtelte Klammern
Klammern sind beliebig tief korrekt geschachtelt
ein Dateiname endet mit .zip

Lösungshinweis

Ein endlicher Automat reicht für feste Muster wie vier Ziffern, Endung ing oder .zip.

Für beliebig tief geschachtelte Klammern reicht ein endlicher Automat nicht, weil unbegrenzt gemerkt werden müsste, wie viele Klammern noch offen sind. Dafür braucht man ein Modell mit zusätzlichem Speicher, etwa einen Kellerautomaten.

Warum Grammatiken für Programmiersprachen wichtig sind

Abb.: Vom Quellcode zur Ausführung: Formale Regeln ermöglichen maschinelle Prüfung.

Programmiersprachen sind formale Sprachen. Ein Computer kann ein Programm nur dann sinnvoll verarbeiten, wenn der Quellcode nach den Regeln der Sprache aufgebaut ist.

Vereinfacht läuft die Verarbeitung so ab:

1. Quellcode: Der Mensch schreibt Programmtext.
2. Lexikalische Analyse: Zeichen werden zu sinnvollen Einheiten zusammengefasst, z. B. Schlüsselwörter, Namen, Zahlen.
3. Syntaxanalyse: Die Struktur wird anhand einer Grammatik geprüft.
4. Semantische Analyse: Es wird geprüft, ob die Bedeutung im Kontext passt, z. B. Typen, Namen, Gültigkeitsbereiche.
5. Ausführung / Übersetzung: Das Programm wird interpretiert oder in maschinennahe Befehle übersetzt.

Wichtig

Schon kleine Syntaxfehler können verhindern, dass ein Programm ausgeführt wird. Menschen können oft erraten, was gemeint war; Compiler und Interpreter brauchen präzise Regeln.

Prüfungsvorbereitung

Die folgenden Aufgaben trainieren dieselben Kompetenzen, verwenden aber andere Kontexte, Daten und Beispiele.

📝 Übung: Automatenmodell im Alltag

Ein Paketabholfach funktioniert vereinfacht so:

1. Kund·in scannt einen Abholcode.
2. Das System prüft, ob der Code gültig ist.
3. Bei gültigem Code öffnet sich ein Fach.
4. Nach der Entnahme wird das Fach wieder verriegelt.

Bearbeite:

1. Beschreibe passende Zustände.
2. Beschreibe sinnvolle Zustandsübergänge.
3. Entscheide, welche Eingabefolge akzeptiert werden sollte.
4. Begründe, welche Vereinfachungen dein Modell enthält.

📝 Übung: DEA testen

Ein DEA über {0,1} akzeptiert Wörter, die das Teilwort 010 enthalten.

Teste:

010
1010
0110
00010
111

Bearbeite:

1. Welche Wörter werden akzeptiert?
2. Welche Information muss der Automat höchstens speichern?
3. Warum braucht der Automat kein unbegrenztes Gedächtnis?

Lösungshinweis

Akzeptiert werden 010, 1010 und 00010.

Der Automat muss nur speichern, wie viel vom Muster 010 zuletzt bereits erkannt wurde. Dafür reichen endlich viele Zustände.

📝 Übung: NEA in DEA überführen

Ein NEA erkennt Wörter über {a,b}, in denen irgendwo aba vorkommt.

NEA-Zustand	Eingabe a	Eingabe b
q0	{q0, q1}	{q0}
q1	∅	{q2}
q2	{q3}	∅
q3	{q3}	{q3}

Startzustand: q0
Endzustand: q3

Bearbeite:

1. Beginne die Potenzmengenkonstruktion mit {q0}.
2. Fülle die Übergänge für alle erreichbaren Zustandsmengen aus.
3. Markiere die akzeptierenden Zustandsmengen.
4. Erkläre, warum der entsprechende DEA deterministisch ist.

Lösungshinweis

Ein möglicher Beginn:

DEA-Zustand	a	b
{q0}	{q0, q1}	{q0}
{q0, q1}	{q0, q1}	{q0, q2}
{q0, q2}	{q0, q1, q3}	{q0}
{q0, q1, q3}	{q0, q1, q3}	{q0, q2, q3}

Akzeptierend sind alle Zustandsmengen, die q3 enthalten.

📝 Übung: Grammatik ableiten

Gegeben ist eine kleine Grammatik für dreisilbige Wörter:

S → maA | miA | moA
A → maB | miB | moB
B → mo

Bearbeite:

1. Leite mamimo ab.
2. Prüfe, ob mima zur Sprache gehört.
3. Nenne alle Terminale und Nichtterminale.
4. Erkläre, warum es sich um eine rechtsreguläre Grammatik handelt.

Lösungshinweis

Eine Ableitung für mamimo:

S → maA → mamiB → mamimo

mima gehört nicht zur Sprache, weil nur zwei Silben vorhanden sind und die letzte Regel B → mo erzwingt.

📝 Übung: Mealy-Automat erklären

Ein Snackautomat gibt nach zwei gültigen Schritten Rückmeldungen aus:

• Eingabe K bedeutet Karte erkannt.
• Eingabe S bedeutet Snack ausgewählt.
• Ausgabe OK1 bedeutet: Karte akzeptiert.
• Ausgabe SNACK bedeutet: Snack wird ausgegeben.
• Ausgabe ERR bedeutet: falsche Reihenfolge oder ungültige Eingabe.

Bearbeite:

1. Skizziere einen passenden Mealy-Automaten.
2. Beschreibe Eingabealphabet und Ausgabealphabet.
3. Erkläre, warum die Ausgabe auf den Übergängen liegt.
4. Vergleiche das Modell mit einem akzeptierenden Automaten.

📝 Übung: Grenzen endlicher Automaten erklären

Erkläre, warum ein endlicher Automat folgende Sprache nicht allgemein erkennen kann:

L = { 0ⁿ1ⁿ | n ≥ 1 }

Gehe ein auf:

1. was der Automat zählen müsste,
2. warum endlich viele Zustände nicht ausreichen,
3. welches Modell mit zusätzlichem Speicher besser geeignet wäre.

Lösungshinweis

Der Automat müsste sich merken, wie viele 0 gelesen wurden, um danach genau gleich viele 1 zu prüfen. Da n beliebig groß sein kann, reicht eine feste endliche Anzahl an Zuständen nicht aus. Ein Kellerautomat kann mit einem Stapel arbeiten und pro 0 ein Symbol speichern, das bei den 1 wieder entfernt wird.

Ich kann …

Nach der Wiederholung dieses Themenbereichs solltest du Folgendes können:

• Ich kann erklären, was eine formale Sprache ist.
• Ich kann Alphabet, Wort, leeres Wort und Sprache unterscheiden.
• Ich kann erklären, warum natürliche Sprachen mehrdeutig sein können.
• Ich kann Syntax und Semantik voneinander unterscheiden.
• Ich kann den Aufbau eines endlichen Automaten als 5-Tupel erklären.
• Ich kann die Bedeutung von Q, Σ, δ, q0 und E beschreiben.
• Ich kann Zustandsdiagramme und Übergangstabellen lesen.
• Ich kann einen einfachen Automaten Schritt für Schritt mit Beispielwörtern testen.
• Ich kann erklären, wann ein Wort von einem Automaten akzeptiert wird.
• Ich kann den Unterschied zwischen DEA und NEA erklären.
• Ich kann beschreiben, was „deterministisch“ bedeutet.
• Ich kann erklären, warum ein NEA mehrere mögliche Wege haben kann.
• Ich kann begründen, warum jeder NEA in einen äquivalenten DEA überführt werden kann.
• Ich kann die Grundidee der Potenzmengenkonstruktion erklären.
• Ich kann Zustandsmengen bei der Potenzmengenkonstruktion tabellarisch darstellen.
• Ich kann erklären, was ein Mealy-Automat ist.
• Ich kann Mealy-Automaten und akzeptierende endliche Automaten vergleichen.
• Ich kann die Bestandteile eines Mealy-Automaten als 7-Tupel erklären.
• Ich kann λ als Ausgabefunktion und Ω als Ausgabealphabet einordnen.
• Ich kann Terminal- und Nichtterminalsymbole in einer Grammatik unterscheiden.
• Ich kann einfache Produktionen anwenden und Wörter oder Sätze ableiten.
• Ich kann reguläre Grammatiken grundlegend erkennen.
• Ich kann erklären, warum reguläre Grammatiken und endliche Automaten zusammenhängen.
• Ich kann erklären, warum Grammatiken für Programmiersprachen wichtig sind.
• Ich kann den Weg vom Quellcode zur Ausführung grob beschreiben.
• Ich kann erklären, warum endliche Automaten nur begrenztes Gedächtnis besitzen.
• Ich kann begründen, warum beliebig tief geschachtelte Strukturen nicht durch endliche Automaten erkannt werden können.
• Ich kann erklären, warum ein Kellerautomat durch einen Stapel mächtiger ist.
• Ich kann praktische Validierungsaufgaben nennen, für die ein DEA ausreicht.

Mini-Check

Beantworte zum Abschluss kurz:

1. Was ist eine formale Sprache?
2. Was ist ein Alphabet?
3. Was ist der Unterschied zwischen einem Wort und einer Sprache?
4. Warum ist natürliche Sprache für Computer schwieriger als formale Sprache?
5. Was ist der Unterschied zwischen Syntax und Semantik?
6. Wofür steht Q bei einem endlichen Automaten?
7. Wofür steht Σ?
8. Was beschreibt δ?
9. Wann akzeptiert ein endlicher Automat ein Wort?
10. Was bedeutet deterministisch?
11. Was unterscheidet einen DEA von einem NEA?
12. Warum kann ein NEA oft kompakter dargestellt werden?
13. Was ist ein ε-Übergang?
14. Was ist die Grundidee der Potenzmengenkonstruktion?
15. Wann ist eine Zustandsmenge im konstruierten DEA akzeptierend?
16. Was unterscheidet einen Mealy-Automaten von einem akzeptierenden Automaten?
17. Wofür steht Ω beim Mealy-Automaten?
18. Was sind Terminal- und Nichtterminalsymbole?
19. Warum sind Grammatiken für Programmiersprachen wichtig?
20. Was bedeutet „reguläre Sprache“?
21. Warum kann ein endlicher Automat beliebig tief geschachtelte Klammern nicht allgemein erkennen?
22. Welches zusätzliche Hilfsmittel besitzt ein Kellerautomat?

Kurzlösungen

1. Eine formale Sprache ist eine Menge von Wörtern, die nach genau festgelegten Regeln aus einem Alphabet gebildet werden.
2. Ein Alphabet ist die Menge der erlaubten Zeichen.
3. Ein Wort ist eine konkrete Zeichenfolge; eine Sprache ist eine Menge solcher Wörter.
4. Natürliche Sprache ist mehrdeutig, kontextabhängig und oft unvollständig; formale Sprache soll eindeutig sein.
5. Syntax betrifft die korrekte Form, Semantik die Bedeutung.
6. Q ist die Menge der Zustände.
7. Σ ist das Eingabealphabet.
8. δ beschreibt die Übergänge zwischen Zuständen.
9. Ein Wort wird akzeptiert, wenn der Automat nach vollständigem Lesen in einem Endzustand ist.
10. Deterministisch bedeutet, dass der nächste Schritt eindeutig festgelegt ist.
11. Ein DEA hat pro Zustand und Eingabezeichen genau einen Folgezustand; ein NEA kann mehrere mögliche Übergänge besitzen.
12. Weil er mögliche Wege parallel bzw. nicht eindeutig darstellen darf.
13. Ein ε-Übergang ist ein Zustandsübergang ohne gelesenes Eingabezeichen.
14. Mögliche NEA-Zustände werden zu Zustandsmengen eines DEA zusammengefasst.
15. Wenn sie mindestens einen akzeptierenden Zustand des ursprünglichen NEA enthält.
16. Ein Mealy-Automat erzeugt Ausgaben während der Verarbeitung; ein akzeptierender Automat entscheidet am Ende akzeptiert oder abgelehnt.
17. Ω ist das Ausgabealphabet.
18. Terminale erscheinen im fertigen Wort oder Satz; Nichtterminale sind Platzhalter, die ersetzt werden.
19. Sie legen eindeutig fest, welche Programmtexte syntaktisch korrekt sind.
20. Eine Sprache ist regulär, wenn sie durch eine reguläre Grammatik erzeugt bzw. durch einen endlichen Automaten erkannt werden kann.
21. Weil er sich für beliebig tiefe Verschachtelung nicht unbegrenzt merken kann, wie viele öffnende Klammern noch geschlossen werden müssen.
22. Ein Kellerautomat besitzt einen Stapel als zusätzlichen Speicher.