Contents
Was ist ein endlicher Automat?
Finite Automata (FA) ist die einfachste Maschine zum Erkennen von Mustern. Der endliche Automat oder die endliche Zustandsmaschine ist eine abstrakte Maschine, die fünf Elemente oder Tupel hat. Es hat eine Reihe von Zuständen und Regeln zum Wechseln von einem Zustand in einen anderen, hängt jedoch vom angewendeten Eingabesymbol ab. Im Grunde ist es ein abstraktes Modell eines digitalen Computers.
Ein endlicher Automat besteht aus:
F : Endliche Menge von Zuständen. Σ : Satz von Eingabesymbolen. q : Ausgangszustand. F: Satz von Endzuständen. : Übergangsfunktion.
Was Sie über endliche Automaten wissen müssen
- Endliche Automaten beschreiben die Klasse der regulären Sprachen.
- Endliche Automaten haben eine geringere Rechenleistung als die Turing-Maschine.
- Es besteht aus einer endlichen Anzahl von Zuständen, einer endlichen Menge von Eingabesymbolen, einem Anfangszustand von Automaten und einer endlichen Menge von Übergangsregeln für den Übergang von einem Zustand in einen anderen.
- Das Eingabeband hat eine endliche Länge sowohl von der linken als auch von der rechten Seite.
- Es erkennt die Sprache, die als reguläre Sprache bezeichnet wird.
- Die Übergangsfunktion in endlichen Automaten kann dargestellt werden durch:
δ : Q × Σ* → Q - Das Entwerfen endlicher Automaten ist einfacher.
- Head kann nur die Symbole vom Band lesen, aber keine Symbole auf das Band schreiben.
- Der Kopf kann sich nur in die richtige Richtung bewegen. In Zwei-Wege-Automaten kann sich der Kopf in beide Richtungen bewegen.
- Ein endlicher Automat ist nur eine Menge von Zuständen und Übergängen. Der einzige Speicher, den es hat, ist der Zustand, in dem er sich befindet. Daher ist die Anzahl der Speicherzustände … endlich.
Was ist eine Turingmaschine?
Eine Turingmaschine (TM) ist ein mathematisches Modell, das aus einem unendlich langen Band besteht, das in Zellen unterteilt ist, auf denen Eingaben erfolgen. Es besteht aus einem Kopf, der das Eingabeband liest. Ein Zustandsregister speichert den Zustand der Turingmaschine. Nach dem Lesen eines Eingabesymbols wird es durch ein anderes Symbol ersetzt, sein interner Zustand wird geändert und es bewegt sich von einer Zelle nach rechts oder links. Erreicht das TM den Endzustand, wird der Eingabestring akzeptiert, andernfalls verworfen.
Eine TM kann formal als 7-Tupel (Q, X, ∑, δ, q 0 , B, F) beschrieben werden, wobei −
- Q ist eine endliche Menge von Zuständen
- X ist das Tonbandalphabet
- ∑ ist das Eingabealphabet
- δ eine Übergangsfunktion ist; δ : Q × X → Q × X × {Linksverschiebung, Rechtsverschiebung}.
- q 0 ist der Anfangszustand
- B ist das leere Symbol
- F ist die Menge der Endzustände
Was Sie über Turing-Maschinen wissen müssen
- Turingmaschinen beschreiben eine viel größere Klasse von Sprachen, die Klasse der rekursiv aufzählbaren Sprachen.
- Turing-Maschinen haben mehr Rechenleistung als FSM.
- Es enthält außerdem einen endlichen Satz von Bandsymbolen und ein leeres Symbol auf dem Band zusätzlich zu einer endlichen Anzahl von Zuständen, einem endlichen Satz von Eingabesymbolen, einem Anfangszustand von Automaten und einem endlichen Satz von Übergangsregeln zum Übergang von einem Zustand in einen anderen.
- Das Eingabeband hat eine endliche Länge von links, aber eine unendliche Länge von rechts.
- Es erkennt nicht nur reguläre Sprache, sondern auch kontextfreie Sprache, kontextsensitive Sprache und rekursiv aufzählbare Sprachen.
- Die Übergangsfunktion in einer Turing-Maschine kann dargestellt werden durch: : Q × T → Q × T × {L, R} wobei L und R die linke und rechte Bewegung des Bandkopfes angeben.
- Das Entwerfen einer Turing-Maschine ist sowohl schwierig als auch komplex.
- Der Kopf kann sowohl Symbole auf dem Band lesen als auch schreiben.
- Kopf kann in beide Richtungen bewegt werden.
- Eine Turing-Maschine ist eine endliche Zustandsmaschine plus Bandspeicher. Jeder Übergang kann von einer Operation auf dem Band begleitet sein (verschieben, lesen, schreiben). Seine insgesamt möglichen Konfigurationen sind beliebig groß, unabhängig von der Größe des Programms; es dehnt sich ins Unendliche aus.
Unterschied zwischen endlichen Automaten und Turing-Maschinen in Tabellenform
| VERGLEICHSGRUNDLAGE | FINITE AUTOMATA | TURING MASCHINE |
| Beschreibung | Endliche Automaten beschreiben die Klasse der regulären Sprachen. | Turingmaschinen beschreiben eine viel größere Klasse von Sprachen, die Klasse der rekursiv aufzählbaren Sprachen. |
| Rechenleistung | Endliche Automaten haben eine geringere Rechenleistung als die Turing-Maschine. | Turing-Maschinen haben mehr Rechenleistung als FSM. |
| Zustände | Es besteht aus einer endlichen Anzahl von Zuständen, einer endlichen Menge von Eingabesymbolen, einem Anfangszustand von Automaten und einer endlichen Menge von Übergangsregeln für den Übergang von einem Zustand in einen anderen. | Es enthält außerdem einen endlichen Satz von Bandsymbolen und ein leeres Symbol auf dem Band zusätzlich zu einer endlichen Anzahl von Zuständen, einem endlichen Satz von Eingabesymbolen, einem Anfangszustand von Automaten und einem endlichen Satz von Übergangsregeln zum Übergang von einem Zustand in einen anderen. |
| Eingabelänge | Das Eingabeband hat eine endliche Länge sowohl von der linken als auch von der rechten Seite. | Das Eingabeband hat eine endliche Länge von links, aber eine unendliche Länge von rechts. |
| Spracherkennung | Es erkennt die Sprache, die als reguläre Sprache bezeichnet wird. | Es erkennt nicht nur reguläre Sprache, sondern auch kontextfreie Sprache, kontextsensitive Sprache und rekursiv aufzählbare Sprachen. |
| Übergangsfunktion | Die Übergangsfunktion in endlichen Automaten kann dargestellt werden durch: δ : Q × Σ* → Q | Die Übergangsfunktion in einer Turing-Maschine kann dargestellt werden durch: : Q × T → Q × T × {L, R} wobei L und R die linke und rechte Bewegung des Bandkopfes angeben. |
| Entwerfen | Das Entwerfen endlicher Automaten ist einfacher. | Das Entwerfen einer Turing-Maschine ist sowohl schwierig als auch komplex. |
| Kopf | Head kann nur die Symbole vom Band lesen, aber keine Symbole auf das Band schreiben. | Der Kopf kann sowohl Symbole auf dem Band lesen als auch schreiben. |
| Kopfbewegung | Der Kopf kann sich nur in die richtige Richtung bewegen. In Zwei-Wege-Automaten kann sich der Kopf in beide Richtungen bewegen. | Kopf kann in beide Richtungen bewegt werden. |
| Erinnerung | Ein endlicher Automat ist nur eine Menge von Zuständen und Übergängen. Die einzige Erinnerung, die es hat, ist der Zustand, in dem es sich befindet. | Eine Turing-Maschine ist eine endliche Zustandsmaschine plus Ba |