Deterministischer Endlicher Automat - Versionsgeschichte

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

2023-08-30T13:43:32Z

Beziehung zu regulären Sprachen und regulären Grammatiken

← Nächstältere Version		Version vom 30. August 2023, 13:43 Uhr
Zeile 83:		Zeile 83:
	* '''Zu jedem deterministischen endlichen Automaten gibt es eine [[reguläre Grammatik]].'''		* '''Zu jedem deterministischen endlichen Automaten gibt es eine [[reguläre Grammatik]].'''
	** Diese lässt sich leicht aus dem Übergangsgraphen konstruieren, indem man aus jedem Zustand ein Nichtterminalsymbol macht und aus jedem Übergang eine Regel (mit einem Terminalsymbol und einem Nichtterminalsymbol).		** Diese lässt sich leicht aus dem Übergangsgraphen konstruieren, indem man aus jedem Zustand ein Nichtterminalsymbol macht und aus jedem Übergang eine Regel (mit einem Terminalsymbol und einem Nichtterminalsymbol).
			** Erklärvideo dazu: [https://youtu.be/BcMXVx6VeSk Deterministischen endlichen Automaten in reguläre Grammatik umwandeln]
	* '''Zu jeder [[reguläre Grammatik\|regulären Grammatik]] gibt es einen deterministischen endlichen Automaten.'''<br>		* '''Zu jeder [[reguläre Grammatik\|regulären Grammatik]] gibt es einen deterministischen endlichen Automaten.'''<br>
	** Dazu erstellt man aus der regulären Grammatik erst einen [[Nicht-deterministischer endlicher Automaten\|Nicht-deterministischen endlichen Automaten]], indem man aus jedem Nichtterminalsymbol einen Zustand macht und aus jeder Produktionsregel einen Übergang.		** Dazu erstellt man aus der regulären Grammatik erst einen [[Nicht-deterministischer endlicher Automaten\|Nicht-deterministischen endlichen Automaten]], indem man aus jedem Nichtterminalsymbol einen Zustand macht und aus jeder Produktionsregel einen Übergang.

Akaibel: /* Fachbegriffe */

2023-08-30T13:42:27Z

Fachbegriffe

← Nächstältere Version		Version vom 30. August 2023, 13:42 Uhr
Zeile 17:		Zeile 17:

	Deterministischer endlicher Automat (DEA), Zustand, Anfangszustand, Endzustände, Alphabet, Übergang, Zustandsübergangsfunktion, Übergangsgraph, prüfen		Deterministischer endlicher Automat (DEA), Zustand, Anfangszustand, Endzustände, Alphabet, Übergang, Zustandsübergangsfunktion, Übergangsgraph, prüfen

			=Erklärvideos=
			* [https://youtu.be/BcMXVx6VeSk Deterministischen endlichen Automaten in reguläre Grammatik umwandeln]

	=Beispiel=		=Beispiel=

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

2022-02-14T19:09:59Z

Beziehung zu regulären Sprachen und regulären Grammatiken

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

	=Beziehung zu regulären Sprachen und regulären Grammatiken=		=Beziehung zu regulären Sprachen und regulären Grammatiken=
			[[Datei:DEA-RG-NEA-reg-Sprache.png\|400px\|thumb\|right\|Beziehungen: Reguläre Grammatik - DEA - NEA - reguläre Sprache]]
	* Sprachen, die von deterministischen endlichen Automaten akzeptiert werden, heißen '''reguläre Sprache'''.		* Sprachen, die von deterministischen endlichen Automaten akzeptiert werden, heißen '''reguläre Sprache'''.
	* '''Zu jedem deterministischen endlichen Automaten gibt es eine [[reguläre Grammatik]].'''		* '''Zu jedem deterministischen endlichen Automaten gibt es eine [[reguläre Grammatik]].'''

Akaibel: /* Überprüfung von Wörtern */

2022-01-23T17:57:33Z

Überprüfung von Wörtern

← Nächstältere Version		Version vom 23. Januar 2022, 17:57 Uhr
Zeile 54:		Zeile 54:
	'''Beispiele:'''		'''Beispiele:'''
	* Überprüfung von "060074":		* Überprüfung von "060074":
	<code>		<code> 0 6 0 0 7 4
	0 6 0 0 7 4
	q<sub>0</sub> → q<sub>1</sub> → q<sub>0</sub> → q<sub>1</sub> → q<sub>2</sub> → q<sub>3</sub> → q<sub>3</sub>		q<sub>0</sub> → q<sub>1</sub> → q<sub>0</sub> → q<sub>1</sub> → q<sub>2</sub> → q<sub>3</sub> → q<sub>3</sub>
	Endzustand erreicht, d.h. akzeptiert.		Endzustand erreicht, d.h. akzeptiert.</code>
	</code>
	* Überprüfung von "060064":		* Überprüfung von "060064":
	<code>		<code> 0 6 0 0 6 4
	0 6 0 0 6 4
	q<sub>0</sub> → q<sub>1</sub> → q<sub>0</sub> → q<sub>1</sub> → q<sub>2</sub> → q<sub>0</sub> → q<sub>0</sub> :		q<sub>0</sub> → q<sub>1</sub> → q<sub>0</sub> → q<sub>1</sub> → q<sub>2</sub> → q<sub>0</sub> → q<sub>0</sub> :
	Endzustand <u>nicht</u> erreicht, d.h. <u>nicht</u> akzeptiert.		Endzustand <u>nicht</u> erreicht, d.h. <u>nicht</u> akzeptiert.
	</code>		</code>

	''In diesem Beispiel kann nicht demonstriert werden, wie man in eine Senke fahren kann, weil es es in jedem Zustand für jedes Symbol einen Übergang gibt.''		''In diesem Beispiel kann nicht demonstriert werden, wie man in eine Senke fahren kann, weil es es in jedem Zustand für jedes Symbol einen Übergang gibt.''

Akaibel am 23. Juni 2019 um 13:26 Uhr

2019-06-23T13:26:42Z

← Nächstältere Version		Version vom 23. Juni 2019, 13:26 Uhr
Zeile 14:		Zeile 14:

	Deterministische endliche Automaten können als Java-Programm realisiert werden. Ein solches Programm nennt man '''[[Parser]]'''.		Deterministische endliche Automaten können als Java-Programm realisiert werden. Ein solches Programm nennt man '''[[Parser]]'''.
			=Fachbegriffe=

			Deterministischer endlicher Automat (DEA), Zustand, Anfangszustand, Endzustände, Alphabet, Übergang, Zustandsübergangsfunktion, Übergangsgraph, prüfen

	=Beispiel=		=Beispiel=

Akaibel: /* Beispiel */

2017-11-13T15:34:05Z

Beispiel

← Nächstältere Version		Version vom 13. November 2017, 15:34 Uhr
Zeile 98:		Zeile 98:

	'''Begründung:''' Der Automat muss sich "merken" können, wie viele a vorgekommen sind. Dafür bräuchte er eine unbegrenzte Menge von Zuständen, denn es ist nicht festgelegt, wie viele Buchstaben "a" kommen, bevor man zu "b" übergeht.		'''Begründung:''' Der Automat muss sich "merken" können, wie viele a vorgekommen sind. Dafür bräuchte er eine unbegrenzte Menge von Zuständen, denn es ist nicht festgelegt, wie viele Buchstaben "a" kommen, bevor man zu "b" übergeht.

			'''Hinweis:'''<br>
			Für die Sprache <code>a<sup>n</sup>b<sup>n</sup></code> kann man einen '''[[Kellerautomat]]''' entwickeln.

	==Weitere Beispiele==		==Weitere Beispiele==

Akaibel: /* Überprüfung von Wörtern */

2015-09-13T12:43:05Z

Überprüfung von Wörtern

← Nächstältere Version		Version vom 13. September 2015, 12:43 Uhr
Zeile 56:		Zeile 56:
	Endzustand erreicht, d.h. akzeptiert.		Endzustand erreicht, d.h. akzeptiert.
	</code>		</code>
	* Überprüfung von "060064": q<sub>0</sub> → q<sub>1</sub> →q<sub>0</sub> →q<sub>1</sub> →q<sub>2</sub> →q<sub>0</sub> →q<sub>0</sub> : Endzustand <u>nicht</u> erreicht, d.h. <u>nicht</u> akzeptiert.		* Überprüfung von "060064":
			<code>
			0 6 0 0 6 4
			q<sub>0</sub> → q<sub>1</sub> → q<sub>0</sub> → q<sub>1</sub> → q<sub>2</sub> → q<sub>0</sub> → q<sub>0</sub> :
			Endzustand <u>nicht</u> erreicht, d.h. <u>nicht</u> akzeptiert.
			</code>

	''In diesem Beispiel kann nicht demonstriert werden, wie man in eine Senke fahren kann, weil es es in jedem Zustand für jedes Symbol einen Übergang gibt.''		''In diesem Beispiel kann nicht demonstriert werden, wie man in eine Senke fahren kann, weil es es in jedem Zustand für jedes Symbol einen Übergang gibt.''

Akaibel: /* Überprüfung von Wörtern */

2015-09-13T12:40:53Z

Überprüfung von Wörtern

← Nächstältere Version		Version vom 13. September 2015, 12:40 Uhr
Zeile 50:		Zeile 50:

	'''Beispiele:'''		'''Beispiele:'''
	* Überprüfung von "060074": q<sub>0</sub> → q<sub>1</sub> →q<sub>0</sub> →q<sub>1</sub> →q<sub>2</sub> →q<sub>3</sub> →q<sub>3</sub> : Endzustand erreicht, d.h. akzeptiert.		* Überprüfung von "060074":
			<code>
			0 6 0 0 7 4
			q<sub>0</sub> → q<sub>1</sub> → q<sub>0</sub> → q<sub>1</sub> → q<sub>2</sub> → q<sub>3</sub> → q<sub>3</sub>
			Endzustand erreicht, d.h. akzeptiert.
			</code>
	* Überprüfung von "060064": q<sub>0</sub> → q<sub>1</sub> →q<sub>0</sub> →q<sub>1</sub> →q<sub>2</sub> →q<sub>0</sub> →q<sub>0</sub> : Endzustand <u>nicht</u> erreicht, d.h. <u>nicht</u> akzeptiert.		* Überprüfung von "060064": q<sub>0</sub> → q<sub>1</sub> →q<sub>0</sub> →q<sub>1</sub> →q<sub>2</sub> →q<sub>0</sub> →q<sub>0</sub> : Endzustand <u>nicht</u> erreicht, d.h. <u>nicht</u> akzeptiert.

Akaibel: /* Beispiel */

2015-02-28T09:01:12Z

Beispiel

← Nächstältere Version		Version vom 28. Februar 2015, 09:01 Uhr
Zeile 32:		Zeile 32:
	{\| class="wikitable"		{\| class="wikitable"
	\|-		\|-
	!\| \|\| <b~~>q<sub~~>0~~</sub>~~</b> \|\| <b>~~q<sub>1</sub>~~</b> \|\| <b>~~q<sub>2</sub></b> \|\| <b>q<sub>3</sub>~~</b>		!\| \|\| <b>0</b> \|\| <b>7</b> \|\| <b>1..6, 8, 9</b>
	\|-		\|-
	\|\|<b>q<sub>0</sub></b> \|\| 1~~..9~~ \|\| 0 \|\| \|\|		\|\|<b>q<sub>0</sub></b> \|\| q<sub>1</sub> \|\| q<sub>0</sub> \|\| q<sub>0</sub>
	\|-		\|-
	\|\|<b>q<sub>1</sub></b> \|\| ~~1..9~~ \|\| \|\| 0 \|\|		\|\|<b>q<sub>1</sub></b> \|\| q<sub>2</sub> \|\| q<sub>0</sub> \|\| q<sub>0</sub>
	\|-		\|-
	\|\|<b>q<sub>2</sub></b> \|\| ~~1..6,8,9~~ \|\| \|\| 0 ~~\|\| 7~~		\|\|<b>q<sub>2</sub></b> \|\| q<sub>2</sub> \|\| q<sub>3</sub> \|\| q<sub>0</sub>
	\|-		\|-
	\|\|<b>q<sub>3</sub></b> \|\| \|\| \|\| ~~\|\| 0..9~~		\|\|<b>q<sub>3</sub></b> \|\| q<sub>3</sub> \|\| q<sub>3</sub> \|\| q<sub>3</sub>
	\|}		\|}

Akaibel: /* Überprüfung von Wörtern */

2015-02-23T09:17:24Z

Überprüfung von Wörtern

← Nächstältere Version		Version vom 23. Februar 2015, 09:17 Uhr
Zeile 53:		Zeile 53:
	* Überprüfung von "060064": q<sub>0</sub> → q<sub>1</sub> →q<sub>0</sub> →q<sub>1</sub> →q<sub>2</sub> →q<sub>0</sub> →q<sub>0</sub> : Endzustand <u>nicht</u> erreicht, d.h. <u>nicht</u> akzeptiert.		* Überprüfung von "060064": q<sub>0</sub> → q<sub>1</sub> →q<sub>0</sub> →q<sub>1</sub> →q<sub>2</sub> →q<sub>0</sub> →q<sub>0</sub> : Endzustand <u>nicht</u> erreicht, d.h. <u>nicht</u> akzeptiert.

			''In diesem Beispiel kann nicht demonstriert werden, wie man in eine Senke fahren kann, weil es es in jedem Zustand für jedes Symbol einen Übergang gibt.''
	In diesem Beispiel ~~gibt es in jedem Zustand für jedes Symbol einen Übergang; deswegen~~ kann ~~hier~~ nicht demonstriert werden, wie man in eine Senke fahren kann.

	=Definition=		=Definition=