|
|
| Zeile 1: |
Zeile 1: |
| In der Informatik ist ein Wort jede endliche Zeichenfolge, die sich aus den Zeichen eines festgelegten Alphabets zusammensetzt – etwa ein Passwort, eine Binärzahl oder eine Folge von Tastendrücken. Ob die Zeichenfolge inhaltlich einen Sinn ergibt, spielt dabei keine Rolle.
| | Die Turingmaschine ist ein sehr einfaches Modell eines Rechners und kann trotzdem alles berechnen, was ein Computer berechnen kann. An ihr lässt sich auch zeigen, was kein Computer leisten kann. |
|
| |
|
| ==Definition== | | ==Definition== |
| Es sei <math>\Sigma</math> ein [[Alphabet]] (eine endliche, nicht leere [[Menge]] von [[Zeichen]]). Ein '''Wort''' <math>w</math> über dem Alphabet <math>\Sigma</math> ist eine endliche Folge von <math>n</math> Zeichen <math>a_1; a_2; \dots; a_n</math> mit <math>a_i \in \Sigma</math> und <math>n \in \mathbb{N}_0</math>:
| | Eine '''Turingmaschine''' ist ein 7-Tupel <math>M = (Q; \Sigma; \Gamma; \delta; q_0; \square; F)</math>: |
|
| |
|
| :<math>w = a_1 a_2 \dots a_n</math> | | * <math>Q</math> ist die endliche, nicht leere Zustandsmenge. |
| | * <math>\Sigma</math> ist das [[Alphabet|Eingabealphabet]]. |
| | * <math>\Gamma</math> ist das Bandalphabet mit <math>\Sigma \subset \Gamma</math>. |
| | * <math>\delta: Q \times \Gamma \to Q \times \Gamma \times \{L; R\}</math> ist die Übergangsfunktion. Sie muss nicht für jedes Paar aus Zustand und Zeichen einen Wert haben. |
| | * <math>q_0 \in Q</math> ist der Startzustand. |
| | * <math>\square \in \Gamma \setminus \Sigma</math> ist das Leerzeichen. |
| | * <math>F \subseteq Q</math> ist die Menge der Endzustände. |
|
| |
|
| <math>\mathbb{N}_0</math> ist die Menge der natürlichen Zahlen einschließlich der Null. Besteht die Folge aus gar keinem Zeichen (<math>n = 0</math>), heißt sie '''leeres Wort''' und wird mit dem griechischen Buchstaben <math>\varepsilon</math> (Epsilon) bezeichnet. Manche Bücher schreiben dafür <math>\lambda</math> (Lambda). In diesem Wiki steht <math>\lambda</math> für die Ausgabefunktion des [[Mealy-Automat|Mealy-Automaten]]. | | Die Maschine arbeitet auf einem Band, das in beide Richtungen unbegrenzt ist. Jedes Feld des Bandes trägt ein [[Zeichen]] aus <math>\Gamma</math>. Ein Lese-Schreib-Kopf steht auf genau einem Feld. Anders als ein [[Endlicher Automat|endlicher Automat]] kann die Turingmaschine ihre Eingabe verändern, und anders als ein [[Kellerautomat]] erreicht sie jede Stelle ihres Speichers. Jeder endliche Automat und jeder Kellerautomat lässt sich durch eine Turingmaschine nachbilden. Die Sprachen, die Turingmaschinen erkennen, bilden Typ 0 der [[Chomsky-Hierarchie]]. |
|
| |
|
| Die Menge aller endlichen Wörter, die sich aus den Zeichen des Alphabets <math>\Sigma</math> bilden lassen (einschließlich des leeren Wortes <math>\varepsilon</math>), heißt '''Kleenesche Hülle''' <math>\Sigma^*</math> (gelesen „Sigma Stern“). Für <math>w \in \Sigma^*</math> liest man: „<math>w</math> ist ein Wort über <math>\Sigma</math>“. Die Menge aller Wörter ohne das leere Wort wird mit <math>\Sigma^+</math> (gelesen „Sigma Plus“) bezeichnet. Als [[Menge#Differenzmenge|Differenzmenge]] geschrieben gilt <math>\Sigma^+ = \Sigma^* \setminus \{\varepsilon\}</math>.
| | ==Arbeitsweise== |
| | Zu Beginn steht die Eingabe auf dem Band, alle übrigen Felder tragen <math>\square</math>. Die Maschine startet in <math>q_0</math>, der Kopf steht auf dem ersten Zeichen der Eingabe. |
|
| |
|
| Stern und Plus werden auch auf eine ausgeschriebene Menge von Zeichen angewendet. Die Menge steht dann in Mengenklammern vor dem Stern oder dem Plus, siehe das Beispiel [[#Kleenesche Hülle aufschreiben|Kleenesche Hülle aufschreiben]].
| | In jedem Schritt liest der Kopf ein Feld. Die Übergangsfunktion legt dann drei Dinge fest: das Zeichen, das auf das Feld geschrieben wird, die Bewegung des Kopfes um ein Feld nach links (<math>L</math>) oder rechts (<math>R</math>) und den Folgezustand. |
|
| |
|
| Anders als bei einer Menge kommt es bei einem Wort auf die Reihenfolge der Zeichen an, und dasselbe Zeichen darf mehrfach vorkommen.
| | Die Maschine hält, wenn sie einen Endzustand erreicht oder wenn für den Zustand und das gelesene Zeichen kein Übergang festgelegt ist. Hält sie in einem Endzustand, hat sie die Eingabe akzeptiert, und das Ergebnis der Berechnung steht auf dem Band. Hält sie in einem anderen Zustand, hat sie die Eingabe abgelehnt. So beantwortet eine Turingmaschine eine Frage mit ja (akzeptiert) oder nein (abgelehnt). Eine Turingmaschine muss nicht halten: Sie kann auch endlos weiterlaufen. |
|
| |
|
| ==Eigenschaften und Operationen== | | ==Entscheidbarkeit== |
| ===Wortlänge===
| | Die These von Church und Turing besagt: Was überhaupt berechenbar ist, kann eine Turingmaschine berechnen. Berechenbar heißt eine Aufgabe, wenn es ein Verfahren gibt, das sie in endlich vielen, eindeutig festgelegten Schritten löst. Die Aussage heißt These und nicht Satz, weil sie sich nicht beweisen lässt: Was als Verfahren gilt, ist nicht mathematisch festgelegt. Bisher wurde aber kein Verfahren gefunden, das sich nicht durch eine Turingmaschine nachbilden lässt. Was eine Turingmaschine nicht kann, kann deshalb auch kein Programm in [[Java]] oder einer anderen Programmiersprache. |
| Die '''Wortlänge''' <math>|w|</math> gibt die Gesamtzahl der Zeichen an, aus denen das Wort <math>w</math> besteht. Kommt dasselbe Zeichen mehrfach im Wort vor, wird jedes Auftreten einzeln mitgezählt. Für ein Wort <math>w = a_1 a_2 \dots a_n</math> gilt <math>|w| = n</math>. | |
|
| |
|
| ===Leeres Wort===
| | Ein '''Problem''' ist hier eine Frage, die für jede Eingabe mit ja oder nein zu beantworten ist. Ein Problem heißt '''entscheidbar''', wenn es eine Turingmaschine gibt, die bei jeder Eingabe nach endlich vielen Schritten hält und die richtige Antwort gibt. Gibt es keine solche Maschine, heißt das Problem '''unentscheidbar'''. |
| Das leere Wort <math>\varepsilon</math> enthält kein einziges Zeichen, sodass für seine Wortlänge <math>|\varepsilon| = 0</math> gilt. Es gehört zu jedem <math>\Sigma^*</math> (<math>\varepsilon \in \Sigma^*</math>), weil es kein Zeichen enthält, das außerhalb von <math>\Sigma</math> liegt. Das leere Wort selbst ist jedoch kein einzelnes Zeichen des Alphabets (<math>\varepsilon \notin \Sigma</math>).
| |
|
| |
|
| ===Verkettung (Konkatenation)===
| | Unentscheidbar ist das '''Halteproblem'''. Es fragt, ob ein Programm bei einer Eingabe irgendwann hält. Die Frage ist sinnvoll, weil ein Programm selbst ein Text ist und deshalb als Eingabe eines anderen Programms dienen kann, so wie ein Quelltext die Eingabe eines [[Compiler|Compilers]] ist. |
| Werden zwei Wörter <math>u \in \Sigma^*</math> und <math>v \in \Sigma^*</math> direkt hintereinander gehängt, entsteht ein neues Wort <math>uv \in \Sigma^*</math>. Diese Operation heißt '''Verkettung''' oder '''Konkatenation'''.
| |
| * '''Additivität der Wortlänge:''' Die Länge des verketteten Wortes ist die Summe der Einzellängen: <math>|uv| = |u| + |v|</math>.
| |
| * '''Reihenfolge (Nicht-Kommutativität):''' Bei einem Wort kommt es exakt auf die Reihenfolge der Zeichen an. Im Allgemeinen sind <math>uv</math> und <math>vu</math> verschiedene Wörter (<math>uv \neq vu</math>).
| |
| * '''Neutrales Element:''' Das Verketten mit dem leeren Wort <math>\varepsilon</math> verändert ein Wort nicht: <math>w\varepsilon = \varepsilon w = w</math>.
| |
| * '''Wortpotenz:''' Wird dasselbe Wort oder Zeichen <math>k</math>-mal hintereinander gehängt, schreibt man verkürzt <math>w^k</math> (wobei <math>w^0 = \varepsilon</math> festgelegt ist), siehe [[#Wortpotenz|Wortpotenz]].
| |
|
| |
|
| ===Wortpotenz===
| | Beweisidee: Angenommen, es gäbe ein Programm <math>H</math>, das für jedes Programm <math>p</math> und jede Eingabe <math>e</math> entscheidet, ob <math>p</math> bei <math>e</math> hält. Dann ließe sich ein Programm <math>D</math> bauen. <math>D</math> erhält ein Programm <math>p</math> und fragt <math>H</math>, ob <math>p</math> bei der Eingabe <math>p</math> hält. Antwortet <math>H</math> mit „hält“, läuft <math>D</math> endlos. Antwortet <math>H</math> mit „hält nicht“, hält <math>D</math>. |
| Die '''Wortpotenz''' <math>w^k</math> ist die <math>k</math>-fache Verkettung eines Wortes <math>w</math> mit sich selbst:
| |
|
| |
|
| :<math>w^k = \underbrace{w\,w \dots w}_{k\text{-mal}} \quad \text{mit } k \in \mathbb{N}_0</math>
| | Wird <math>D</math> auf sich selbst angewendet, widerspricht jede Antwort von <math>H</math>. Sagt <math>H</math>, dass <math>D</math> bei der Eingabe <math>D</math> hält, läuft <math>D</math> endlos. Sagt <math>H</math>, dass <math>D</math> nicht hält, hält <math>D</math>. Also kann es <math>H</math> nicht geben. |
|
| |
|
| * Für <math>k = 0</math> entsteht das leere Wort: <math>w^0 = \varepsilon</math>. Für <math>k = 1</math> bleibt das Wort unverändert: <math>w^1 = w</math>.
| | Unentscheidbar bedeutet nicht „schwierig“ oder „langsam“. Es bedeutet: Kein Verfahren beantwortet die Frage für alle Eingaben richtig. Für einzelne Programme lässt sie sich oft beantworten. Eine Folge für die Praxis: Kein Werkzeug entscheidet für jedes Programm richtig, ob es hält. Tests und Analysen senken das Risiko einer Endlosschleife, ersetzen aber keinen vollständigen Nachweis. |
| * Die Länge vervielfacht sich: <math>|w^k| = k \cdot |w|</math>.
| |
| * Der Exponent bezieht sich nur auf das Zeichen direkt davor. Soll ein ganzes Wort wiederholt werden, steht es in Klammern. Die Klammern gehören dabei nicht zum Wort.
| |
| * Steht im Exponenten eine Variable wie <math>n</math>, beschreibt die Potenz viele Wörter auf einmal: für jeden zulässigen Wert von <math>n</math> eines. So lassen sich auch unendliche [[Formale Sprache|Sprachen]] kurz angeben.
| |
|
| |
|
| ===Teilwort=== | | ==Beispiele== |
| Ein Wort <math>u</math> heißt '''Teilwort''' von <math>w</math>, wenn <math>u</math> als zusammenhängendes Stück in <math>w</math> vorkommt. Dann lässt sich <math>w</math> als Verkettung <math>w = xuy</math> mit zwei Wörtern <math>x \in \Sigma^*</math> und <math>y \in \Sigma^*</math> schreiben.
| | ===Bits invertieren=== |
| * Steht <math>u</math> am Anfang von <math>w</math> (also <math>x = \varepsilon</math>), heißt <math>u</math> '''Präfix''' von <math>w</math>.
| | Die Turingmaschine ersetzt jede <math>0</math> durch <math>1</math> und jede <math>1</math> durch <math>0</math>. Sie hat die Zustände <math>q_0</math> (Startzustand) und <math>q_1</math> (Endzustand), das Eingabealphabet <math>\Sigma = \{0; 1\}</math> und das Bandalphabet <math>\Gamma = \{0; 1; \square\}</math>. Das Zeichen <math>\square</math> steht für das Leerzeichen. |
| * Steht <math>u</math> am Ende von <math>w</math> (also <math>y = \varepsilon</math>), heißt <math>u</math> '''Suffix''' von <math>w</math>.
| |
| * Das leere Wort <math>\varepsilon</math> und das Wort <math>w</math> selbst sind Teilwörter von <math>w</math>.
| |
|
| |
|
| ===Spiegelwort=== | | {| class="wikitable" style="text-align:center" |
| Das '''Spiegelwort''' <math>w^R</math> enthält die Zeichen von <math>w</math> in umgekehrter Reihenfolge (<math>R</math> für englisch ''reverse'', umgekehrt). Für <math>w = a_1 a_2 \dots a_n</math> gilt:
| | ! Zustand !! liest !! schreibt !! bewegt !! Folgezustand |
| | |- |
| | | <math>q_0</math> || <math>0</math> || <math>1</math> || <math>R</math> || <math>q_0</math> |
| | |- |
| | | <math>q_0</math> || <math>1</math> || <math>0</math> || <math>R</math> || <math>q_0</math> |
| | |- |
| | | <math>q_0</math> || <math>\square</math> || <math>\square</math> || <math>L</math> || <math>q_1</math> |
| | |} |
|
| |
|
| :<math>w^R = a_n \dots a_2 a_1</math> | | [[Datei:Turingmaschine Bits invertieren.png|mini|Band, Zustand und Kopfposition beim Lauf für die Eingabe 10]] |
|
| |
|
| * Die Wortlänge bleibt gleich: <math>|w^R| = |w|</math>.
| | Lauf für die Eingabe <math>10</math>: |
| * Das leere Wort und jedes Wort aus einem einzigen Zeichen stimmen mit ihrem Spiegelwort überein.
| |
| * Beim Spiegeln einer Verkettung kehrt sich auch die Reihenfolge der Teile um: <math>(uv)^R = v^R u^R</math>.
| |
| * Ein Wort, das mit seinem Spiegelwort übereinstimmt (<math>w = w^R</math>), heißt '''Palindrom'''.
| |
|
| |
|
| ==Anzahl der Wörter==
| | # <math>q_0</math> liest <math>1</math>, schreibt <math>0</math> und geht nach rechts. |
| Über einem Alphabet mit <math>m</math> Zeichen gibt es genau <math>m^n</math> Wörter der Länge <math>n</math>: Für jede der <math>n</math> Stellen stehen <math>m</math> Zeichen zur Wahl, und die Möglichkeiten werden multipliziert.
| | # <math>q_0</math> liest <math>0</math>, schreibt <math>1</math> und geht nach rechts. |
| | # <math>q_0</math> liest <math>\square</math>, schreibt <math>\square</math> und geht nach links in <math>q_1</math>. <math>q_1</math> ist ein Endzustand, die Maschine hält. |
|
| |
|
| Sind an den einzelnen Stellen unterschiedlich viele Zeichen erlaubt, werden die Anzahlen der erlaubten Zeichen aller Stellen miteinander multipliziert: Bei <math>m_1</math> Möglichkeiten für die erste Stelle, <math>m_2</math> für die zweite und so weiter bis <math>m_n</math> für die <math>n</math>-te Stelle gibt es <math>m_1 \cdot m_2 \cdot \dots \cdot m_n</math> Wörter.
| | Das Ergebnis auf dem Band ist <math>01</math>. |
|
| |
|
| Die Menge aller Wörter der Länge <math>n</math> wird mit <math>\Sigma^n</math> bezeichnet. Damit gilt: | | ===Paritätsbit anhängen=== |
| * <math>\Sigma^0 = \{\varepsilon\}</math>: Es gibt genau ein Wort der Länge 0, das leere Wort.
| | [[Datei:Turingmaschine Paritätsbit anhängen.png|mini|Band, Zustand und Kopfposition beim Lauf für die Eingabe 101]] |
| * <math>\Sigma^1</math> enthält die <math>m</math> Wörter, die aus einem einzigen Zeichen bestehen.
| | Die Turingmaschine hängt an eine Folge von Bits ein Prüfbit an, das Paritätsbit: <math>0</math> bei einer geraden, <math>1</math> bei einer ungeraden Anzahl Einsen. Die Zustände merken sich, ob bisher gerade viele (<math>q_0</math>) oder ungerade viele Einsen (<math>q_1</math>) gelesen wurden. <math>q_2</math> ist der Endzustand. Das Eingabealphabet ist <math>\Sigma = \{0; 1\}</math>, das Bandalphabet <math>\Gamma = \{0; 1; \square\}</math>. Der Kopf bewegt sich in jedem Schritt nach rechts. |
| * <math>\Sigma^* = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup \dots</math> enthält die Wörter aller Längen. Das Zeichen <math>\cup</math> steht für die [[Menge#Vereinigungsmenge|Vereinigung]] von Mengen.
| |
| * <math>\Sigma^+ = \Sigma^1 \cup \Sigma^2 \cup \dots</math> enthält die Wörter aller Längen ab 1.
| |
|
| |
|
| Obwohl das Alphabet endlich ist und jedes einzelne Wort endlich lang ist, enthält <math>\Sigma^*</math> unendlich viele Wörter: Zu jedem Wort entsteht durch Anhängen eines Zeichens ein längeres Wort.
| | {| class="wikitable" style="text-align:center" |
| | | ! Zustand !! liest !! schreibt !! bewegt !! Folgezustand |
| ==Wörter und formale Sprachen==
| | |- |
| Während <math>\Sigma^*</math> sämtliche Wörter enthält, die sich aus den Zeichen des Alphabets <math>\Sigma</math> bilden lassen, umfasst eine [[Formale Sprache]] <math>L \subseteq \Sigma^*</math> nur diejenigen Wörter, die zusätzliche formale Regeln erfüllen. Sie ist eine [[Menge#Teilmenge|Teilmenge]] von <math>\Sigma^*</math>.
| | | <math>q_0</math> || <math>0</math> || <math>0</math> || <math>R</math> || <math>q_0</math> |
| | |
| Prüft ein [[Deterministischer endlicher Automat|deterministischer endlicher Automat]] <math>A</math> die Eingabewörter über <math>\Sigma</math>, gehört ein Wort <math>w \in \Sigma^*</math> genau dann zur vom Automaten akzeptierten Sprache <math>L(A)</math>, wenn sich der Automat nach dem vollständigen Lesen von <math>w</math> in einem Endzustand befindet. Ist bereits der Startzustand des Automaten ein Endzustand, wird auch das leere Wort <math>\varepsilon</math> akzeptiert (<math>\varepsilon \in L(A)</math>). Bei einem [[Nichtdeterministischer endlicher Automat|nichtdeterministischen endlichen Automaten]] genügt es, wenn mindestens ein Pfad nach dem vollständigen Lesen in einem Endzustand endet.
| |
| | |
| ==Beispiele== | |
| ===Wörter, Wortlängen und Verkettungen bestimmen===
| |
| Gegeben sei das Alphabet <math>\Sigma = \{K; E\}</math>. Aus diesen beiden Zeichen lassen sich unter anderem folgende Wörter aus <math>\Sigma^*</math> bilden und untersuchen:
| |
| * '''Wortlängen bestimmen:'''
| |
| ** Das Wort <math>w_1 = KEK</math> besteht aus drei Zeichen, hat also die Wortlänge <math>|KEK| = 3</math>.
| |
| ** Das Wort <math>w_2 = KKKK</math> (in Potenzschreibweise <math>K^4</math>) hat die Wortlänge <math>|KKKK| = 4</math>.
| |
| ** Das leere Wort <math>\varepsilon</math> enthält kein Zeichen und besitzt die Wortlänge <math>|\varepsilon| = 0</math>.
| |
| * '''Wörter verketten:''' Gegeben seien die Wörter <math>u = EK</math> (mit <math>|u| = 2</math>) und <math>v = K</math> (mit <math>|v| = 1</math>).
| |
| ** Das Anhängen von <math>v</math> an <math>u</math> ergibt <math>uv = EKK</math> mit der Länge <math>|uv| = |u| + |v| = 2 + 1 = 3</math>.
| |
| ** In umgekehrter Reihenfolge entsteht <math>vu = KEK</math>. Da die Zeichen an unterschiedlichen Positionen stehen, gilt <math>uv \neq vu</math>.
| |
| ** Die Verkettung mit dem leeren Wort ergibt <math>u\varepsilon = EK\varepsilon = EK = u</math>.
| |
| | |
| ===Wortpotenzen ausschreiben===
| |
| Über dem Alphabet <math>\Sigma = \{K; E\}</math> werden Potenzen ausgeschrieben und Wörter in Potenzschreibweise zusammengefasst:
| |
| | |
| {| class="wikitable"
| |
| ! Potenzschreibweise !! ausgeschrieben !! Wortlänge
| |
| |- | | |- |
| | <math>K^3</math> || <math>KKK</math> || <math>3 \cdot 1 = 3</math> | | | <math>q_0</math> || <math>1</math> || <math>1</math> || <math>R</math> || <math>q_1</math> |
| |- | | |- |
| | <math>(KE)^2</math> || <math>KEKE</math> || <math>2 \cdot 2 = 4</math> | | | <math>q_1</math> || <math>0</math> || <math>0</math> || <math>R</math> || <math>q_1</math> |
| |- | | |- |
| | <math>KE^2</math> || <math>KEE</math> || <math>1 + 2 = 3</math> | | | <math>q_1</math> || <math>1</math> || <math>1</math> || <math>R</math> || <math>q_0</math> |
| |- | | |- |
| | <math>K^2E^3</math> || <math>KKEEE</math> || <math>2 + 3 = 5</math> | | | <math>q_0</math> || <math>\square</math> || <math>0</math> || <math>R</math> || <math>q_2</math> |
| |- | | |- |
| | <math>(KE)^0</math> || <math>\varepsilon</math> || <math>0 \cdot 2 = 0</math> | | | <math>q_1</math> || <math>\square</math> || <math>1</math> || <math>R</math> || <math>q_2</math> |
| |} | | |} |
|
| |
|
| Der Vergleich der Zeilen <math>(KE)^2</math> und <math>KE^2</math> zeigt die Wirkung der Klammern: In <math>(KE)^2</math> wird das ganze Wort <math>KE</math> wiederholt, in <math>KE^2</math> nur das Zeichen <math>E</math>. Umgekehrt lässt sich das Wort <math>KKKKEE</math> kürzer als <math>K^4E^2</math> schreiben.
| | Lauf für die Eingabe <math>101</math>: |
|
| |
|
| Mit einer Variablen im Exponenten steht <math>K^n</math> mit <math>n \ge 0</math> für die Wörter <math>\varepsilon</math>, <math>K</math>, <math>KK</math>, <math>KKK</math> und so weiter. <math>K^nE</math> mit <math>n \ge 1</math> beschreibt alle Wörter aus mindestens einem <math>K</math> und einem abschließenden <math>E</math>, also <math>KE</math>, <math>KKE</math>, <math>KKKE</math> und so weiter.
| | # <math>q_0</math> liest <math>1</math>, lässt die <math>1</math> stehen und wechselt nach <math>q_1</math>: Bisher wurde eine ungerade Anzahl Einsen gelesen. |
| | # <math>q_1</math> liest <math>0</math>, lässt sie stehen und bleibt in <math>q_1</math>. |
| | # <math>q_1</math> liest <math>1</math> und wechselt nach <math>q_0</math>: Jetzt ist die Anzahl gerade. |
| | # <math>q_0</math> liest <math>\square</math>: Die Eingabe ist zu Ende. Die Maschine schreibt das Prüfbit <math>0</math> auf das leere Feld und wechselt in den Endzustand <math>q_2</math>. |
|
| |
|
| ===Kleenesche Hülle aufschreiben===
| | Das Ergebnis auf dem Band ist <math>1010</math>. Anders als im ersten Beispiel beschreibt die Maschine ein Feld, das vorher leer war: Das Band ist ihr Arbeitsspeicher und nicht nur ihre Eingabe. |
| Gegeben ist das Alphabet <math>\Sigma = \{K; E\}</math>. Seine Wörter werden nach der Länge geordnet aufgeschrieben:
| |
|
| |
|
| {| class="wikitable"
| | ===Eingabe ablehnen=== |
| ! Menge !! ausgeschrieben !! Anzahl der Wörter
| | Die Turingmaschine prüft, ob eine Folge von Bits nur aus Nullen besteht. Sie hat die Zustände <math>q_0</math> (Startzustand) und <math>q_1</math> (Endzustand), das Eingabealphabet <math>\Sigma = \{0; 1\}</math> und das Bandalphabet <math>\Gamma = \{0; 1; \square\}</math>. |
| |-
| | |
| | <math>\Sigma^0</math> || <math>\{\varepsilon\}</math> || <math>2^0 = 1</math>
| | {| class="wikitable" style="text-align:center" |
| |-
| | ! Zustand !! liest !! schreibt !! bewegt !! Folgezustand |
| | <math>\Sigma^1</math> || <math>\{K; E\}</math> || <math>2^1 = 2</math>
| |
| |- | | |- |
| | <math>\Sigma^2</math> || <math>\{KK; KE; EK; EE\}</math> || <math>2^2 = 4</math> | | | <math>q_0</math> || <math>0</math> || <math>0</math> || <math>R</math> || <math>q_0</math> |
| |- | | |- |
| | <math>\Sigma^3</math> || <math>\{KKK; KKE; KEK; KEE; EKK; EKE; EEK; EEE\}</math> || <math>2^3 = 8</math> | | | <math>q_0</math> || <math>\square</math> || <math>\square</math> || <math>R</math> || <math>q_1</math> |
| |} | | |} |
|
| |
|
| * '''Kleenesche Hülle:''' <math>\Sigma^*</math> enthält die Wörter aller Zeilen und alle längeren Wörter: <math>\Sigma^* = \{\varepsilon; K; E; KK; KE; EK; EE; KKK; \dots\}</math>. Die Aufzählung endet nie, das zeigen die drei Punkte an.
| | Für <math>q_0</math> und das Zeichen <math>1</math> ist kein Übergang festgelegt. |
| * '''Ohne das leere Wort:''' <math>\Sigma^+ = \{K; E; KK; KE; EK; EE; KKK; \dots\}</math> enthält dieselben Wörter außer <math>\varepsilon</math>.
| |
| * '''Stern über einer kleineren Menge:''' <math>\{K\}^* = \{\varepsilon; K; KK; KKK; \dots\}</math> enthält nur die Wörter, in denen kein anderes Zeichen als <math>K</math> vorkommt. <math>\{K\}^+</math> enthält dieselben Wörter außer <math>\varepsilon</math>.
| |
| * '''Zugehörigkeit prüfen:''' Es gilt <math>KEK \in \Sigma^*</math> und <math>KEK \in \Sigma^+</math>, aber <math>KEK \notin \{K\}^*</math>, weil das Wort ein <math>E</math> enthält. Für das leere Wort gilt <math>\varepsilon \in \Sigma^*</math> und <math>\varepsilon \in \{K\}^*</math>, aber <math>\varepsilon \notin \Sigma^+</math>.
| |
| * '''Teil eines größeren Alphabets:''' Über dem Alphabet <math>\{a; b; c\}</math> enthält <math>\{a; b\}^+</math> alle Wörter aus mindestens einem Zeichen, in denen nur <math>a</math> und <math>b</math> vorkommen. Dazu gehören <math>a</math>, <math>ab</math> und <math>bba</math>, nicht aber <math>\varepsilon</math> und <math>ac</math>.
| |
| | |
| ===Wörter aufzählen und zählen===
| |
| Gegeben ist das Alphabet <math>\Sigma = \{a; b; c\}</math> mit <math>m = 3</math> Zeichen. Gesucht sind alle Wörter bis zur Länge 2 und die Anzahl der Wörter der Länge 4.
| |
| | |
| * '''Länge 0:''' Es gibt nur das leere Wort <math>\varepsilon</math>, also <math>3^0 = 1</math> Wort.
| |
| * '''Länge 1:''' <math>a</math>, <math>b</math> und <math>c</math>, also <math>3^1 = 3</math> Wörter.
| |
| * '''Länge 2:''' Jedes der 3 Zeichen an der ersten Stelle lässt sich mit jedem der 3 Zeichen an der zweiten Stelle kombinieren. Das ergibt <math>3^2 = 9</math> Wörter: <math>aa</math>, <math>ab</math>, <math>ac</math>, <math>ba</math>, <math>bb</math>, <math>bc</math>, <math>ca</math>, <math>cb</math> und <math>cc</math>.
| |
| * '''Bis zur Länge 2:''' Zusammen sind das <math>1 + 3 + 9 = 13</math> Wörter.
| |
| * '''Länge 4:''' Für vier Stellen gibt es <math>3^4 = 3 \cdot 3 \cdot 3 \cdot 3 = 81</math> Wörter. Aufzählen lohnt sich hier nicht mehr, die Formel <math>m^n</math> liefert die Anzahl direkt.
| |
| | |
| ===Wörter mit unterschiedlichen Stellen zählen===
| |
| Ein Kaffeeautomat bietet zwei Getränke an, Kaffee <math>K</math> und Espresso <math>E</math>, jeweils in drei Bechergrößen <math>1</math>, <math>2</math> und <math>3</math>. Eine Bestellung besteht aus genau zwei Zeichen: zuerst das Getränk, dann die Größe. Das Alphabet ist <math>\Sigma = \{K; E; 1; 2; 3\}</math>.
| |
| | |
| * '''Möglichkeiten je Stelle:''' Für die erste Stelle gibt es 2 Zeichen, für die zweite Stelle 3 Zeichen.
| |
| * '''Anzahl:''' Jedes Getränk lässt sich mit jeder Größe kombinieren. Es gibt <math>2 \cdot 3 = 6</math> Bestellungen.
| |
| * '''Aufzählung:''' <math>K1</math>, <math>K2</math>, <math>K3</math>, <math>E1</math>, <math>E2</math> und <math>E3</math>.
| |
| * '''Vergleich:''' Über <math>\Sigma</math> gibt es <math>5^2 = 25</math> Wörter der Länge 2. Nur 6 davon sind Bestellungen. Die Wörter <math>1K</math> und <math>KE</math> sind zum Beispiel keine.
| |
| | |
| ===Teilwörter erkennen===
| |
| Gegeben ist das Wort <math>w = KEKK</math> über <math>\Sigma = \{K; E\}</math>.
| |
| * <math>EK</math> ist ein Teilwort von <math>w</math>: Es gilt <math>w = xuy</math> mit <math>x = K</math>, <math>u = EK</math> und <math>y = K</math>.
| |
| * <math>KE</math> ist ein Präfix von <math>w</math>, denn <math>w</math> beginnt mit <math>KE</math>.
| |
| * <math>KK</math> ist ein Suffix von <math>w</math>, denn <math>w</math> endet mit <math>KK</math>.
| |
| * <math>EE</math> ist kein Teilwort von <math>w</math>, denn in <math>w</math> stehen nirgends zwei <math>E</math> direkt hintereinander.
| |
| * <math>KKK</math> ist kein Teilwort von <math>w</math>: Das Wort enthält zwar drei <math>K</math>, aber nicht zusammenhängend.
| |
| * Alle Präfixe von <math>w</math> sind <math>\varepsilon</math>, <math>K</math>, <math>KE</math>, <math>KEK</math> und <math>KEKK</math>. Alle Suffixe von <math>w</math> sind <math>\varepsilon</math>, <math>K</math>, <math>KK</math>, <math>EKK</math> und <math>KEKK</math>.
| |
|
| |
|
| ===Spiegelwörter bilden===
| | * '''Eingabe <math>000</math>:''' <math>q_0</math> liest dreimal <math>0</math>, lässt die Zeichen stehen und geht jeweils nach rechts. Dann liest <math>q_0</math> das Leerzeichen <math>\square</math> und wechselt in den Endzustand <math>q_1</math>. Die Maschine hält in einem Endzustand: Die Eingabe ist akzeptiert, die Antwort lautet ja. |
| Gegeben sind Wörter über <math>\Sigma = \{K; E\}</math>.
| | * '''Eingabe <math>010</math>:''' <math>q_0</math> liest <math>0</math> und geht nach rechts. Dann liest <math>q_0</math> die <math>1</math>. Dafür gibt es keinen Übergang, die Maschine hält in <math>q_0</math>. Das ist kein Endzustand: Die Eingabe ist abgelehnt, die Antwort lautet nein. |
| * <math>(KKE)^R = EKK</math>: Das Wort wird von hinten nach vorn gelesen. Die Klammern gehören nicht zum Wort, sie zeigen nur, worauf sich das <math>R</math> bezieht. | |
| * <math>(KEK)^R = KEK</math>: Das Wort stimmt mit seinem Spiegelwort überein, es ist ein Palindrom.
| |
| * Für <math>u = KK</math> und <math>v = E</math> ist <math>uv = KKE</math>. Das Spiegelwort entsteht auch aus den gespiegelten Teilen in umgekehrter Reihenfolge: Mit <math>v^R = E</math> und <math>u^R = KK</math> ergibt sich <math>v^R u^R = EKK</math>.
| |
| * Hängt man an ein Wort <math>u</math> sein Spiegelwort an, entsteht ein spiegelbildlich aufgebautes Wort <math>u\,u^R</math>. Für <math>u = KE</math> ist <math>u^R = EK</math> und damit <math>u\,u^R = KEEK</math>: Die zweite Hälfte wiederholt die erste in umgekehrter Reihenfolge.
| |
|
| |
|
| ===Akzeptierte und abgelehnte Wörter am Kaffeeautomaten unterscheiden===
| | Die Maschine hält bei jeder Eingabe nach endlich vielen Schritten und gibt die richtige Antwort. Die Frage „Besteht die Eingabe nur aus Nullen?“ ist damit entscheidbar. |
| [[Datei:DEA Kaffeeautomat vollständig.png|mini|Vollständiger DEA des Kaffeeautomaten]]
| |
| Der abgebildete Kaffeeautomat besitzt das Eingabealphabet <math>\Sigma = \{K; E\}</math>. Er sammelt den Kaffeesatz in einem Behälter, dem Satzfach. Ein Kaffee <math>K</math> füllt das Satzfach um 1 Einheit, ein Espresso <math>E</math> um 2 Einheiten. Der Automat startet im Zustand <math>q_0</math> (0 Einheiten) und akzeptiert genau die Wörter, nach deren Eingabe er sich im doppelt umkreisten Endzustand <math>q_4</math> (Satzfach mit genau 4 Einheiten voll) befindet:
| |
|
| |
|
| * '''Akzeptierte Wörter (<math>w \in L</math>):''' Genau fünf Wörter über <math>\Sigma</math> führen vom Startzustand <math>q_0</math> in den Endzustand <math>q_4</math> und bilden die akzeptierte Sprache <math>L = \{KKKK; EE; EKK; KEK; KKE\}</math>.
| | ===Entscheidbare und unentscheidbare Fragen unterscheiden=== |
| * '''Abgelehnte Wörter (<math>w \in \Sigma^*</math>, aber <math>w \notin L</math>):''' Alle übrigen Wörter aus <math>\Sigma^*</math> sind zwar formal gültige Wörter über dem Alphabet <math>\Sigma</math>, gehören aber nicht zur Sprache <math>L</math>:
| | Für drei Fragen wird geprüft, ob sie entscheidbar sind: |
| ** <math>KK</math> (<math>|KK| = 2</math>): Nach zwei Kaffees endet der Automat im Zustand <math>q_2</math>. Da <math>q_2</math> kein Endzustand ist, gilt <math>KK \notin L</math>.
| |
| ** <math>EEK</math> (<math>|EEK| = 3</math>): Nach <math>EE</math> ist zwar <math>q_4</math> erreicht, das anschließende <math>K</math> führt jedoch weiter in den [[Deterministischer endlicher Automat#Vollständiger DEA und Fehlerzustand|Fehlerzustand]] <math>q_F</math> (Überlauf bei 5 Einheiten). Daher gilt <math>EEK \notin L</math>.
| |
| ** <math>\varepsilon</math> (<math>|\varepsilon| = 0</math>): Ohne Eingabe verbleibt der Automat im Startzustand <math>q_0</math>. Da <math>q_0</math> kein Endzustand ist, wird das leere Wort nicht akzeptiert (<math>\varepsilon \notin L</math>).
| |
|
| |
|
| Die Zustandsfolgen dieser Wörter stehen Schritt für Schritt im Beispiel [[Deterministischer endlicher Automat#Wortzugehörigkeit mit einem DEA prüfen|Wortzugehörigkeit mit einem DEA prüfen]]. Einen Automaten, der das leere Wort akzeptiert, zeigt das Beispiel [[Deterministischer endlicher Automat#DEA für Reste entwerfen|DEA für Reste entwerfen]]. | | * '''„Enthält ein Text die Zeichenfolge <code>UML</code>?“''' Die Frage ist entscheidbar. Schon ein [[Deterministischer endlicher Automat|DEA]] wie der [[Endlicher Automat#Spam-Filter als NEA und DEA gegenüberstellen|Spam-Filter]] liest den Text einmal von vorn nach hinten, hält nach dem letzten Zeichen und antwortet mit akzeptiert oder abgelehnt. |
| | * '''„Ist ein Klammerausdruck korrekt geklammert?“''' Die Frage ist entscheidbar. Ein [[Kellerautomat]] liest den Ausdruck einmal und hält bei jeder Eingabe. |
| | * '''„Hält ein beliebiges Programm bei einer beliebigen Eingabe?“''' Die Frage ist unentscheidbar, das ist das Halteproblem. Für einzelne Programme ist die Antwort trotzdem leicht: Ein Programm, das nur aus der Schleife <code>while (true) { }</code> besteht, hält nie. Ein Programm ohne Schleifen und ohne Methodenaufrufe hält immer. Es gibt aber kein Verfahren, das für jedes Programm die richtige Antwort findet. |
|
| |
|
| [[Kategorie:Formale Sprachen]] | | [[Kategorie:Automaten]] |
| [[Kategorie:AHR I Informatik LK]] | | [[Kategorie:AHR I Informatik LK]] |