Kontextfreie Grammatik - Versionsgeschichte

Akaibel: /* Zusammenhang zum Kellerautomat */

2023-11-05T10:39:02Z

Zusammenhang zum Kellerautomat

← Nächstältere Version		Version vom 5. November 2023, 10:39 Uhr
Zeile 42:		Zeile 42:
	* Zu jeder von einem <u>nicht-deterministischen</u> [[Kellerautomat]] erkannten Sprache gibt es eine kontextfreie Grammatik.		* Zu jeder von einem <u>nicht-deterministischen</u> [[Kellerautomat]] erkannten Sprache gibt es eine 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...		''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...
			** Wer sich den (langatmigen!!) Beweis mal anschauen will: <br/>[https://ai.dmi.unibas.ch/_files/teaching/fs14/theo/slides/theo10.pdf Theorie der Informatik, Kontextfreie Sprachen II, Universität Basel 2014]<br/>S. 17 ff.

	'''Zu beachten ist:'''		'''Zu beachten ist:'''

	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.		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.


	Vgl. [[Kellerautomat]]		Vgl. [[Kellerautomat]]

Akaibel: /* Zusammenhang zum Kellerautomat */

2020-10-23T16:57:18Z

Zusammenhang zum Kellerautomat

← Nächstältere Version		Version vom 23. Oktober 2020, 16:57 Uhr
Zeile 38:		Zeile 38:

	=Zusammenhang zum Kellerautomat=		=Zusammenhang zum Kellerautomat=
	Jede ~~kontextfreie~~ Sprache lässt sich durch einen nicht-deterministischen [[Kellerautomat]] überprüfen.
			* Jede von einer kontextfreien Grammatik erzeugte Sprache lässt sich durch einen <u>nicht-deterministischen</u> [[Kellerautomat]] überprüfen.
			* Zu jeder von einem <u>nicht-deterministischen</u> [[Kellerautomat]] erkannten Sprache gibt es eine 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...

			'''Zu beachten ist:'''

			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.

			Vgl. [[Kellerautomat]]

	=Grenzen der kontextfreien Sprache=		=Grenzen der kontextfreien Sprache=
	Die Sprache L = {a<sup>n</sup>b<sup>n</sup>c<sup>n</sup>} ist nicht kontextfrei.		Die Sprache L = {a<sup>n</sup>b<sup>n</sup>c<sup>n</sup>} ist nicht kontextfrei.

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

2020-03-29T14:36:19Z

← Nächstältere Version		Version vom 29. März 2020, 14:36 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>

	=Fachbegriffe=		=Fachbegriffe=

	Nicht-terminal-symbole, Terminal-Symbole, Startsymbol, Produktionsregeln, Ableitung (eines Wortes), Sprache		Nicht-terminal-symbole, Terminal-Symbole, Startsymbol, Produktionsregeln, Ableitung (eines Wortes), Sprache

Akaibel am 23. Juni 2019 um 13:41 Uhr

2019-06-23T13:41:40Z

← Nächstältere Version		Version vom 23. Juni 2019, 13:41 Uhr
Zeile 3:		Zeile 3:
	[[Kategorie:Informatik-Abitur]]		[[Kategorie:Informatik-Abitur]]
	[[Kategorie:Informatik]]		[[Kategorie:Informatik]]
			=Fachbegriffe=

			Nicht-terminal-symbole, Terminal-Symbole, Startsymbol, Produktionsregeln, Ableitung (eines Wortes), Sprache

	=Definition=		=Definition=

Akaibel: Die Seite wurde neu angelegt: „Kategorie:endliche Automaten Kategorie:Informatik-Q2 Kategorie:Informatik-Abitur Kategorie:Informatik =Definition= Eine '''Grammatik''' G wird…“

2017-11-24T19:51:40Z

Die Seite wurde neu angelegt: „Kategorie:endliche Automaten Kategorie:Informatik-Q2 Kategorie:Informatik-Abitur Kategorie:Informatik =Definition= Eine '''Grammatik''' G wird…“

Neue Seite

[[Kategorie:endliche Automaten]]
[[Kategorie:Informatik-Q2]]
[[Kategorie:Informatik-Abitur]]
[[Kategorie:Informatik]]

=Definition=
Eine '''Grammatik''' G wird durch ein 4-Tupel (N, T, S, P) definiert:
* N ist die Menge der '''Nichtterminalsymbole'''.
* T ist die Menge der '''Terminalsymbole'''.
* S ∈ N ist das '''Startsymbol'''.
* P ist die Menge der '''Produktionsregeln'''.

Eine '''kontextfreie''' Grammatik ist eine Grammatik, bei der alle Produktionen den folgenden Anforderungen genügen:
* '''links''' darf nur ein Nichtterminal stehen.
* '''rechts''' darf eine (endliche) Kombination von Terminal- und Nichtterminal-Symbolen stehen.

Somit ist klar, dass jede [[reguläre Grammatik]] auch eine kontextfreie Grammatik ist.

=Beispiel=

Die Sprache L = {anbn} lässt sich mit einer kontextfreien Grammatik erzeugen:
* G= (N, T, S, P)
* '''Nichtterminalsymbole''' N = {S}
* '''Terminalsymbole''' T = {a,b}
* '''Startsymbol''' S = S
* '''Produktionsregeln P = {'''
** S → aSb | ε
* '''}'''

===Beispiel für die Ableitung eines Wortes===
Dass das Wort "aabb" zur Sprache L gehört, lässt sich durch folgende Ableitung zeigen:
* S → aSb → aaSbb → aabb
Bei der letzten Ableitung wurde das S durch nichts (ε) ersetzt.

=Zusammenhang zum Kellerautomat=
Jede kontextfreie Sprache lässt sich durch einen nicht-deterministischen [[Kellerautomat]] überprüfen.

=Grenzen der kontextfreien Sprache=
Die Sprache L = {anbncn} ist nicht kontextfrei.