www.wikidata.de-de.nina.az

Nichtdeterministischer endlicher Automat Ein nichtdeterministischer endlicher Automat NEA englisch nondeterministic fini

Nichtdeterministischer endlicher Automat

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.

Grafische Darstellung eines NEA

Definition Bearbeiten

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 Bearbeiten

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 Bearbeiten

Alternativ lassen sich die Übergänge auch durch eine Transitionsfunktion definieren, die dann in eine Menge von Zuständen abbildet:

Da die Funktion auch auf die leere Menge abbilden kann, sodass gelten kann, ist auch hier ein vorzeitiges Stehenbleiben möglich.

Epsilon-Übergänge Bearbeiten

Ein NEA, der zur Sprache die Sprache erkennt

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 Bearbeiten

Ein NEA mit neuem Startzustand, der mit Epsilon-Übergängen die Startzustände von Teilautomaten verbindet

Es ist auch möglich, mehrere Startzustände zu erlauben.

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 Bearbeiten

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. Diesen Vorgang nennt man Induktive Konstruktion oder auch Thompsons Konstruktion.

Siehe auch Bearbeiten

Literatur Bearbeiten

  • 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 Bearbeiten

Einzelnachweise Bearbeiten

  1. Katrin Erk, Lutz Priese: Theoretische Informatik: Eine umfassende Einführung. 3. Auflage. Springer, 2008, ISBN 3-540-76319-8, Seite 67
  2. Hans Werner Lang: Konstruktion eines nichtdeterministischen endlichen Automaten auf der Seite der Hochschule Flensburg
  3. Alfred V. Aho, Ravi Sethi, Jeffrey Ullman: Compilers: Principles, Techniques and Tools. Addison-Wesley, 1986
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Ein nichtdeterministischer endlicher Automat NEA englisch nondeterministic finite automaton NFA ist ein endlicher Automat bei dem es fur den Zustandsubergang mehrere gleichwertige Moglichkeiten gibt Im Unterschied zum deterministischen endlichen Automaten sind die Moglichkeiten nicht eindeutig dem Automaten ist also nicht vorgegeben welchen Ubergang er zu wahlen hat Grafische Darstellung eines NEA Inhaltsverzeichnis 1 Definition 1 1 Verhalten 1 2 Transition als Funktion 1 3 Epsilon Ubergange 1 4 Mehrere Startzustande 2 Eigenschaften 3 Siehe auch 4 Literatur 5 Weblinks 6 EinzelnachweiseDefinition BearbeitenFormal kann ein NEA A displaystyle mathcal A nbsp als Quintupel 5 Tupel Q S D S F displaystyle left Q Sigma Delta S F right nbsp definiert werden Hierbei gilt Folgendes Q displaystyle Q nbsp ist eine endliche nicht leere Menge von Zustanden Q lt displaystyle left Q right lt infty nbsp S displaystyle Sigma nbsp ist ein endliches nicht leeres Eingabealphabet S lt displaystyle left Sigma right lt infty nbsp D Q S Q displaystyle Delta subseteq Q times Sigma times Q nbsp ist die Ubergangsrelation oder Transitionsrelation S Q displaystyle S in Q nbsp ist der Startzustand F Q displaystyle F subseteq Q nbsp ist eine endliche Menge moglicher akzeptierender Zustande Finalzustande Wenn der Automat nach Lesen des Eingabewortes w S displaystyle w in Sigma nbsp in einem Zustand aus F displaystyle F nbsp fallt so gehort w displaystyle w nbsp zur Sprache L A displaystyle L left mathcal A right nbsp Verhalten Bearbeiten Liest der NEA in einem Zustand q displaystyle q nbsp das Eingabesymbol a displaystyle a nbsp dann wechselt er nichtdeterministisch in einen Nachfolgezustand der durch die Ubergangsrelation gegeben ist Der Automat hat also die Wahl zwischen allen Zustanden p displaystyle p nbsp fur die q a p D displaystyle q a p in Delta nbsp gilt Gibt es keinen solchen Zustand bleibt der Automat vorzeitig stehen und verwirft die Eingabe Ein Eingabewort w displaystyle w nbsp gilt dann als akzeptiert wenn es fur w displaystyle w nbsp eine durch D displaystyle Delta nbsp gegebene Folge von Zustandswechseln gibt bei der der Automat nicht vorzeitig stehen bleibt und der letzte Zustand ein akzeptierender Zustand ist Transition als Funktion Bearbeiten Alternativ lassen sich die Ubergange auch durch eine Transitionsfunktion definieren die dann in eine Menge von Zustanden abbildet A Q S d S F displaystyle mathcal A left Q Sigma delta S F right nbsp mit d Q S P Q displaystyle delta colon Q times Sigma to mathcal P Q nbsp Da die Funktion auch auf die leere Menge abbilden kann sodass d q a displaystyle delta q a varnothing nbsp gelten kann ist auch hier ein vorzeitiges Stehenbleiben moglich Epsilon Ubergange Bearbeiten nbsp Ein NEA der zur Sprache a displaystyle alpha nbsp die Sprache a displaystyle alpha nbsp erkenntMan kann NEAs auch so definieren dass Zustandsubergange moglich sind bei denen kein Eingabezeichen gelesen wird Vor oder nach dem Lesen eines Zeichens kann ein NEA also zusatzlich den Zustand wechseln Die Zustande die gewechselt werden konnen werden durch Ubergange verbunden die statt eines Symbols das leere Wort e displaystyle varepsilon nbsp manchmal auch l displaystyle lambda nbsp lesen Diese Zustandswechsel werden e displaystyle varepsilon nbsp Ubergange oder e displaystyle varepsilon nbsp Schritte genannt Bei grafischen Reprasentationen von NEAs werden die Ubergange als mit e displaystyle varepsilon nbsp oder l displaystyle lambda nbsp beschriftete Kanten dargestellt und deshalb auch e displaystyle varepsilon nbsp Kanten genannt Formal ermoglicht man diese Ubergange indem man die Transitionsrelation erweitert D Q S e Q displaystyle Delta subseteq Q times Sigma cup varepsilon times Q nbsp Dabei ist sicherzustellen dass e displaystyle varepsilon nbsp nicht bereits in S displaystyle Sigma nbsp vorhanden ist sondern ausschliesslich das leere Wort reprasentiert NEAs mit Epsilon Ubergangen konnen nicht mehr Worter erkennen als ohne diese Erweiterung Zu einem NEA mit Epsilon Ubergangen gibt es also immer einen aquivalenten NEA ohne Epsilon Ubergange Sie konnen aber die Konstruktion mancher Automaten vereinfachen Beispielsweise kann man zu einem NEA A displaystyle mathcal A nbsp mit wenig Aufwand einen Automaten A displaystyle mathcal A nbsp konstruieren der die Kleene sche Hulle der Sprache von A displaystyle mathcal A nbsp akzeptiert also L A L A displaystyle mathcal L mathcal A mathcal L mathcal A nbsp Mehrere Startzustande Bearbeiten nbsp Ein NEA mit neuem Startzustand der mit Epsilon Ubergangen die Startzustande von Teilautomaten verbindetEs ist auch moglich mehrere Startzustande zu erlauben 1 Der Automat ist dann definiert als A Q S D S F displaystyle mathcal A left Q Sigma Delta S F right nbsp mit S Q displaystyle S subseteq Q nbsp Solche Automaten lassen sich mittels e displaystyle varepsilon nbsp Ubergangen in NEAs mit genau einem Startzustand uberfuhren indem man einen neuen Zustand einfuhrt von dem aus man die ursprunglichen Startzustande durch e displaystyle varepsilon nbsp Ubergange erreicht Auf diese Weise kann man zu zwei Automaten A B displaystyle mathcal A mathcal B nbsp einen NEA C displaystyle mathcal C nbsp erstellen dessen Sprache die Vereinigung der Sprachen der beiden anderen Automaten ist also L C L A L B displaystyle mathcal L mathcal C mathcal L mathcal A cup mathcal L mathcal B nbsp Bei disjunkten Zustandsmengen von A displaystyle mathcal A nbsp und B displaystyle mathcal B nbsp muss man nur einen neuen Startzustand einfuhren der uber Epsilon Ubergange mit den Startzustanden der beiden Automaten verbunden ist Die Menge der akzeptierenden Zustande ist die Vereinigung der akzeptierenden Zustande der beiden Automaten Eigenschaften BearbeitenNEAs DEAs und Typ 3 Grammatiken vgl Chomsky Hierarchie beschreiben die gleiche Sprachklasse NEAs lassen sich mittels Potenzmengenkonstruktion in aquivalente DEAs umwandeln Der wesentliche Unterschied des NEA zum deterministischen endlichen Automaten DEA liegt somit darin dass auch mehrere Folgezustande moglich sind oder auch ganz fehlen konnen Es handelt sich hierbei allerdings nicht um zwei verschiedene Arten sondern ein DEA ist eine Sonderform des NEAs Um einen regularen Ausdruck in einen NEA zu uberfuhren sind gewisse Regeln zu befolgen 2 Diesen Vorgang nennt man Induktive Konstruktion oder auch Thompsons Konstruktion 3 Siehe auch BearbeitenPotenzautomat Eindeutiger endlicher AutomatLiteratur BearbeitenJohn E Hopcroft Jeffrey Ullman Einfuhrung in die Automatentheorie formale Sprachen und Komplexitatstheorie 2 Auflage Addison Wesley Bonn Munchen 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 5Weblinks BearbeitenHans Werner Lang Theoretische Informatik Artikel zum Themengebiet auf der Seite der Hochschule FlensburgEinzelnachweise Bearbeiten Katrin Erk Lutz Priese Theoretische Informatik Eine umfassende Einfuhrung 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 Abgerufen von https de wikipedia org w index php title Nichtdeterministischer endlicher Automat amp oldid 238359945