„Deterministischer endlicher Automat“ – Versionsunterschied
[gesichtete Version] | [gesichtete Version] |
eine erste Lokalisierung (für fachfremde Leser wie mich) |
Abschnitt →Programmierung: hinzugefügt Markierungen: Zurückgesetzt Visuelle Bearbeitung |
||
Zeile 83: | Zeile 83: | ||
Es besteht außerdem die Möglichkeit, minimale deterministische endliche Automaten inkrementell aufzubauen. ''Inkrementell'' bedeutet hier, dass die zu akzeptierenden Worte einzeln dem Automaten hinzugefügt werden. Nach jedem Einfügen eines solchen Wortes ist der deterministische endliche Automat minimal. Dieses Verfahren ist vor allem dann erfolgversprechend, wenn die Worte häufig gemeinsame Prä- und Suffixe teilen, dies ist z. B. bei Worten aus natürlichen Sprachen der Fall. |
Es besteht außerdem die Möglichkeit, minimale deterministische endliche Automaten inkrementell aufzubauen. ''Inkrementell'' bedeutet hier, dass die zu akzeptierenden Worte einzeln dem Automaten hinzugefügt werden. Nach jedem Einfügen eines solchen Wortes ist der deterministische endliche Automat minimal. Dieses Verfahren ist vor allem dann erfolgversprechend, wenn die Worte häufig gemeinsame Prä- und Suffixe teilen, dies ist z. B. bei Worten aus natürlichen Sprachen der Fall. |
||
== Programmierung == |
|||
Das folgende Codebeispiel in der [[Programmiersprache]] [[C++]] zeigt die Implementierung eines deterministischen endlichen Automaten, der alle Vorkommen eines gegebenen Musters in einem Text findet und das Suchergebnis auf der Konsole ausgibt.<syntaxhighlight lang="c++"> |
|||
#include <iostream> |
|||
#include <stdio.h> |
|||
#include <string.h> |
|||
using namespace std; |
|||
#define total_chars 256 |
|||
// Diese Funktion ermittelt den Nachfolgezustand |
|||
int calculateNextState(char* pattern, int m, int state, int symbol) |
|||
{ |
|||
if (state < m && symbol == pattern[state]) |
|||
{ |
|||
return state + 1; |
|||
} |
|||
int i; |
|||
// Diese for-Schleife durchläuft alle Zustände |
|||
for (int nextState = state; nextState > 0; nextState--) |
|||
{ |
|||
if (pattern[nextState - 1] == symbol) |
|||
{ |
|||
for (i = 0; i < nextState - 1; i++) |
|||
{ |
|||
if (pattern[i] != pattern[state - nextState + i + 1]) |
|||
{ |
|||
break; |
|||
} |
|||
} |
|||
if (i == nextState - 1) |
|||
{ |
|||
return nextState; |
|||
} |
|||
} |
|||
} |
|||
return 0; |
|||
} |
|||
// Diese Funktion ermittelt die Werte der Zustandsübergangsfunktion für das gegebene Muster |
|||
void calculateTransitionFunction(char* pattern, int m, int** transitionFunction) |
|||
{ |
|||
// Diese for-Schleife durchläuft alle Zustände |
|||
for (int state = 0; state <= m; state++) |
|||
{ |
|||
// Diese for-Schleife durchläuft alle Zeichen |
|||
for (int symbol = 0; symbol < total_chars; symbol++) |
|||
{ |
|||
transitionFunction[state][symbol] = calculateNextState(pattern, m, state, symbol); // Aufruf der Methode |
|||
} |
|||
} |
|||
} |
|||
// Diese Funktion gibt alle Vorkommen des gegebenen Musters im Text auf der Konsole aus |
|||
void findPattern(char* pattern, char* text) |
|||
{ |
|||
int m = strlen(pattern); // Länge des Musters |
|||
int n = strlen(text); // Länge des Textes |
|||
int** transitionFunction = new int*[n]; |
|||
for (int i = 0; i < m + 1; i++) |
|||
{ |
|||
transitionFunction[i] = new int[total_chars]; |
|||
} |
|||
calculateTransitionFunction(pattern, m, transitionFunction); // Aufruf der Methode |
|||
int state = 0; |
|||
// Diese for-Schleife durchläuft den Text zeichenweise |
|||
for (int i = 0; i < n; i++) |
|||
{ |
|||
state = transitionFunction[state][text[i]]; |
|||
if (state == m) |
|||
{ |
|||
cout << "Das gegebene Muster wurde an der Stelle " << i - m + 1 << " gefunden." << endl; // Ausgabe auf der Konsole |
|||
} |
|||
} |
|||
} |
|||
// Hauptfunktion die das Programm ausführt |
|||
int main() |
|||
{ |
|||
char* text = (char*)"AABCDAABBDCAABADAABDABAABA"; |
|||
char* pattern = (char*)"AABA"; |
|||
findPattern(pattern, text); // Aufruf der Methode |
|||
} |
|||
</syntaxhighlight> |
|||
== Siehe auch == |
== Siehe auch == |
Version vom 10. Oktober 2023, 23:30 Uhr
Ein deterministischer endlicher Automat (DEA; englisch deterministic finite state machine oder deterministic finite automaton, DFA) ist in der theoretischen Informatik ein endlicher Automat, der unter Eingabe eines Zeichens seines Eingabealphabetes (den möglichen Eingaben) von einem Zustand, in dem er sich befindet, in einen eindeutig bestimmten Folgezustand wechselt. Von jedem (Final-)Zustand muss für jedes Zeichen des Eingabealphabets ein Übergang in einen Folgezustand existieren.[1] Er unterscheidet sich darin von nichtdeterministischen endlichen Automaten, deren Zustandswechsel sich nicht immer deterministisch ereignen müssen.
Definition
Automat
Formal kann ein DEA als Quintupel (5-Tupel) definiert werden. Hierbei gilt Folgendes:
- ist eine endliche Zustandsmenge. Weitere oft verwendete Symbole für sind oder .
- ist das endliche Eingabealphabet, also die Menge erlaubter Eingabesymbole.
- ist die Übergangsfunktion (oder Transitionsfunktion). Sie ordnet jedem Paar bestehend aus einem Zustand und einem Eingabesymbol einen Nachfolgezustand zu.
- ist der Startzustand (auch Anfangszustand oder Initalzustand).
- ist die Menge der akzeptierenden Zustände, die sogenannten Finalzustände (oder Endzustände). Ein anderes übliches Symbol für ist .
Verhalten
Befindet sich der Automat in einem Zustand und liest das Eingabesymbol , wechselt er in einen neuen Zustand, der durch die Übergangsfunktion vorgegeben ist, also in den Zustand .
Hat der Automat noch kein Eingabesymbol gelesen, befindet er sich im Startzustand . Erhält der Automat als Eingabe eine Folge von Eingabesymbolen, in der theoretischen Informatik Wort genannt, liest er von links nach rechts ein Symbol nach dem anderen und wechselt gemäß der Übergangsfunktion den Zustand. Befindet sich der Automat nach dem Lesen des letzten Eingabesymbols in einem akzeptierenden Zustand , akzeptiert er die Eingabe. Man sagt dann, dass sich das Eingabewort in der Menge der Wörter befindet, die vom Automaten akzeptiert werden (kurz: die vom Automaten akzeptierte Sprache, siehe unten).
Verworfene Eingaben
Endet der Automat nach dem Lesen eines Eingabewortes in einem nicht-akzeptierenden Zustand, gilt die Eingabe als verworfen. Wenn die Frage, ob die Eingabe verworfen oder akzeptiert wird, sich nicht erst mit dem letzten Eingabesymbol klärt, befindet sich ein minimaler Automat vorzeitig in einem Zustand, den er nicht mehr verlässt.
Sprache eines DEA
Die Menge aller vom DEA akzeptierten Wörter wird als Sprache von bezeichnet. Die Menge aller Sprachen, die von irgendeinem DEA akzeptiert werden, ist die Klasse der regulären Sprachen.
Nichtdeterministische endliche Automaten (NEA), DEA und Typ-3-Grammatiken (in der Chomsky-Hierarchie) beschreiben die gleiche Sprachklasse. NEA lassen sich mittels Potenzmengenkonstruktion in äquivalente DEA wandeln.
Beispiele
Getränkeautomat
Ein deterministischer endlicher Automat, der einfache Abläufe eines Getränkeautomaten nachbildet, kann aus den Zuständen bestehen, welche folgende Zustände des Getränkeautomaten beschreiben: „Getränkeautomat wartet auf Münzeinwurf“, „Getränkeautomat wartet auf Getränkewahl“ und „Getränk wird ausgeschenkt“.
Gültige Eingabesymbole könnten durch die Menge das Einwerfen einer Münze, die Wahl eines Getränks, das Abbrechen der Getränkewahl und die Entnahme eines Getränks beschreiben.
Ein Automat mit den Übergängen
- ,
- ,
- und
beschreibt dann, dass zunächst mit einer Münze bezahlt wird, anschließend ein Getränk gewählt wird, welches entnommen werden muss, bevor wieder von vorne begonnen werden kann. Hat man die Münze eingeworfen, aber noch kein Getränk ausgewählt, kann man auch noch abbrechen.
Verlangt man für die Übergänge eine totale Funktion, muss unter anderem auch ein Zustand angegeben werden, in den der Automat bei Abbruch wechselt, wenn ein Getränk bereits gewählt aber noch nicht entnommen wurde.
-
Grafische Darstellung des DEA aus dem Beispiel
-
Der entsprechende DEA mit totaler Übergangsfunktion
Regulärer Ausdruck
Der reguläre Ausdruck kann als folgender DEA dargestellt werden:
- Zustandsmenge
- Eingabealphabet
- partielle Übergangsfunktion mit
- Finalzustände
-
Grafische Darstellung des DEA aus dem Beispiel
Minimierung
Zu jedem DEA existiert ein (bis auf die Benennung der Zustände) eindeutiger minimaler Automat, der dieselbe Sprache akzeptiert.
Da die Zustände des Minimalautomaten den Äquivalenzklassen der vom endlichen Automaten akzeptierten Sprache unter der Nerode-Relation entsprechen, spricht man auch vom Äquivalenzklassenautomat:
Sei ein deterministischer endlicher Automat. Dann ist mit
der Äquivalenzklassenautomat zu .
Die Minimierung eines deterministischen Automaten kann algorithmisch durch fortwährende Verfeinerung der Äquivalenzklassen gelöst werden. Man beginnt mit den Zustandsmengen und . Für jeden Buchstaben aus dem Alphabet wird nun jede Zustandsmenge dahingehend aufgeteilt, dass die Überführungsfunktion die Zustände jeder neuen Menge den Buchstaben in eine jeweils eindeutige Menge abbildet. Dies wird so oft wiederholt bis sich keine Änderung mehr ergibt.
Es besteht außerdem die Möglichkeit, minimale deterministische endliche Automaten inkrementell aufzubauen. Inkrementell bedeutet hier, dass die zu akzeptierenden Worte einzeln dem Automaten hinzugefügt werden. Nach jedem Einfügen eines solchen Wortes ist der deterministische endliche Automat minimal. Dieses Verfahren ist vor allem dann erfolgversprechend, wenn die Worte häufig gemeinsame Prä- und Suffixe teilen, dies ist z. B. bei Worten aus natürlichen Sprachen der Fall.
Programmierung
Das folgende Codebeispiel in der Programmiersprache C++ zeigt die Implementierung eines deterministischen endlichen Automaten, der alle Vorkommen eines gegebenen Musters in einem Text findet und das Suchergebnis auf der Konsole ausgibt.
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define total_chars 256
// Diese Funktion ermittelt den Nachfolgezustand
int calculateNextState(char* pattern, int m, int state, int symbol)
{
if (state < m && symbol == pattern[state])
{
return state + 1;
}
int i;
// Diese for-Schleife durchläuft alle Zustände
for (int nextState = state; nextState > 0; nextState--)
{
if (pattern[nextState - 1] == symbol)
{
for (i = 0; i < nextState - 1; i++)
{
if (pattern[i] != pattern[state - nextState + i + 1])
{
break;
}
}
if (i == nextState - 1)
{
return nextState;
}
}
}
return 0;
}
// Diese Funktion ermittelt die Werte der Zustandsübergangsfunktion für das gegebene Muster
void calculateTransitionFunction(char* pattern, int m, int** transitionFunction)
{
// Diese for-Schleife durchläuft alle Zustände
for (int state = 0; state <= m; state++)
{
// Diese for-Schleife durchläuft alle Zeichen
for (int symbol = 0; symbol < total_chars; symbol++)
{
transitionFunction[state][symbol] = calculateNextState(pattern, m, state, symbol); // Aufruf der Methode
}
}
}
// Diese Funktion gibt alle Vorkommen des gegebenen Musters im Text auf der Konsole aus
void findPattern(char* pattern, char* text)
{
int m = strlen(pattern); // Länge des Musters
int n = strlen(text); // Länge des Textes
int** transitionFunction = new int*[n];
for (int i = 0; i < m + 1; i++)
{
transitionFunction[i] = new int[total_chars];
}
calculateTransitionFunction(pattern, m, transitionFunction); // Aufruf der Methode
int state = 0;
// Diese for-Schleife durchläuft den Text zeichenweise
for (int i = 0; i < n; i++)
{
state = transitionFunction[state][text[i]];
if (state == m)
{
cout << "Das gegebene Muster wurde an der Stelle " << i - m + 1 << " gefunden." << endl; // Ausgabe auf der Konsole
}
}
}
// Hauptfunktion die das Programm ausführt
int main()
{
char* text = (char*)"AABCDAABBDCAABADAABDABAABA";
char* pattern = (char*)"AABA";
findPattern(pattern, text); // Aufruf der Methode
}
Siehe auch
Literatur
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. 2. Auflage. Pearson Studium, Reading 2002, ISBN 3-8273-7020-5
- Gottfried Vossen, Kurt Ulrich Witt: Grundkurs Theoretische Informatik. 3. Auflage. ISBN 3-528-23147-5
- Peter Sander, Wolffried Stucky, Rudolf Herschel: Automaten, Sprachen, Berechenbarkeit. Teubner, Stuttgart 1992, ISBN 3-519-02937-5
- Uwe Schöning: Ideen der Informatik, Grundlegende Modelle und Konzepte. Oldenbourg, München 2006, ISBN 3-486-57833-2
- Jan Daciuk, Bruce W. Watson, Richard E. Watson, Ul. G. Narutowicza: Incremental Construction of Minimal Acyclic Finite State Automata and Transducers. 1998.
Weblinks
- Automatonsimulator – ein webbasierter, grafischer Editor und Simulator (englisch)
Einzelnachweise
- ↑ Hans Werner Lang: Konstruktion eines deterministischen endlichen Automaten. Hochschule Flensburg, 2007, abgerufen am 9. September 2018.