Mit Google fortfahren
Wenn du Programmcode schreibst, prüft der Computer zuerst, ob der Text zu den Regeln der Programmiersprache passt. Ein Compiler ist ein Programm, das Quellcode übersetzt und dabei solche Regelverstöße findet. Syntaktisch korrekt heißt: Der Code ist nach den Sprachregeln richtig aufgebaut. Genau diese Art von Ja-Nein-Prüfung steckt hinter dem Wortproblem.
- Du verstehst, welche Frage das Wortproblem stellt.
- Du kannst Alphabet, Wort und formale Sprache unterscheiden.
- Du erkennst, wie Grammatiken und Automaten beim Prüfen helfen.
- Du kannst entscheidbar, semi-entscheidbar und unentscheidbar erklären.
Wörter und formale Sprachen
Im Alltag denkst du bei einem Wort vielleicht an Schule, Haus oder Tastatur. In der theoretischen Informatik ist ein Wort allgemeiner: Es ist eine endliche Folge von Zeichen.
Ein Alphabet ist die festgelegte Menge der erlaubten Zeichen. Wenn das Alphabet aus den Zeichen a und b besteht, darfst du daraus Wörter wie a, ba oder abba bilden.
Eine formale Sprache ist eine genau festgelegte Menge von Wörtern über einem Alphabet. Sie ist also nicht Deutsch oder Englisch, sondern eine Sammlung erlaubter Zeichenfolgen.
Ein Wort ist eine endliche Zeichenfolge.
Ein Alphabet ist die Menge der Zeichen, aus denen Wörter gebaut werden dürfen.
Eine formale Sprache ist eine Menge von Wörtern über einem Alphabet.
Alphabet: \(\{a,b\}\)
Sprache: alle Wörter, die mit a beginnen und mit b enden.
Dann gehören ab, aab und abb zur Sprache. Das Wort ba gehört nicht dazu.
Beim Wortproblem wird immer ein einzelnes Wort gegen eine festgelegte Sprache geprüft.
Interaktive Quizfrage wird geladen ...
Die Frage des Wortproblems
Jetzt wird aus den Bausteinen eine Prüfaufgabe. Ein Entscheidungsproblem ist eine Frage, bei der nur Ja oder Nein herauskommen soll.
Das Wortproblem fragt: Gehört ein gegebenes Wort zu einer gegebenen formalen Sprache? Wenn die Sprache \(L\) heißt und das Wort \(w\) heißt, schreibt man für die Ja-Antwort \(w \in L\).
Diese Schreibweise bedeutet: Das Wort ist ein Element der Sprache. Wenn es nicht dazugehört, schreibt man \(w \notin L\).
Das Wortproblem fragt zu einer formalen Sprache \(L\) und einem Wort \(w\), ob \(w \in L\) gilt.
Sprache: alle Wörter über a und b mit gleich vielen a wie b.
Wort abba: Es enthält zwei a und zwei b. Also gehört es zur Sprache.
Wort aaabb: Es enthält drei a und zwei b. Also gehört es nicht zur Sprache.
Bei Programmiersprachen ist das Wort oft ein Stück Quellcode. Die Sprache ist dann die Menge aller syntaktisch korrekten Programme.
Interaktiver Lückentext wird geladen ...
Grammatiken und Automaten
Eine formale Sprache kann durch Regeln beschrieben werden. Eine Grammatik ist ein solches Regelsystem. Sie erzeugt Wörter Schritt für Schritt.
Eine Ableitung ist die Folge dieser Regelanwendungen. Man startet bei einem Startsymbol und ersetzt Zeichen nach den Regeln, bis ein fertiges Wort entsteht.
Ein Automat ist ein einfaches Rechenmodell, das eine Eingabe Zeichen für Zeichen verarbeitet. Am Ende entscheidet er, ob das Wort angenommen oder abgelehnt wird.
Eine Grammatik ist ein Regelsystem zum Erzeugen von Wörtern.
Eine Ableitung ist eine Schrittfolge von Regelanwendungen.
Ein Automat ist ein Rechenmodell, das Wörter liest und annimmt oder ablehnt.
Eine Grammatik soll Wörter wie ab, aabb und aaabbb erzeugen.
Start: S
Regeln: S wird zu aSb S wird zu ab
Eine Ableitung ist: S wird zu aSb, dann zu aaSbb, dann zu aaabbb.
So entsteht ein Wort mit gleich vielen a vorne und b hinten.
Eine Grammatik erzeugt Wörter. Das Wortproblem fragt umgekehrt: Kann das gegebene Wort durch die Regeln entstehen?
Interaktive Quizfrage wird geladen ...
Entscheidbar und nicht immer entscheidbar
Ein Wortproblem heißt entscheidbar, wenn es einen Algorithmus gibt, der für jede Eingabe nach endlicher Zeit Ja oder Nein sagt. Ein Algorithmus ist eine klare Schrittfolge zur Lösung einer Aufgabe.
Manchmal kann ein Verfahren alle Wörter einer Sprache nacheinander ausgeben. Dann erkennst du ein Ja, sobald dein Wort auftaucht. Aber wenn es nicht auftaucht, weißt du vielleicht nicht, ob du nur länger warten musst.
Das nennt man semi-entscheidbar: Ja-Fälle können sicher gefunden werden, Nein-Fälle aber nicht immer. Unentscheidbar heißt: Es gibt keinen Algorithmus, der für jede Eingabe immer korrekt anhält und Ja oder Nein sagt.
Entscheidbar bedeutet: Ein Algorithmus hält für jede Eingabe an und liefert Ja oder Nein.
Semi-entscheidbar bedeutet: Ja-Fälle werden irgendwann erkannt, aber Nein-Fälle können offen bleiben.
Unentscheidbar bedeutet: Es gibt keinen immer haltenden Algorithmus für alle Eingaben.
Ein Verfahren gibt nach und nach Wörter einer Sprache aus.
Gesuchtes Wort: abba
Wenn abba ausgegeben wird, ist die Antwort Ja.
Wenn abba lange nicht ausgegeben wird, ist die Antwort noch nicht sicher Nein. Vielleicht erscheint es später.
Aufzählen ist nicht dasselbe wie Entscheiden. Entscheiden braucht immer eine sichere Antwort nach endlicher Zeit.
Interaktive Quizfrage wird geladen ...
Chomsky-Hierarchie und Wortproblem
Die Chomsky-Hierarchie ordnet formale Sprachen nach der Stärke ihrer Grammatikregeln. Je kleiner die Typnummer, desto allgemeiner sind die Regeln. Je größer die Typnummer, desto stärker sind sie eingeschränkt.
Typ 3 umfasst reguläre Sprachen. Sie lassen sich mit endlichen Automaten prüfen. Das Wort wird Zeichen für Zeichen gelesen, und am Ende steht Annahme oder Ablehnung.
Typ 2 umfasst kontextfreie Sprachen. Sie eignen sich für verschachtelte Strukturen, zum Beispiel korrekt gesetzte Klammern. Für sie gibt es Verfahren, die das Wortproblem entscheiden.
Typ 1 umfasst kontextsensitive Sprachen. Für die Entscheidbarkeit nutzt man oft die gleich starke Sicht über monotone Grammatiken. Monoton bedeutet: Regelanwendungen machen Wörter nicht kürzer. Darum muss man beim Prüfen eines Wortes der Länge \(n\) nur endlich viele Zwischenformen bis zu dieser Länge betrachten.
Typ 0 ist die allgemeinste Klasse. Dort ist das Wortproblem im Allgemeinen unentscheidbar, auch wenn Ja-Fälle oft durch systematisches Aufzählen gefunden werden können.
Typ 3: Wörter über a und b, die auf ab enden.
Typ 2: Klammerwörter wie (()()), bei denen jede öffnende Klammer passend geschlossen wird.
Typ 1: Wörter wie aaabbbccc, also gleich viele a, b und c in dieser Reihenfolge.
Typ 0: Sehr allgemeine Regelsprachen, bei denen eine sichere Ja-Nein-Entscheidung unmöglich sein kann.
Je kleiner die Typnummer, desto allgemeiner die Grammatik. Allgemeinere Regeln können mächtiger sein, aber das Wortproblem kann schwieriger werden.
Interaktive Quizfrage wird geladen ...
Aufgaben sicher bearbeiten
Bei einer Aufgabe zum Wortproblem schaust du zuerst, wie die Sprache beschrieben ist. Gibt es eine Eigenschaft, eine Grammatik oder einen Automaten?
Dann prüfst du das gegebene Wort gegen diese Beschreibung. Bei einfachen Eigenschaften kannst du zählen oder Muster vergleichen. Bei Grammatiken suchst du eine Ableitung oder erklärst, warum keine möglich ist.
Sprache: alle Wörter über a und b mit gerader Anzahl von a.
Wort: abba
Im Wort stehen zwei a. Zwei ist gerade. Also gehört abba zur Sprache.
Sprache: alle Wörter der Form \(a^n b^n\) mit \(n \ge 1\).
Wort: aaabb
Das Wort hat drei a und zwei b. Für diese Sprache müssen es gleich viele a und b sein. Also gehört aaabb nicht zur Sprache.
Interaktive Lernkarten wird geladen ...
Interaktiver Lückentext wird geladen ...
Zusammenfassung
Das Wortproblem fragt, ob ein gegebenes Wort zu einer formalen Sprache gehört. Dafür brauchst du die Begriffe Alphabet, Wort und formale Sprache.
Grammatiken erzeugen Wörter mit Regeln. Beim Wortproblem zu einer Grammatik prüfst du, ob das Wort aus dem Startsymbol ableitbar ist.
Automaten können Wörter lesen und je nach Sprachklasse annehmen oder ablehnen. Für reguläre Sprachen ist das besonders direkt.
Entscheidbar heißt, dass ein Algorithmus immer nach endlicher Zeit Ja oder Nein sagt. Semi-entscheidbar reicht nur für sichere Ja-Fälle, unentscheidbar bedeutet: Ein allgemeiner immer haltender Entscheider existiert nicht.
In der Chomsky-Hierarchie sind die Wortprobleme für Typ 3, Typ 2 und Typ 1 entscheidbar. Für Typ 0 ist das Wortproblem im Allgemeinen unentscheidbar.