Nicht-deterministischer endlicher Automaten - Versionsgeschichte

Akaibel: /* Beziehung zu deterministischen endlichen Automaten */

2023-11-09T19:41:09Z

Beziehung zu deterministischen endlichen Automaten

@@ Zeile 25: / Zeile 25: @@
 * Zu jedem Nicht-deterministischen endlichen Automaten kann man eine deterministischen endlichen Automaten konstruieren.
 ** Das Verfahren dazu heißt '''[[Potenzmengenkonstruktion]]''' und ist reichlich kompliziert, funktioniert aber immer!<br/>(Das ist mathematisch bewiesen...)
 =Beziehung zu regulären Grammatiken=

Akaibel: /* Beziehung zu regulären Grammatiken */

2022-02-14T19:10:51Z

Beziehung zu regulären Grammatiken

← Nächstältere Version		Version vom 14. Februar 2022, 19:10 Uhr
Zeile 27:		Zeile 27:

	=Beziehung zu regulären Grammatiken=		=Beziehung zu regulären Grammatiken=
			[[Datei:DEA-RG-NEA-reg-Sprache.png\|400px\|thumb\|right\|Beziehungen: Reguläre Grammatik - DEA - NEA - reguläre Sprache]]
	* '''Zu jedem nicht-deterministischen endlichen Automaten lässt sich einfach eine [[Reguläre Grammatik\|reguläre Grammatik]] konstruieren:'''		* '''Zu jedem nicht-deterministischen endlichen Automaten lässt sich einfach eine [[Reguläre Grammatik\|reguläre Grammatik]] konstruieren:'''
	** Aus jedem Zustand des Automaten macht man ein Nicht-Terminal in der Grammatik - und der Rest ergibt sich von selbst.		** Aus jedem Zustand des Automaten macht man ein Nicht-Terminal in der Grammatik - und der Rest ergibt sich von selbst.

Akaibel: /* Beispiel */

2019-06-23T13:47:39Z

Beispiel

← Nächstältere Version		Version vom 23. Juni 2019, 13:47 Uhr
Zeile 7:		Zeile 7:
	* '''Die Übergänge zwischen den Zuständen sind <u>nicht eindeutig</u>.'''<br/>D.h. es kann für ein Symbol und einen Zustand mehrere mögliche Übergänge geben.		* '''Die Übergänge zwischen den Zuständen sind <u>nicht eindeutig</u>.'''<br/>D.h. es kann für ein Symbol und einen Zustand mehrere mögliche Übergänge geben.
	* '''Ein Wort gilt als akzeptiert, wenn es für das Wort einen Übergang vom Anfangs- in einen Endzustand <u>gibt</u>.'''<br/>D.h.: Nicht jeder "Weg" muss zu einem Endzustand führen - es reicht, wenn es einen Weg gibt! <br/>''Und der "richtige" Weg ist manchmal ziemlich schwer zu finden...''		* '''Ein Wort gilt als akzeptiert, wenn es für das Wort einen Übergang vom Anfangs- in einen Endzustand <u>gibt</u>.'''<br/>D.h.: Nicht jeder "Weg" muss zu einem Endzustand führen - es reicht, wenn es einen Weg gibt! <br/>''Und der "richtige" Weg ist manchmal ziemlich schwer zu finden...''

			=Fachbegriffe=
			Nicht-Deterministischer endlicher Automat (NEA), Zustand, Anfangszustand, Endzustände, Alphabet, Übergang, Zustandsübergangsfunktion, Übergangsgraph, prüfen, "es gibt einen Weg"

	=Beispiel=		=Beispiel=

	[[File:Automat007nichtDeterministisch.png\|thumb\|Der KGB-Automat als <u>Nicht</u>-deterministischer endlicher Automat. \|557px]]		[[File:Automat007nichtDeterministisch.png\|thumb\|Der KGB-Automat als <u>Nicht</u>-deterministischer endlicher Automat. \|557px]]

Akaibel: /* Beziehung zu regulären Grammatiken */

2019-02-11T17:08:54Z

Beziehung zu regulären Grammatiken

← Nächstältere Version		Version vom 11. Februar 2019, 17:08 Uhr
Zeile 23:		Zeile 23:

	=Beziehung zu regulären Grammatiken=		=Beziehung zu regulären Grammatiken=
	* Zu jeder [[Reguläre Grammatik\|regulären Grammatik]] lässt sich einfach ein nicht-deterministischer endlicher Automat konstruieren:		* '''Zu jedem nicht-deterministischen endlichen Automaten lässt sich einfach eine [[Reguläre Grammatik\|reguläre Grammatik]] konstruieren:'''
			** Aus jedem Zustand des Automaten macht man ein Nicht-Terminal in der Grammatik - und der Rest ergibt sich von selbst.
			* '''Zu jeder [[Reguläre Grammatik\|regulären Grammatik]] lässt sich einfach ein nicht-deterministischer endlicher Automat konstruieren:'''
	** Aus jedem Nichtterminalsymbol wird einen Zustand des Automaten gemacht und aus jeder Produktionsregel einen Übergang des Automaten.		** Aus jedem Nichtterminalsymbol wird einen Zustand des Automaten gemacht und aus jeder Produktionsregel einen Übergang des Automaten.
	* Der Nicht-deterministische endliche Automat ist deswegen ein Zwischenschritt beim Übergang von der [[Reguläre Grammatik\|regulären Grammatik]] zum [[Deterministischer Endlicher Automat\|deterministischen endlichen Automaten]].		** Der Nicht-deterministische endliche Automat ist deswegen ein Zwischenschritt beim Übergang von der [[Reguläre Grammatik\|regulären Grammatik]] zum [[Deterministischer Endlicher Automat\|deterministischen endlichen Automaten]].

Akaibel am 11. Februar 2019 um 17:05 Uhr

2019-02-11T17:05:31Z

← Nächstältere Version		Version vom 11. Februar 2019, 17:05 Uhr
Zeile 4:		Zeile 4:
	[[Kategorie:Informatik]]		[[Kategorie:Informatik]]

	Nichtdeterministische endliche Automaten unterscheiden sich von [[Deterministischer Endlicher Automat\|Deterministischen endlichen Automaten]] ~~nur~~ in ~~einem~~ wesentlichen ~~Punkt~~:		Nichtdeterministische endliche Automaten unterscheiden sich von [[Deterministischer Endlicher Automat\|Deterministischen endlichen Automaten]] in zwei wesentlichen Punkten:
	* '''Die Übergänge zwischen den Zuständen sind <u>nicht eindeutig</u>.		* '''Die Übergänge zwischen den Zuständen sind <u>nicht eindeutig</u>.'''<br/>D.h. es kann für ein Symbol und einen Zustand mehrere mögliche Übergänge geben.
	D.h. es kann für ein Symbol und einen Zustand mehrere mögliche Übergänge geben.		* '''Ein Wort gilt als akzeptiert, wenn es für das Wort einen Übergang vom Anfangs- in einen Endzustand <u>gibt</u>.'''<br/>D.h.: Nicht jeder "Weg" muss zu einem Endzustand führen - es reicht, wenn es einen Weg gibt! <br/>''Und der "richtige" Weg ist manchmal ziemlich schwer zu finden...''

	Ein Wort gilt als ~~'''~~akzeptiert~~'''~~, wenn es für das Wort einen Übergang vom Anfangs- in einen Endzustand gibt.

	=Beispiel=		=Beispiel=

Akaibel: /* Beziehung zu deterministischen endlichen Automaten */

2019-02-11T17:00:37Z

Beziehung zu deterministischen endlichen Automaten

← Nächstältere Version		Version vom 11. Februar 2019, 17:00 Uhr
Zeile 21:		Zeile 21:
	=Beziehung zu deterministischen endlichen Automaten=		=Beziehung zu deterministischen endlichen Automaten=
	* Jeder deterministische endliche Automat ist (ohne irgendwelches Dazutun) direkt auch ein Nicht-deterministischer endlicher Automat.		* Jeder deterministische endliche Automat ist (ohne irgendwelches Dazutun) direkt auch ein Nicht-deterministischer endlicher Automat.
	* Zu jedem Nicht-deterministischen endlichen Automaten kann man eine deterministischen endlichen Automaten konstruieren. Das Verfahren dazu heißt '''[[Potenzmengenkonstruktion]]''' und ist reichlich kompliziert, funktioniert aber immer! (Das ist mathematisch bewiesen...)		* Zu jedem Nicht-deterministischen endlichen Automaten kann man eine deterministischen endlichen Automaten konstruieren.
			** Das Verfahren dazu heißt '''[[Potenzmengenkonstruktion]]''' und ist reichlich kompliziert, funktioniert aber immer!<br/>(Das ist mathematisch bewiesen...)

	=Beziehung zu regulären Grammatiken=		=Beziehung zu regulären Grammatiken=

Akaibel: /* Beziehung zu deterministischen endlichen Automaten */

2019-02-11T16:49:06Z

Beziehung zu deterministischen endlichen Automaten

← Nächstältere Version		Version vom 11. Februar 2019, 16:49 Uhr
Zeile 21:		Zeile 21:
	=Beziehung zu deterministischen endlichen Automaten=		=Beziehung zu deterministischen endlichen Automaten=
	* Jeder deterministische endliche Automat ist (ohne irgendwelches Dazutun) direkt auch ein Nicht-deterministischer endlicher Automat.		* Jeder deterministische endliche Automat ist (ohne irgendwelches Dazutun) direkt auch ein Nicht-deterministischer endlicher Automat.
	* Zu jedem Nicht-deterministischen endlichen Automaten kann man eine deterministischen endlichen Automaten konstruieren. Das Verfahren ist kompliziert, aber mathematisch bewiesen~~; Details dazu unter [http://de~~.~~wikipedia~~.~~org/wiki/Potenzmengenkonstruktion]~~		* Zu jedem Nicht-deterministischen endlichen Automaten kann man eine deterministischen endlichen Automaten konstruieren. Das Verfahren dazu heißt '''[[Potenzmengenkonstruktion]]''' und ist reichlich kompliziert, funktioniert aber immer! (Das ist mathematisch bewiesen...)

	=Beziehung zu regulären Grammatiken=		=Beziehung zu regulären Grammatiken=

Akaibel am 23. Februar 2015 um 09:13 Uhr

2015-02-23T09:13:19Z

← Nächstältere Version		Version vom 23. Februar 2015, 09:13 Uhr
Zeile 1:		Zeile 1:
	Nichtdeterministische endliche Automaten unterscheiden sich von [[Deterministischen endlichen Automaten~~\|Deterministischer Endlicher Automat~~]] nur in einem wesentlichen Punkt:		[[Kategorie:endliche Automaten]]
			[[Kategorie:Informatik-Q2]]
			[[Kategorie:Informatik-Abitur]]
			[[Kategorie:Informatik]]

			Nichtdeterministische endliche Automaten unterscheiden sich von [[Deterministischer Endlicher Automat\|Deterministischen endlichen Automaten]] nur in einem wesentlichen Punkt:
	* '''Die Übergänge zwischen den Zuständen sind <u>nicht eindeutig</u>.		* '''Die Übergänge zwischen den Zuständen sind <u>nicht eindeutig</u>.
	D.h. es kann für ein Symbol und einen Zustand mehrere mögliche Übergänge geben.		D.h. es kann für ein Symbol und einen Zustand mehrere mögliche Übergänge geben.

Akaibel: Die Seite wurde neu angelegt: „Nichtdeterministische endliche Automaten unterscheiden sich von Deterministischer Endlicher Automat nur in einem wese…“

2015-02-23T09:12:30Z

Die Seite wurde neu angelegt: „Nichtdeterministische endliche Automaten unterscheiden sich von Deterministischer Endlicher Automat nur in einem wese…“

Neue Seite

Nichtdeterministische endliche Automaten unterscheiden sich von [[Deterministischen endlichen Automaten|Deterministischer Endlicher Automat]] nur in einem wesentlichen Punkt:
* '''Die Übergänge zwischen den Zuständen sind nicht eindeutig.
D.h. es kann für ein Symbol und einen Zustand mehrere mögliche Übergänge geben.

Ein Wort gilt als '''akzeptiert''', wenn es für das Wort einen Übergang vom Anfangs- in einen Endzustand gibt.

=Beispiel=
[[File:Automat007nichtDeterministisch.png|thumb|Der KGB-Automat als Nicht-deterministischer endlicher Automat. |557px]]

Der KGB-Automat erkennt Wörter, die nur aus den Ziffern 0,...,9 bestehen und die irgendwo die Zahlenkette "007" enhalten.

Man sieht, dass im Zustand <code>q0</code> der Übergang für die 0 nicht eindeutig ist; man kann entweder bei q0 bleiben oder zu q1 übergehen.

Die Darstellung als Nicht-deterministischer endlicher Automat ist oft viel einfacher als die Darstellung als [[Deterministischer Endlicher Automat]].

=Beziehung zu deterministischen endlichen Automaten=
* Jeder deterministische endliche Automat ist (ohne irgendwelches Dazutun) direkt auch ein Nicht-deterministischer endlicher Automat.
* Zu jedem Nicht-deterministischen endlichen Automaten kann man eine deterministischen endlichen Automaten konstruieren. Das Verfahren ist kompliziert, aber mathematisch bewiesen; Details dazu unter [http://de.wikipedia.org/wiki/Potenzmengenkonstruktion]

=Beziehung zu regulären Grammatiken=
* Zu jeder [[Reguläre Grammatik|regulären Grammatik]] lässt sich einfach ein nicht-deterministischer endlicher Automat konstruieren:
** Aus jedem Nichtterminalsymbol wird einen Zustand des Automaten gemacht und aus jeder Produktionsregel einen Übergang des Automaten.
* Der Nicht-deterministische endliche Automat ist deswegen ein Zwischenschritt beim Übergang von der [[Reguläre Grammatik|regulären Grammatik]] zum [[Deterministischer Endlicher Automat|deterministischen endlichen Automaten]].