Einführung in die Automatentheorie/2. Stunde - Versionsgeschichte

Matthias Scharwies: formatiert

2019-08-10T12:51:02Z

formatiert

← Nächstältere Version		Version vom 10. August 2019, 12:51 Uhr
Zeile 166:		Zeile 166:


	~~[[Kategorie:~~Einführung in die Automatentheorie]]		{{Fortsetzung\|weiter=weiter mit der 3. Stunde\|weiterlink=Einführung in die Automatentheorie/3. Stunde}}
			{{Einführung in die Automatentheorie}}

Matthias Scharwies: 11 Versionen importiert

2019-08-10T12:37:29Z

11 Versionen importiert

← Nächstältere Version

Version vom 10. August 2019, 12:37 Uhr

main>Karl Kirst: Arbeiten -> Aufgaben

2018-03-11T00:07:53Z

Arbeiten -> Aufgaben

← Nächstältere Version		Version vom 11. März 2018, 00:07 Uhr
Zeile 43:		Zeile 43:


	:{{~~Arbeiten~~\|~~NUMMER~~=2.1\|~~ARBEIT~~=		{{Aufgaben\|1=2.1\|2=

	Eine einfache Supermarktkasse funktioniert folgendermaßen:<br>		Eine einfache Supermarktkasse funktioniert folgendermaßen:<br>
Zeile 99:		Zeile 99:
	<br><br>		<br><br>

	:{{~~Arbeiten~~\|~~NUMMER~~=2.2\|~~ARBEIT~~=		{{Aufgaben\|1=2.2\|2=
	Betrachte folgenden Automaten.		Betrachte folgenden Automaten.

Zeile 117:		Zeile 117:


	:{{~~Arbeiten~~\|~~NUMMER~~=2.3\|~~ARBEIT~~=		{{Aufgaben\|1=2.3\|2=
	Betrachte den Automaten aus Aufgabe 2.2.		Betrachte den Automaten aus Aufgabe 2.2.

Zeile 144:		Zeile 144:

	==Übungsaufgaben==		==Übungsaufgaben==
	:{{~~Arbeiten~~\|~~NUMMER~~=2.4\|~~ARBEIT~~=		{{Aufgaben\|1=2.4\|2=
	<quiz>		<quiz>
	{ Fülle folgenden Lückentest aus!		{ Fülle folgenden Lückentest aus!
Zeile 154:		Zeile 154:
	}}		}}

	:{{~~Arbeiten~~\|~~NUMMER~~=2.5\|~~ARBEIT~~=		{{Aufgaben\|1=2.5\|2=
	Versuche einen Lachautomaten mit dem Eingabealphabet {h,a} zu konstruieren, der nur die Eingaben '''ha''', '''haha''', '''hahaha''' usw. akzeptiert.		Versuche einen Lachautomaten mit dem Eingabealphabet {h,a} zu konstruieren, der nur die Eingaben '''ha''', '''haha''', '''hahaha''' usw. akzeptiert.

	}}		}}

	:{{~~Arbeiten~~\|~~NUMMER~~=2.6\|~~ARBEIT~~=		{{Aufgaben\|1=2.6\|2=
	Versuche einen Automaten mit dem Eingabealphabet {a,b} zu konstruieren, der nur die Eingaben '''aaab''', '''aaabaaab''', '''aaabaaabaaab''' usw. akzeptiert.		Versuche einen Automaten mit dem Eingabealphabet {a,b} zu konstruieren, der nur die Eingaben '''aaab''', '''aaabaaab''', '''aaabaaabaaab''' usw. akzeptiert.

main>Karl Kirst: katfix

2016-03-15T20:19:49Z

katfix

← Nächstältere Version		Version vom 15. März 2016, 20:19 Uhr
Zeile 165:		Zeile 165:


	~~{{SORTIERUNG:{{SUBPAGENAME}}}}~~
	[[Kategorie:Einführung in die Automatentheorie]]		[[Kategorie:Einführung in die Automatentheorie]]

main>Karl Kirst: Einführung in die Automatentheorie

2016-03-15T20:13:52Z

Einführung in die Automatentheorie

← Nächstältere Version		Version vom 15. März 2016, 20:13 Uhr
Zeile 1:		Zeile 1:
			{{Einführung in die Automatentheorie}}
	==Zustände und Übergänge==		==Zustände und Übergänge==

main>Karl Kirst: Absätze; typo

2013-04-05T14:28:42Z

Absätze; typo

← Nächstältere Version		Version vom 5. April 2013, 14:28 Uhr
Zeile 1:		Zeile 1:
	==Zustände und Übergänge==		==Zustände und Übergänge==
	Automaten kann man sich als eine Art "Maschine" vorstellen, die stur einem festgelegtem Schema folgt, so wie zum Beispiel eine Kaffeemaschine. Eine Kaffeemaschine kann sich in verschiedenen Zuständen befinden (warten,Kaffe kochen, Kaffee warm halten). Das festgelegte Schema sagt ihr, dass sie, wenn sie angeschaltet wird, Kaffee kochen soll. Wenn sie damit fertig ist, soll sie den Kaffee warm halten, solange, bis sie ausgeschaltet wird.<br>
	~~Im Allgemeinen haben alle Automaten ein solches festes vorgegebenes Schema wie eine Kaffeemaschine.<br><br>~~

	Wie wir bereits gesehen haben, setzt sich ein Automat aus Zuständen und Übergängen zusammen. Ein festgelegtes Schema gibt vor, wann ein Automat von einem Zustand in einen anderen übergeht.~~<br><br>~~		Automaten kann man sich als eine Art "Maschine" vorstellen, die stur einem festgelegtem Schema folgt, so wie zum Beispiel eine Kaffeemaschine. Eine Kaffeemaschine kann sich in verschiedenen Zuständen befinden (warten, Kaffe kochen, Kaffee warm halten). Das festgelegte Schema sagt ihr, dass sie, wenn sie angeschaltet wird, Kaffee kochen soll. Wenn sie damit fertig ist, soll sie den Kaffee warm halten, solange, bis sie ausgeschaltet wird.

			Im Allgemeinen haben alle Automaten ein solches festes vorgegebenes Schema wie eine Kaffeemaschine.


			Wie wir bereits gesehen haben, setzt sich ein Automat aus Zuständen und Übergängen zusammen. Ein festgelegtes Schema gibt vor, wann ein Automat von einem Zustand in einen anderen übergeht.


	{{Definition\|Zu jedem Zeitpunkt befindet sich ein Automat in genau einem '''Zustand'''. '''Übergänge''' werden anhand einer '''Übergangsfunktion''' beschrieben. Eine Übergangsfunktion gibt an, mit welchem Zeichen von einem bestimmten Zustand in einen anderen gewechselt werden kann.}}		{{Definition\|Zu jedem Zeitpunkt befindet sich ein Automat in genau einem '''Zustand'''. '''Übergänge''' werden anhand einer '''Übergangsfunktion''' beschrieben. Eine Übergangsfunktion gibt an, mit welchem Zeichen von einem bestimmten Zustand in einen anderen gewechselt werden kann.}}
Zeile 9:		Zeile 13:

	Schauen wir uns hierzu nochmal den Parkscheinautomat an.		Schauen wir uns hierzu nochmal den Parkscheinautomat an.
	[[Datei:Zeichnungen_4.jpeg\|600px]]~~<br>~~
	Beschriften wir die Zustände und Übergänge ein wenig anders, sieht das ganze so aus: ~~<br>~~		[[Datei:Zeichnungen_4.jpeg\|600px]]

			Beschriften wir die Zustände und Übergänge ein wenig anders, sieht das ganze so aus:

	[[Datei:Zeichnungen_6.jpeg\|600px]]		[[Datei:Zeichnungen_6.jpeg\|600px]]
	~~<br>~~
	Dieser Automat hat folgende Zustände:~~<br>~~		Dieser Automat hat folgende Zustände:

	* z<sub>0</sub>: Der Automat wartet auf eine Eingabe. '''Wartezustnd'''		* z<sub>0</sub>: Der Automat wartet auf eine Eingabe. '''Wartezustnd'''
Zeile 21:		Zeile 28:
	* z<sub>2</sub>: Der Automat druckt das Parkticket und gibt es aus.		* z<sub>2</sub>: Der Automat druckt das Parkticket und gibt es aus.

	~~<br>~~Außerdem hat der Automat folgende Übergänge:~~<br>~~		Außerdem hat der Automat folgende Übergänge:

	* v<sub>1</sub>: Geld wird eingeworfen.<br> => Der Automat wechselt von z<sub>0</sub> nach z<sub>1</sub>.		* v<sub>1</sub>: Geld wird eingeworfen.<br> => Der Automat wechselt von z<sub>0</sub> nach z<sub>1</sub>.
Zeile 69:		Zeile 76:

	==Besondere Zustände==		==Besondere Zustände==
	Auf den Zustand mit dem Startpfeil sind wir ja schon eingegangen, dieser Zustand heißt '''Startzustand'''. ~~<br>~~		Auf den Zustand mit dem Startpfeil sind wir ja schon eingegangen, dieser Zustand heißt '''Startzustand'''.
	Jeder andere Zustand hat noch einen anderen "besonderen" Zustand, einen '''Endzustand'''. der Endzustand wird im Allgemeinen durch einen doppelten Kreis gekennzeichnet. '''Ein Automat''' kann auch '''mehrere''' Endzustände haben. Dazu aber später mehr.~~<br>~~
	In unserem Beispiel ist der Startzustand gleich dem Endzustand.~~<br>~~		Jeder andere Zustand hat noch einen anderen "besonderen" Zustand, einen '''Endzustand'''. der Endzustand wird im Allgemeinen durch einen doppelten Kreis gekennzeichnet. '''Ein Automat''' kann auch '''mehrere''' Endzustände haben. Dazu aber später mehr.

			In unserem Beispiel ist der Startzustand gleich dem Endzustand.

	[[Datei:Zeichnungen_7.jpeg\|300px]]		[[Datei:Zeichnungen_7.jpeg\|300px]]

	==Eingaben==		==Eingaben==
	Ein Automat reagiert auf Aktionen. So wechselt der Parkscheinautomat zum Beispiel beim Einwurf von einer Geldmünze den Zustand. Eine Folge von Aktionen wird '''Eingabe''' genannt. So ist z.B. [20 ct - 10ct - 10ct - 20ct - Tickettaste drücken - Ticket entnehmen] eine Eingabe.~~<br>~~		Ein Automat reagiert auf Aktionen. So wechselt der Parkscheinautomat zum Beispiel beim Einwurf von einer Geldmünze den Zustand. Eine Folge von Aktionen wird '''Eingabe''' genannt. So ist z.B. [20 ct - 10ct - 10ct - 20ct - Tickettaste drücken - Ticket entnehmen] eine Eingabe.

	Ein Automat verarbeitet eine Eingabe, indem er die einzelnen Aktionen der Reihe nach betrachtet und entsprechend reagiert.		Ein Automat verarbeitet eine Eingabe, indem er die einzelnen Aktionen der Reihe nach betrachtet und entsprechend reagiert.
	~~<br>~~'''Reagieren''' heißt hier: ~~<br>~~
			'''Reagieren''' heißt hier:

	Der Automat sucht einen Übergang, der vom aktuellen Zustand ausgeht und mit der Aktion, die an der Reihe ist, beschriftet ist.		Der Automat sucht einen Übergang, der vom aktuellen Zustand ausgeht und mit der Aktion, die an der Reihe ist, beschriftet ist.
	<br><br>		<br><br>
	Eingaben können unterschiedlich aussehen, es können sowohl Folgen von Zahlen, Wörtern, Zeichen oder Buchstaben sein. Bei realen Automaten sind dies Knöpfe, Münzen, Auswahltasten usw.		Eingaben können unterschiedlich aussehen, es können sowohl Folgen von Zahlen, Wörtern, Zeichen oder Buchstaben sein. Bei realen Automaten sind dies Knöpfe, Münzen, Auswahltasten usw.
	~~<br>~~
	Um Automaten strukturiert und übersichtlich darstellen zu können, verwendet man oft Kürzel an den Übergängen. Diese Standardisierung ermöglicht uns außerdem die Analyse der Eigenschaften von Automaten.		Um Automaten strukturiert und übersichtlich darstellen zu können, verwendet man oft Kürzel an den Übergängen. Diese Standardisierung ermöglicht uns außerdem die Analyse der Eigenschaften von Automaten.
	<br><br>		<br><br>

	:{{Arbeiten\|NUMMER=2.2\|ARBEIT=		:{{Arbeiten\|NUMMER=2.2\|ARBEIT=
	Betrachte folgenden Automaten. ~~<br>~~		Betrachte folgenden Automaten.
	[[Datei:Zeichnungen_8.jpeg\|300px]]~~<br>~~
			[[Datei:Zeichnungen_8.jpeg\|300px]]

	Fülle den Lückentext aus.		Fülle den Lückentext aus.
	<div class="lueckentext-quiz">		<div class="lueckentext-quiz">
Zeile 102:		Zeile 117:

	:{{Arbeiten\|NUMMER=2.3\|ARBEIT=		:{{Arbeiten\|NUMMER=2.3\|ARBEIT=
	Betrachte den Automaten aus Aufgabe 2.2. ~~<br>~~		Betrachte den Automaten aus Aufgabe 2.2.

	Gegeben sind verschiedene Eingaben. Setze in die entsprechenden Lücken die passenden Zustände ein (z.B. "z0-z1-z2" oder schreibe "kein Endzustand". Du must deine Antwort genau so eingeben wie hier im Beispiel, nur ohne die Anführungszeichen).		Gegeben sind verschiedene Eingaben. Setze in die entsprechenden Lücken die passenden Zustände ein (z.B. "z0-z1-z2" oder schreibe "kein Endzustand". Du must deine Antwort genau so eingeben wie hier im Beispiel, nur ohne die Anführungszeichen).

	<quiz>		<quiz>
	{ Fülle die Lücken!		{ Fülle die Lücken!
Zeile 116:		Zeile 133:


	Wie bereits erwähnt, können Eingaben sehr unterschiedlich sein. Deswegen ist es nötig, zu jedem Automaten anzugeben, aus welchen "Buchstaben" die "Sprache" besteht, die er versteht.~~<br>~~		Wie bereits erwähnt, können Eingaben sehr unterschiedlich sein. Deswegen ist es nötig, zu jedem Automaten anzugeben, aus welchen "Buchstaben" die "Sprache" besteht, die er versteht.
	Die Menge dieser "Buchstaben" wird '''Eingabealphabet''' genannt. So ist das Eingabealphabet des Automaten aus dem Beispiel oben {a,b,c}.~~<br>~~
			Die Menge dieser "Buchstaben" wird '''Eingabealphabet''' genannt. So ist das Eingabealphabet des Automaten aus dem Beispiel oben {a,b,c}.

	Das Eingabealphabet muss natürlich nicht aus wirklichen Buchstaben bestehen, es kann genauso aus den ganzen Wörtern, Sätzen oder Zahlen bestehen.<br><br>		Das Eingabealphabet muss natürlich nicht aus wirklichen Buchstaben bestehen, es kann genauso aus den ganzen Wörtern, Sätzen oder Zahlen bestehen.<br><br>

Zeile 128:		Zeile 147:
	{ Fülle folgenden Lückentest aus!		{ Fülle folgenden Lückentest aus!
	\| type="{}" }		\| type="{}" }
	Ein Automat setzt sich aus { Zuständen } und { Übergängen } zusammen. Dabei hat jeder Automat zwei besondere Zustände: Einen { Startzustand } und mindestens einen { Endzustand }. Der Startzustand wird stets mit einem { Pfeil } gekennzeichnet. Die Endzustände werden durch einen { doppelten Kreis } markiert. ~~<br>~~		Ein Automat setzt sich aus { Zuständen } und { Übergängen } zusammen. Dabei hat jeder Automat zwei besondere Zustände: Einen { Startzustand } und mindestens einen { Endzustand }. Der Startzustand wird stets mit einem { Pfeil } gekennzeichnet. Die Endzustände werden durch einen { doppelten Kreis } markiert.

	Ein festgelegtes Schema gibt vor, wann ein Automat von einem { Zustand } in einen anderen { Zustand } übergeht. Allgemein sagt man, dass der Automat eine { Eingabe } aus dem { Eingabealphabet } verarbeitet. </quiz>		Ein festgelegtes Schema gibt vor, wann ein Automat von einem { Zustand } in einen anderen { Zustand } übergeht. Allgemein sagt man, dass der Automat eine { Eingabe } aus dem { Eingabealphabet } verarbeitet. </quiz>

main>Fieldman: /* Besondere Zustände */

2013-04-05T00:20:32Z

Besondere Zustände

← Nächstältere Version		Version vom 5. April 2013, 00:20 Uhr
Zeile 69:		Zeile 69:

	==Besondere Zustände==		==Besondere Zustände==
	Auf den ~~Zsutand~~ mit dem Startpfeil sind wir ja schon eingegangen, dieser Zustand heißt '''Startzustand'''. <br>		Auf den Zustand mit dem Startpfeil sind wir ja schon eingegangen, dieser Zustand heißt '''Startzustand'''. <br>
	Jeder andere Zustand hat noch einen anderen "besonderen" Zustand, einen '''Endzustand'''. der Endzustand wird im Allgemeinen durch einen doppelten Kreis gekennzeichnet. '''Ein Automat''' kann auch '''mehrere''' Endzustände haben. Dazu aber später mehr.<br>		Jeder andere Zustand hat noch einen anderen "besonderen" Zustand, einen '''Endzustand'''. der Endzustand wird im Allgemeinen durch einen doppelten Kreis gekennzeichnet. '''Ein Automat''' kann auch '''mehrere''' Endzustände haben. Dazu aber später mehr.<br>
	In unserem Beispiel ist der Startzustand gleich dem Endzustand.<br>		In unserem Beispiel ist der Startzustand gleich dem Endzustand.<br>

main>Karl Kirst: kat

2013-03-18T12:46:35Z

kat

← Nächstältere Version		Version vom 18. März 2013, 12:46 Uhr
Zeile 142:		Zeile 142:

	}}		}}


			{{SORTIERUNG:{{SUBPAGENAME}}}}
			[[Kategorie:Einführung in die Automatentheorie]]

main>Fieldman am 15. März 2013 um 11:21 Uhr

2013-03-15T11:21:20Z

main>Fieldman: /* Eingaben */

2013-03-13T08:41:54Z

Eingaben

← Nächstältere Version		Version vom 13. März 2013, 08:41 Uhr
Zeile 122:		Zeile 122:
	{{Definition\|Das '''Eingabealphabet''' eines Automaten, ist die Menge an Zeichen, Wörtern oder Symbolen, auf die der Automat reagieren kann.}}		{{Definition\|Das '''Eingabealphabet''' eines Automaten, ist die Menge an Zeichen, Wörtern oder Symbolen, auf die der Automat reagieren kann.}}
	<br><br>		<br><br>

			==Übungsaufgaben==
			:{{Arbeiten\|NUMMER=2.4\|ARBEIT=
			<quiz>
			{ Fülle folgenden Lückentest aus!
			\| type="{}" }
			Ein Automat setzt sich aus { Zuständen } und { Übergängen } zusammen. Dabei hat jeder Automat zwei besondere Zustände: Einen { Startzustand } und mindestens einen { Endzustand }. Der Startzustand wird stets mit einem { Pfeil } gekennzeichnet. Die Endzustände werden durch einen { doppelten Kreis } markiert. <br>
			Ein festgelegtes Schema gibt vor, wann ein Automat von einem { Zustand } in einen anderen { Zustand } übergeht. Allgemein sagt man, dass der Automat eine { Eingabe } aus dem { Eingabealphabet } verarbeitet. </quiz>

			}}

			:{{Arbeiten\|NUMMER=2.5\|ARBEIT=
			Versuche einen Lachautomaten mit dem Eingabealphabet {h,a} zu konstruieren, der nur die Eingaben ha, haha, hahaha usw. akzeptiert.

			}}

			:{{Arbeiten\|NUMMER=2.6\|ARBEIT=
			Versuche einen Automaten mit dem Eingabealphabet {a,b} zu konstruieren, der nur die Eingaben aaab, aaabaaab, aaabaaabaaab usw. akzeptiert.

			}}

← Nächstältere Version		Version vom 15. März 2013, 11:21 Uhr
Zeile 37:		Zeile 37:
	:{{Arbeiten\|NUMMER=2.1\|ARBEIT=		:{{Arbeiten\|NUMMER=2.1\|ARBEIT=

	Eine einfache ~~Supermarktkette~~ funktioniert folgendermaßen:<br>		Eine einfache Supermarktkasse funktioniert folgendermaßen:<br>

	* Wird ein Preis eingegeben, addiert die Kasse diesem zum ~~Gesmatpreis~~.		* Wird ein Preis eingegeben, addiert die Kasse diesem zum Gesamtpreis.

	* Drückt jemand auf die Taste "Kassieren", wird der Gesamtpreis angezeigt und die Geldlade geöffnet.		* Drückt jemand auf die Taste "Kassieren", wird der Gesamtpreis angezeigt und die Geldlade geöffnet.
Zeile 103:		Zeile 103:
	:{{Arbeiten\|NUMMER=2.3\|ARBEIT=		:{{Arbeiten\|NUMMER=2.3\|ARBEIT=
	Betrachte den Automaten aus Aufgabe 2.2. <br>		Betrachte den Automaten aus Aufgabe 2.2. <br>
	Gegeben sind verschiedene Eingaben. Setze in die entsprechenden Lücken die passenden Zustände ein (z.B. "z0-z1 -z2" oder schreibe "kein Endzustand". Du must deine Antwort genau so eingeben wie hier im Beispiel, nur ohne die Anführungszeichen).		Gegeben sind verschiedene Eingaben. Setze in die entsprechenden Lücken die passenden Zustände ein (z.B. "z0-z1-z2" oder schreibe "kein Endzustand". Du must deine Antwort genau so eingeben wie hier im Beispiel, nur ohne die Anführungszeichen).
	<quiz>		<quiz>
	{ Fülle die Lücken!		{ Fülle die Lücken!
Zeile 118:		Zeile 118:
	Wie bereits erwähnt, können Eingaben sehr unterschiedlich sein. Deswegen ist es nötig, zu jedem Automaten anzugeben, aus welchen "Buchstaben" die "Sprache" besteht, die er versteht.<br>		Wie bereits erwähnt, können Eingaben sehr unterschiedlich sein. Deswegen ist es nötig, zu jedem Automaten anzugeben, aus welchen "Buchstaben" die "Sprache" besteht, die er versteht.<br>
	Die Menge dieser "Buchstaben" wird '''Eingabealphabet''' genannt. So ist das Eingabealphabet des Automaten aus dem Beispiel oben {a,b,c}.<br>		Die Menge dieser "Buchstaben" wird '''Eingabealphabet''' genannt. So ist das Eingabealphabet des Automaten aus dem Beispiel oben {a,b,c}.<br>
	Das Eingabealphabet muss natürlich nicht aus wirklichen Buchstaben bestehen, es ~~kan~~ genauso aus den ganzen Wörtern, Sätzen oder Zahlen bestehen.<br><br>		Das Eingabealphabet muss natürlich nicht aus wirklichen Buchstaben bestehen, es kann genauso aus den ganzen Wörtern, Sätzen oder Zahlen bestehen.<br><br>

	{{Definition\|Das '''Eingabealphabet''' eines Automaten, ist die Menge an Zeichen, Wörtern oder Symbolen, auf die der Automat reagieren kann.}}		{{Definition\|Das '''Eingabealphabet''' eines Automaten, ist die Menge an Zeichen, Wörtern oder Symbolen, auf die der Automat reagieren kann.}}
Zeile 134:		Zeile 134:

	:{{Arbeiten\|NUMMER=2.5\|ARBEIT=		:{{Arbeiten\|NUMMER=2.5\|ARBEIT=
	Versuche einen Lachautomaten mit dem Eingabealphabet {h,a} zu konstruieren, der nur die Eingaben ha, haha, hahaha usw. akzeptiert.		Versuche einen Lachautomaten mit dem Eingabealphabet {h,a} zu konstruieren, der nur die Eingaben '''ha''', '''haha''', '''hahaha''' usw. akzeptiert.

	}}		}}

	:{{Arbeiten\|NUMMER=2.6\|ARBEIT=		:{{Arbeiten\|NUMMER=2.6\|ARBEIT=
	Versuche einen Automaten mit dem Eingabealphabet {a,b} zu konstruieren, der nur die Eingaben aaab, aaabaaab, aaabaaabaaab usw. akzeptiert.		Versuche einen Automaten mit dem Eingabealphabet {a,b} zu konstruieren, der nur die Eingaben '''aaab''', '''aaabaaab''', '''aaabaaabaaab''' usw. akzeptiert.

	}}		}}