Kellerautomat - Versionsgeschichte

Akaibel: /* Beispiel in Standard-Schreibweise */

2021-02-19T10:33:47Z

Beispiel in Standard-Schreibweise

← Nächstältere Version		Version vom 19. Februar 2021, 10:33 Uhr
Zeile 45:		Zeile 45:
	'''Erläuterung:'''		'''Erläuterung:'''

	* '''In der Klammer''' steht zuerst das Kellerzeichen und dann der Buchstabe des Wortes, der gerade bearbeitet wird.		* '''In der Klammer''' steht zuerst das aktuelle Kellerzeichen (d.h. das oberste Zeichen auf dem Keller-Stapel) und dann der Buchstabe des Wortes, der gerade bearbeitet wird.
	* '''Nach dem Doppelpunkt''' steht der Zustand des Kellers nach Abarbeitung. <br/>Dabei bedeutet...		* '''Nach dem Doppelpunkt''' steht der Zustand des Kellers nach Abarbeitung. <br/>Dabei bedeutet...
	** '''<code>€</code>''' : das oberste Zeichen im Keller wurde gelöscht (d.h. <code>pop</code>)		** '''<code>€</code>''' : das oberste Zeichen im Keller wurde gelöscht (d.h. <code>pop</code>)

Akaibel: /* Zusammenhang zur kontextfreien Grammatik */

2020-10-23T17:04:55Z

Zusammenhang zur kontextfreien Grammatik

← Nächstältere Version		Version vom 23. Oktober 2020, 17:04 Uhr
Zeile 62:		Zeile 62:
	* '''# ist das Anfangssymbol im Keller'''		* '''# ist das Anfangssymbol im Keller'''
	* F ist die Menge der akzeptierenden Endzustände.		* F ist die Menge der akzeptierenden Endzustände.

			=Deterministischer und Nicht-Deterministischer Kellerautomat=

			Der nicht-deterministische Kellerautomat ist '''mächtiger''' als der deterministische Kellerautomat!<br/>D.h. es gibt Sprachen, die von einem Nicht-Deterministischen Kellerautomaten geprüft werden können, nicht aber von einem Deterministischen Kellerautomaten.
			==Beispiel==
			Die von der kontextfreien Grammatik erzeugte Sprache

			L = { 0S0 \| 1S1 \| ε }

			kann zwar von einem nicht-deterministischen Kellerautomaten erkannt werden,<br/>aber nicht von einem deterministischen Kellerautomaten.

			''Warum das so ist?! Das geht über das Geschehen auch im Informatik-LK hinaus.<br/>Damit kann/muss man sich im Informatik-Studium (Vorlesung: Theoretische Informatik) auseinandersetzen...''

	=Zusammenhang zur kontextfreien Grammatik=		=Zusammenhang zur kontextfreien Grammatik=
	* ~~Der deterministische~~ Kellerautomat ~~erkennt genau die deterministisch-kontextfreien Sprachen~~.
	* ~~Der nichtdeterministische Kellerautomat erkennt genau die kontextfreien Sprachen, d.h. Sprachen, die~~ von ~~einer~~ [[Kontextfreie Grammatik\|~~kontextfreien~~ Grammatik]] ~~erzeugt werden~~.		* Jede von einer [[Kontextfreie Grammatik\|kontextfreien Grammatik]] erzeugte Sprache lässt sich durch einen <u>nicht-deterministischen</u> Kellerautomat überprüfen.
			* Zu jeder von einem <u>nicht-deterministischen</u> Kellerautomaten erkannten Sprache gibt es eine [[Kontextfreie Grammatik\|kontextfreie Grammatik]].
			''Die Frage nach dem "Warum?" geht auch über den Informatik-LK hinaus und bleibt hier unbeantwortet. <br/>Irgendetwas muss ja auch für das Studium noch übrig bleiben...''

	=Parser für einen Kellerautomaten=		=Parser für einen Kellerautomaten=

Akaibel: /* Parser für einen Kellerautomaten */

2020-03-31T13:22:02Z

Parser für einen Kellerautomaten

← Nächstältere Version		Version vom 31. März 2020, 13:22 Uhr
Zeile 81:		Zeile 81:
	char zeichen = pWort.charAt(i);		char zeichen = pWort.charAt(i);
	char kellerzeichen = keller.top();		char kellerzeichen = keller.top();
	~~switch~~(zustand){		'''if'''(zustand == 0){
	~~case 0:~~
	if(zeichen=='a' && kellerzeichen == '#'){		if(zeichen=='a' && kellerzeichen == '#'){
	zustand = 0;		zustand = 0;
Zeile 100:		Zeile 99:
	continue;		continue;
	// end case 0		// end case 0
	~~case~~ 1:		'''else if'''(zustand == 1){
	if(zeichen=='b' && kellerzeichen == 'A'){		if(zeichen=='b' && kellerzeichen == 'A'){
	zustand = 1;		zustand = 1;
Zeile 113:		Zeile 112:
	continue;		continue;
	// end case 1		// end case 1
	} // ~~end switch~~(~~zustand~~)		}
			'''else'''{
			// andere Zustaende, d.h. Zustand 2
			System.err.println("Im Zustand 2 darf es kein Zeichen mehr geben!!");
			return false;
			}
	} // end for		} // end for

Akaibel: /* Beispiel in Standard-Schreibweise */

2020-03-31T13:13:23Z

Beispiel in Standard-Schreibweise

← Nächstältere Version		Version vom 31. März 2020, 13:13 Uhr
Zeile 43:		Zeile 43:
	Der Zustandsübergangsgraph rechts zeigt die Standard-Schreibweise für einen Kellerautomaten, der die Sprache Sprache L = {a<sup>n</sup>b<sup>n</sup>} überprüft.		Der Zustandsübergangsgraph rechts zeigt die Standard-Schreibweise für einen Kellerautomaten, der die Sprache Sprache L = {a<sup>n</sup>b<sup>n</sup>} überprüft.

	Erläuterung:		'''Erläuterung:'''

	* '''In der Klammer''' steht zuerst das Kellerzeichen und dann der Buchstabe des Wortes, der gerade bearbeitet wird.		* '''In der Klammer''' steht zuerst das Kellerzeichen und dann der Buchstabe des Wortes, der gerade bearbeitet wird.
	* '''Nach dem Doppelpunkt''' steht der Zustand des Kellers nach Abarbeitung. <br/>Dabei bedeutet...		* '''Nach dem Doppelpunkt''' steht der Zustand des Kellers nach Abarbeitung. <br/>Dabei bedeutet...

	** '''<code>€</code>''' : das oberste Zeichen im Keller wurde gelöscht (d.h. <code>pop</code>)		** '''<code>€</code>''' : das oberste Zeichen im Keller wurde gelöscht (d.h. <code>pop</code>)

	** '''ein Buchstabe''' : der Keller hat sich nicht verändert (d.h. <code>nop</code>).		** '''ein Buchstabe''' : der Keller hat sich nicht verändert (d.h. <code>nop</code>).

	** '''zwei Buchstaben''' : es wurde ein Kellerzeichen oben in den Keller reingeschichtet.<br/>Der '''erste''' der beiden Buchstaben ist das '''neue''' Kellerzeichen, <br/>der '''zweite''' Buchstabe ist das bisherige oberste Kellerzeichen.		** '''zwei Buchstaben''' : es wurde ein Kellerzeichen oben in den Keller reingeschichtet.<br/>Der '''erste''' der beiden Buchstaben ist das '''neue''' Kellerzeichen, <br/>der '''zweite''' Buchstabe ist das bisherige oberste Kellerzeichen.

Akaibel: /* Beispiel */

2020-03-31T13:12:27Z

Beispiel

@@ Zeile 20: / Zeile 20: @@
 =Beispiel=
 [[File:Kellerautomat.png|thumb|Kellerautomat für die Sprache L = {a<sup>n</sup>b<sup>n</sup>}. |385px]]
@@ Zeile 31: / Zeile 34: @@
 * Startzustand: q<sub>0</sub>
 * F = {q<sub>2</sub>} ist die Menge der Endzustände
 =Formale Definition des Kellerautomaten=

Akaibel am 29. März 2020 um 14:37 Uhr

2020-03-29T14:37:07Z

← Nächstältere Version		Version vom 29. März 2020, 14:37 Uhr
Zeile 3:		Zeile 3:
	[[Kategorie:Informatik-Abitur]]		[[Kategorie:Informatik-Abitur]]
	[[Kategorie:Informatik]]		[[Kategorie:Informatik]]

	<font color='red'>'''nur relevant für den Leistungskurs!'''</font>		<font color='red'>'''nur relevant für den Leistungskurs!'''</font>

Akaibel am 29. März 2020 um 14:35 Uhr

2020-03-29T14:35:47Z

← Nächstältere Version		Version vom 29. März 2020, 14:35 Uhr
Zeile 3:		Zeile 3:
	[[Kategorie:Informatik-Abitur]]		[[Kategorie:Informatik-Abitur]]
	[[Kategorie:Informatik]]		[[Kategorie:Informatik]]

			<font color='red'>'''nur relevant für den Leistungskurs!'''</font>

	Ein Kellerautomat ist ein [[Deterministischer Endlicher Automat]] (DEA), der um einen Speicher (genannt '''Keller''') in Form eines [[Stack]] erweitert wurde.		Ein Kellerautomat ist ein [[Deterministischer Endlicher Automat]] (DEA), der um einen Speicher (genannt '''Keller''') in Form eines [[Stack]] erweitert wurde.

	In dem Keller kann der Kellerautomat Zeichen, die im sogenannten '''Kelleralphabet''' definiert sind, speichern und sie später nach dem Last-In-First-Out-Prinzip wieder abrufen.		In dem Keller kann der Kellerautomat Zeichen, die im sogenannten '''Kelleralphabet''' definiert sind, speichern und sie später nach dem Last-In-First-Out-Prinzip wieder abrufen.

Akaibel: /* Zweck des Kellerautomaten */

2019-06-23T13:39:12Z

Zweck des Kellerautomaten

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

	In dem Keller kann der Kellerautomat Zeichen, die im sogenannten '''Kelleralphabet''' definiert sind, speichern und sie später nach dem Last-In-First-Out-Prinzip wieder abrufen.		In dem Keller kann der Kellerautomat Zeichen, die im sogenannten '''Kelleralphabet''' definiert sind, speichern und sie später nach dem Last-In-First-Out-Prinzip wieder abrufen.

			=Fachbegriffe=

			Alphabet, Zeichen, Kelleralphabet, Kellerzeichen, Zustand, Anfangszustand, Endzustände, Übergang

	=Zweck des Kellerautomaten=		=Zweck des Kellerautomaten=

	Deterministische Endliche Automaten können nur sehr begrenzte Sprachen überprüfen, vor allem deswegen, weil sie nicht "zählen" können.		Deterministische Endliche Automaten können nur sehr begrenzte Sprachen überprüfen, vor allem deswegen, weil sie nicht "zählen" können.
	Deswegen ist z.B. die Sprache L = {a<sup>n</sup>b<sup>n</sup>} mit einem DEA nicht darstellbar.		Deswegen ist z.B. die Sprache L = {a<sup>n</sup>b<sup>n</sup>} mit einem DEA nicht darstellbar.

Akaibel: /* Zusammenhang zu formalen Sprachen */

2018-11-12T16:37:00Z

Zusammenhang zu formalen Sprachen

← Nächstältere Version		Version vom 12. November 2018, 16:37 Uhr
Zeile 39:		Zeile 39:
	* F ist die Menge der akzeptierenden Endzustände.		* F ist die Menge der akzeptierenden Endzustände.

	=Zusammenhang ~~zu formalen Sprachen~~=		=Zusammenhang zur kontextfreien Grammatik=
	* Der deterministische Kellerautomat erkennt genau die deterministisch-kontextfreien Sprachen.		* Der deterministische Kellerautomat erkennt genau die deterministisch-kontextfreien Sprachen.
	* Der nichtdeterministische Kellerautomat erkennt genau die kontextfreien Sprachen, d.h. Sprachen, die von einer [[Kontextfreie Grammatik\|kontextfreien Grammatik]] erzeugt werden.		* Der nichtdeterministische Kellerautomat erkennt genau die kontextfreien Sprachen, d.h. Sprachen, die von einer [[Kontextfreie Grammatik\|kontextfreien Grammatik]] erzeugt werden.

Akaibel: /* Parser für einen Kellerautomaten */

2018-11-12T16:17:08Z

Parser für einen Kellerautomaten

← Nächstältere Version		Version vom 12. November 2018, 16:17 Uhr
Zeile 54:		Zeile 54:
	keller.push('#');		keller.push('#');
	int zustand = 0;		int zustand = 0;
	for(char zeichen:pWort.~~toCharArray~~()){		for(int i=0; i<pWort.length(); i++){
			char zeichen = pWort.charAt(i);
	char kellerzeichen = keller.top();		char kellerzeichen = keller.top();
	switch(zustand){		switch(zustand){