„Nichtdeterministischer endlicher Automat“ – Versionsunterschied
[gesichtete Version] | [gesichtete Version] |
K Änderungen von 217.224.1.194 (Diskussion) auf die letzte Version von Leyo zurückgesetzt Markierung: Zurücksetzung |
Abschnitt →Programmierung: hinzugefügt Markierungen: Zurückgesetzt Visuelle Bearbeitung |
||
Zeile 56: | Zeile 56: | ||
Um einen [[Regulärer Ausdruck|regulären Ausdruck]] in einen NEA zu überführen, sind gewisse Regeln zu befolgen.<ref>Hans Werner Lang: ''[https://www.inf.hs-flensburg.de/lang/theor/regulaerer-ausdruck-zu-automat-bottomup.htm Konstruktion eines nichtdeterministischen endlichen Automaten]'' auf der Seite der [[Hochschule Flensburg (Fachhochschule)|Hochschule Flensburg]]</ref> |
Um einen [[Regulärer Ausdruck|regulären Ausdruck]] in einen NEA zu überführen, sind gewisse Regeln zu befolgen.<ref>Hans Werner Lang: ''[https://www.inf.hs-flensburg.de/lang/theor/regulaerer-ausdruck-zu-automat-bottomup.htm Konstruktion eines nichtdeterministischen endlichen Automaten]'' auf der Seite der [[Hochschule Flensburg (Fachhochschule)|Hochschule Flensburg]]</ref> |
||
Diesen Vorgang nennt man ''Induktive Konstruktion'' oder auch ''Thompsons Konstruktion''.<ref>[[Alfred V. Aho]], Ravi Sethi, [[Jeffrey Ullman]]: ''Compilers: Principles, Techniques and Tools.'' Addison-Wesley, 1986</ref> |
Diesen Vorgang nennt man ''Induktive Konstruktion'' oder auch ''Thompsons Konstruktion''.<ref>[[Alfred V. Aho]], Ravi Sethi, [[Jeffrey Ullman]]: ''Compilers: Principles, Techniques and Tools.'' Addison-Wesley, 1986</ref> |
||
== Programmierung == |
|||
Das folgende Codebeispiel in der [[Programmiersprache]] [[C++]] zeigt die Implementierung eines nichtdeterministischen endlichen Automaten, der eine binäre [[Zeichenkette]] auf Korrektheit prüft.<ref>GeeksforGeeks: [https://www.geeksforgeeks.org/c-program-to-simulate-nondeterministic-finite-automata-nfa/ C program to simulate Nondeterministic Finite Automata (NFA)]</ref> |
|||
{| class="wikitable left mw-collapsible mw-collapsed font-size: 105.3%;" |
|||
| style="text-align:left; font-size: 95%;" |'''Code-Schnipsel''' |
|||
|- |
|||
|<syntaxhighlight lang="c++"> |
|||
#include <stdio.h> |
|||
#include <stdlib.h> |
|||
#include <string.h> |
|||
#include <stdbool.h> |
|||
#include <math.h> |
|||
int row = 0; |
|||
// A structure to represent an adjacency list node |
|||
struct node |
|||
{ |
|||
int data; |
|||
struct node* next; |
|||
char edgetype; |
|||
} |
|||
typedef node; |
|||
// Adds an edge to an adjacency list |
|||
node* push(node* first, char edgetype, int data) |
|||
{ |
|||
node* new_node = (node*)malloc(sizeof(node)); |
|||
new_node->edgetype = edgetype; |
|||
new_node->data = data; |
|||
new_node->next = NULL; |
|||
if (first == NULL) |
|||
{ |
|||
first = new_node; |
|||
return new_node; |
|||
} |
|||
first->next = push(first->next, edgetype, data); |
|||
return first; |
|||
} |
|||
//Recursive function to check acceptance of input |
|||
int nfa(node** graph, int current, char* input, int* accept, int start) |
|||
{ |
|||
if (start == (int)strlen(input)) |
|||
{ |
|||
return accept[current]; |
|||
} |
|||
node* temp = graph[current]; |
|||
while (temp != NULL) |
|||
{ |
|||
if (input[start] == temp->edgetype) |
|||
{ |
|||
if (nfa(graph, temp->data, input, accept, start + 1 == 1)) |
|||
{ |
|||
return 1; |
|||
} |
|||
temp = temp->next; |
|||
} |
|||
} |
|||
return 0; |
|||
} |
|||
//Function to generate binary strings of size n |
|||
void generate(char** arr, int size, char* a) |
|||
{ |
|||
if (size == 0) |
|||
{ |
|||
strcpy_s(arr[row], sizeof(arr), a); |
|||
row++; |
|||
return; |
|||
} |
|||
char b0[20] = { '\0' }; |
|||
char b1[20] = { '\0' }; |
|||
b0[0] = '0'; |
|||
b1[0] = '1'; |
|||
//Recursively generate the binary string |
|||
generate((char**)arr, size - 1, b0 + *a); //Add 0 in front |
|||
generate((char**)arr, size - 1, b1 + *a); //Add 1 in front |
|||
return; |
|||
} |
|||
// Driver program to test above functions |
|||
int main() |
|||
{ |
|||
int n; |
|||
int i, j; |
|||
scanf_s("%d", &n); //Number of nodes |
|||
node* graph = new node[n + 1]; //Create a graph |
|||
for (int i = 0; i < n + 1; i++) |
|||
{ |
|||
(&graph)[i] = NULL; |
|||
} |
|||
int* accept = new int[n + 1]; //Array to store state of vertex |
|||
for (int i = 0; i < n; i++) |
|||
{ |
|||
//Index of vertex , Acceptance state , Number of edges |
|||
int index, acc, number_nodes; |
|||
scanf_s("%d%d%d", &index, &acc, &number_nodes); |
|||
accept[index] = acc; //Store acceptance |
|||
for (int j = 0; j < number_nodes; j++) //Add all edges |
|||
{ |
|||
int node_add; |
|||
int edge; |
|||
scanf_s("%d%d", &edge, &node_add); |
|||
(&graph)[index] = push(&graph[index], '0' + edge, node_add); |
|||
} |
|||
} |
|||
int size = 1; //Size of input |
|||
int count = 0; //Keep count of output strings |
|||
if (accept[1] == 1) //Check for empty string |
|||
{ |
|||
printf("e\n"); |
|||
count++; |
|||
} |
|||
while (count < 11) |
|||
{ |
|||
char** arr; |
|||
int power = pow(2, size); |
|||
arr = (char**)malloc(power * sizeof(char*)); |
|||
for (i = 0;i < power;i++) |
|||
{ |
|||
arr[i] = (char*)malloc(size * sizeof(char)); |
|||
} |
|||
char a[20] = { '\0' }; |
|||
generate((char**)arr, size, a); //Generate inputs |
|||
for (i = 0; i < power; i++) |
|||
{ |
|||
char input[20] = { '\0' }; |
|||
for (j = 0; j < size; j++) |
|||
{ |
|||
char foo[2]; |
|||
foo[0] = arr[i][size - 1 - j]; |
|||
foo[1] = '\0'; |
|||
strcat_s(input, foo); |
|||
//Copy generated string input |
|||
} |
|||
int result = nfa(&graph, 1, input, accept, 0); |
|||
// Store result of nfa |
|||
if (result == 1) |
|||
{ |
|||
printf("%s\n", input); |
|||
// Print if accepted |
|||
count++; |
|||
} |
|||
if (count == 10) |
|||
{ |
|||
return 0; |
|||
} |
|||
} |
|||
size++; //Increment size of binary string input |
|||
row = 0; |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
|} |
|||
== Siehe auch == |
== Siehe auch == |
Version vom 20. Oktober 2023, 23:15 Uhr
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f9/NFASimpleExample.svg/220px-NFASimpleExample.svg.png)
Ein nichtdeterministischer endlicher Automat (NEA; englisch nondeterministic finite automaton, NFA) ist ein endlicher Automat, bei dem es für den Zustandsübergang mehrere gleichwertige Möglichkeiten gibt. Im Unterschied zum deterministischen endlichen Automaten sind die Möglichkeiten nicht eindeutig, dem Automaten ist also nicht vorgegeben, welchen Übergang er zu wählen hat.
Definition
Formal kann ein NEA als Quintupel (5-Tupel) definiert werden. Hierbei gilt Folgendes:
- ist eine endliche, nicht leere Menge von Zuständen ().
- ist ein endliches, nicht leeres Eingabealphabet, .
- ist die Übergangsrelation (oder Transitionsrelation).
- ist der Startzustand.
- ist eine (endliche) Menge möglicher akzeptierender Zustände (Finalzustände). Wenn der Automat nach Lesen des Eingabewortes in einem Zustand aus fällt, so gehört zur Sprache .
Verhalten
Liest der NEA in einem Zustand das Eingabesymbol , dann wechselt er nichtdeterministisch in einen Nachfolgezustand, der durch die Übergangsrelation gegeben ist. Der Automat hat also die Wahl zwischen allen Zuständen , für die gilt.
Gibt es keinen solchen Zustand, bleibt der Automat vorzeitig stehen und verwirft die Eingabe.
Ein Eingabewort gilt dann als akzeptiert, wenn es für eine durch gegebene Folge von Zustandswechseln gibt, bei der der Automat nicht vorzeitig stehen bleibt und der letzte Zustand ein akzeptierender Zustand ist.
Transition als Funktion
Alternativ lassen sich die Übergänge auch durch eine Transitionsfunktion definieren, die dann in eine Menge von Zuständen abbildet:
- mit
Da die Funktion auch auf die leere Menge abbilden kann, sodass gelten kann, ist auch hier ein vorzeitiges Stehenbleiben möglich.
Epsilon-Übergänge
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c7/NFA_regexp_kleene.svg/220px-NFA_regexp_kleene.svg.png)
Man kann NEAs auch so definieren, dass Zustandsübergänge möglich sind, bei denen kein Eingabezeichen gelesen wird. Vor oder nach dem Lesen eines Zeichens kann ein NEA also zusätzlich den Zustand wechseln. Die Zustände, die gewechselt werden können, werden durch Übergänge verbunden, die statt eines Symbols das leere Wort (manchmal auch ) lesen. Diese Zustandswechsel werden -Übergänge oder -Schritte genannt. Bei grafischen Repräsentationen von NEAs werden die Übergänge als mit (oder ) beschriftete Kanten dargestellt und deshalb auch -Kanten genannt.
Formal ermöglicht man diese Übergänge, indem man die Transitionsrelation erweitert:
Dabei ist sicherzustellen, dass nicht bereits in vorhanden ist, sondern ausschließlich das leere Wort repräsentiert.
NEAs mit Epsilon-Übergängen können nicht mehr Wörter erkennen als ohne diese Erweiterung. Zu einem NEA mit Epsilon-Übergängen gibt es also immer einen äquivalenten NEA ohne Epsilon-Übergänge. Sie können aber die Konstruktion mancher Automaten vereinfachen. Beispielsweise kann man zu einem NEA mit wenig Aufwand einen Automaten konstruieren, der die Kleene'sche Hülle der Sprache von akzeptiert, also .
Mehrere Startzustände
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/55/NFA_regexp_sum.svg/220px-NFA_regexp_sum.svg.png)
Es ist auch möglich, mehrere Startzustände zu erlauben.[1]
Der Automat ist dann definiert als mit .
Solche Automaten lassen sich mittels -Übergängen in NEAs mit genau einem Startzustand überführen, indem man einen neuen Zustand einführt, von dem aus man die ursprünglichen Startzustände durch -Übergänge erreicht.
Auf diese Weise kann man zu zwei Automaten einen NEA erstellen, dessen Sprache die Vereinigung der Sprachen der beiden anderen Automaten ist, also . Bei disjunkten Zustandsmengen von und muss man nur einen neuen Startzustand einführen, der über Epsilon-Übergänge mit den Startzuständen der beiden Automaten verbunden ist. Die Menge der akzeptierenden Zustände ist die Vereinigung der akzeptierenden Zustände der beiden Automaten.
Eigenschaften
NEAs, DEAs und Typ-3-Grammatiken (vgl. Chomsky-Hierarchie) beschreiben die gleiche Sprachklasse. NEAs lassen sich mittels Potenzmengenkonstruktion in äquivalente DEAs umwandeln.
Der wesentliche Unterschied des NEA zum deterministischen endlichen Automaten (DEA) liegt somit darin, dass auch mehrere Folgezustände möglich sind oder auch ganz fehlen können. Es handelt sich hierbei allerdings nicht um zwei verschiedene Arten, sondern ein DEA ist eine Sonderform des NEAs.
Um einen regulären Ausdruck in einen NEA zu überführen, sind gewisse Regeln zu befolgen.[2] Diesen Vorgang nennt man Induktive Konstruktion oder auch Thompsons Konstruktion.[3]
Programmierung
Das folgende Codebeispiel in der Programmiersprache C++ zeigt die Implementierung eines nichtdeterministischen endlichen Automaten, der eine binäre Zeichenkette auf Korrektheit prüft.[4]
Code-Schnipsel |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
int row = 0;
// A structure to represent an adjacency list node
struct node
{
int data;
struct node* next;
char edgetype;
}
typedef node;
// Adds an edge to an adjacency list
node* push(node* first, char edgetype, int data)
{
node* new_node = (node*)malloc(sizeof(node));
new_node->edgetype = edgetype;
new_node->data = data;
new_node->next = NULL;
if (first == NULL)
{
first = new_node;
return new_node;
}
first->next = push(first->next, edgetype, data);
return first;
}
//Recursive function to check acceptance of input
int nfa(node** graph, int current, char* input, int* accept, int start)
{
if (start == (int)strlen(input))
{
return accept[current];
}
node* temp = graph[current];
while (temp != NULL)
{
if (input[start] == temp->edgetype)
{
if (nfa(graph, temp->data, input, accept, start + 1 == 1))
{
return 1;
}
temp = temp->next;
}
}
return 0;
}
//Function to generate binary strings of size n
void generate(char** arr, int size, char* a)
{
if (size == 0)
{
strcpy_s(arr[row], sizeof(arr), a);
row++;
return;
}
char b0[20] = { '\0' };
char b1[20] = { '\0' };
b0[0] = '0';
b1[0] = '1';
//Recursively generate the binary string
generate((char**)arr, size - 1, b0 + *a); //Add 0 in front
generate((char**)arr, size - 1, b1 + *a); //Add 1 in front
return;
}
// Driver program to test above functions
int main()
{
int n;
int i, j;
scanf_s("%d", &n); //Number of nodes
node* graph = new node[n + 1]; //Create a graph
for (int i = 0; i < n + 1; i++)
{
(&graph)[i] = NULL;
}
int* accept = new int[n + 1]; //Array to store state of vertex
for (int i = 0; i < n; i++)
{
//Index of vertex , Acceptance state , Number of edges
int index, acc, number_nodes;
scanf_s("%d%d%d", &index, &acc, &number_nodes);
accept[index] = acc; //Store acceptance
for (int j = 0; j < number_nodes; j++) //Add all edges
{
int node_add;
int edge;
scanf_s("%d%d", &edge, &node_add);
(&graph)[index] = push(&graph[index], '0' + edge, node_add);
}
}
int size = 1; //Size of input
int count = 0; //Keep count of output strings
if (accept[1] == 1) //Check for empty string
{
printf("e\n");
count++;
}
while (count < 11)
{
char** arr;
int power = pow(2, size);
arr = (char**)malloc(power * sizeof(char*));
for (i = 0;i < power;i++)
{
arr[i] = (char*)malloc(size * sizeof(char));
}
char a[20] = { '\0' };
generate((char**)arr, size, a); //Generate inputs
for (i = 0; i < power; i++)
{
char input[20] = { '\0' };
for (j = 0; j < size; j++)
{
char foo[2];
foo[0] = arr[i][size - 1 - j];
foo[1] = '\0';
strcat_s(input, foo);
//Copy generated string input
}
int result = nfa(&graph, 1, input, accept, 0);
// Store result of nfa
if (result == 1)
{
printf("%s\n", input);
// Print if accepted
count++;
}
if (count == 10)
{
return 0;
}
}
size++; //Increment size of binary string input
row = 0;
}
}
|
Siehe auch
Einzelnachweise
- ↑ Katrin Erk, Lutz Priese: Theoretische Informatik: Eine umfassende Einführung. 3. Auflage. Springer, 2008, ISBN 3-540-76319-8, Seite 67
- ↑ Hans Werner Lang: Konstruktion eines nichtdeterministischen endlichen Automaten auf der Seite der Hochschule Flensburg
- ↑ Alfred V. Aho, Ravi Sethi, Jeffrey Ullman: Compilers: Principles, Techniques and Tools. Addison-Wesley, 1986
- ↑ GeeksforGeeks: C program to simulate Nondeterministic Finite Automata (NFA)
Literatur
- John E. Hopcroft, Jeffrey Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2. Auflage. Addison-Wesley, Bonn / München 1990, ISBN 3-89319-181-X (englisch, Originaltitel: Introduction to automata theory, languages and computation.).
- Peter Sander, Wolffried Stucky, Rudolf Herschel: Automaten, Sprachen, Berechenbarkeit. ISBN 3-519-02937-5
- Gottfried Vossen, Kurt-Ulrich Witt: Grundkurs Theoretische Informatik. 3. Auflage. ISBN 3-528-23147-5
Weblinks
- Hans Werner Lang: Theoretische Informatik (Artikel zum Themengebiet) auf der Seite der Hochschule Flensburg