<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="de">
	<id>https://wiki.flbk-hamm.de/index.php?action=history&amp;feed=atom&amp;title=Kontextfreie_Grammatik</id>
	<title>Kontextfreie Grammatik - Versionsgeschichte</title>
	<link rel="self" type="application/atom+xml" href="https://wiki.flbk-hamm.de/index.php?action=history&amp;feed=atom&amp;title=Kontextfreie_Grammatik"/>
	<link rel="alternate" type="text/html" href="https://wiki.flbk-hamm.de/index.php?title=Kontextfreie_Grammatik&amp;action=history"/>
	<updated>2026-11-16T00:45:51Z</updated>
	<subtitle>Versionsgeschichte dieser Seite in FLBK-Wiki</subtitle>
	<generator>MediaWiki 1.46.2</generator>
	<entry>
		<id>https://wiki.flbk-hamm.de/index.php?title=Kontextfreie_Grammatik&amp;diff=3122&amp;oldid=prev</id>
		<title>Flbkwikiadmin am 11. November 2026 um 21:05 Uhr</title>
		<link rel="alternate" type="text/html" href="https://wiki.flbk-hamm.de/index.php?title=Kontextfreie_Grammatik&amp;diff=3122&amp;oldid=prev"/>
		<updated>2026-11-11T21:05:38Z</updated>

		<summary type="html">&lt;p&gt;&lt;/p&gt;
&lt;a href=&quot;https://wiki.flbk-hamm.de/index.php?title=Kontextfreie_Grammatik&amp;amp;diff=3122&amp;amp;oldid=3059&quot;&gt;Änderungen zeigen&lt;/a&gt;</summary>
		<author><name>Flbkwikiadmin</name></author>
	</entry>
	<entry>
		<id>https://wiki.flbk-hamm.de/index.php?title=Kontextfreie_Grammatik&amp;diff=3059&amp;oldid=prev</id>
		<title>Flbkwikiadmin: Die Seite wurde neu angelegt: „Kontextfreie Grammatiken beschreiben verschachtelte Strukturen wie Klammern und Programmblöcke. Dafür reichen reguläre Sprachen nicht aus.  ==Definition== Eine &#039;&#039;&#039;kontextfreie Grammatik&#039;&#039;&#039; ist eine formale Grammatik &lt;math&gt;G = (N, T, P, S)&lt;/math&gt;, deren Regeln links genau ein Nichtterminal haben:  :&lt;math&gt;A \to \beta&lt;/math&gt; mit &lt;math&gt;A \in N&lt;/math&gt; und &lt;math&gt;\beta \in (N \cup T)^*&lt;/math&gt;  Die rechte Seite &lt;ma…“</title>
		<link rel="alternate" type="text/html" href="https://wiki.flbk-hamm.de/index.php?title=Kontextfreie_Grammatik&amp;diff=3059&amp;oldid=prev"/>
		<updated>2026-11-08T08:08:48Z</updated>

		<summary type="html">&lt;p&gt;Die Seite wurde neu angelegt: „Kontextfreie Grammatiken beschreiben verschachtelte Strukturen wie Klammern und Programmblöcke. Dafür reichen &lt;a href=&quot;/Regul%C3%A4re_Grammatik&quot; title=&quot;Reguläre Grammatik&quot;&gt;reguläre Sprachen&lt;/a&gt; nicht aus.  ==Definition== Eine &amp;#039;&amp;#039;&amp;#039;kontextfreie Grammatik&amp;#039;&amp;#039;&amp;#039; ist eine &lt;a href=&quot;/Formale_Grammatik&quot; title=&quot;Formale Grammatik&quot;&gt;formale Grammatik&lt;/a&gt; &amp;lt;math&amp;gt;G = (N, T, P, S)&amp;lt;/math&amp;gt;, deren Regeln links genau ein Nichtterminal haben:  :&amp;lt;math&amp;gt;A \to \beta&amp;lt;/math&amp;gt; mit &amp;lt;math&amp;gt;A \in N&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;\beta \in (N \cup T)^*&amp;lt;/math&amp;gt;  Die rechte Seite &amp;lt;ma…“&lt;/p&gt;
&lt;p&gt;&lt;b&gt;Neue Seite&lt;/b&gt;&lt;/p&gt;&lt;div&gt;Kontextfreie Grammatiken beschreiben verschachtelte Strukturen wie Klammern und Programmblöcke. Dafür reichen [[Reguläre Grammatik|reguläre Sprachen]] nicht aus.&lt;br /&gt;
&lt;br /&gt;
==Definition==&lt;br /&gt;
Eine &amp;#039;&amp;#039;&amp;#039;kontextfreie Grammatik&amp;#039;&amp;#039;&amp;#039; ist eine [[Formale Grammatik|formale Grammatik]] &amp;lt;math&amp;gt;G = (N, T, P, S)&amp;lt;/math&amp;gt;, deren Regeln links genau ein Nichtterminal haben:&lt;br /&gt;
&lt;br /&gt;
:&amp;lt;math&amp;gt;A \to \beta&amp;lt;/math&amp;gt; mit &amp;lt;math&amp;gt;A \in N&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;\beta \in (N \cup T)^*&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Die rechte Seite &amp;lt;math&amp;gt;\beta&amp;lt;/math&amp;gt; ist eine beliebige, auch leere Folge aus Nichtterminalen und Terminalen. Weil links nur ein einzelnes Nichtterminal steht, ersetzt die Regel es unabhängig vom Umfeld, dem Kontext. Die erzeugten Sprachen heißen &amp;#039;&amp;#039;&amp;#039;kontextfreie Sprachen&amp;#039;&amp;#039;&amp;#039;. Sie bilden Typ 2 der [[Chomsky-Hierarchie]]. Passende Automaten sind die [[Kellerautomat|Kellerautomaten]].&lt;br /&gt;
&lt;br /&gt;
==Links- und Rechtsableitung==&lt;br /&gt;
Enthält eine Zeichenfolge mehrere Nichtterminale, lässt sich die Reihenfolge der Ersetzungen wählen. Zwei Reihenfolgen haben eigene Namen:&lt;br /&gt;
&lt;br /&gt;
* Die &amp;#039;&amp;#039;&amp;#039;Linksableitung&amp;#039;&amp;#039;&amp;#039; ersetzt in jedem Schritt das am weitesten links stehende Nichtterminal.&lt;br /&gt;
* Die &amp;#039;&amp;#039;&amp;#039;Rechtsableitung&amp;#039;&amp;#039;&amp;#039; ersetzt in jedem Schritt das am weitesten rechts stehende Nichtterminal.&lt;br /&gt;
&lt;br /&gt;
==Ableitungsbaum==&lt;br /&gt;
Ein &amp;#039;&amp;#039;&amp;#039;Ableitungsbaum&amp;#039;&amp;#039;&amp;#039; (auch Syntaxbaum) zeigt, wie ein Wort aus dem Startsymbol entsteht:&lt;br /&gt;
&lt;br /&gt;
* Die Wurzel ist das Startsymbol.&lt;br /&gt;
* Jeder innere Knoten ist ein Nichtterminal. Seine Kinder sind, von links nach rechts, die Symbole der rechten Seite der angewendeten Regel. Bei einer Regel &amp;lt;math&amp;gt;A \to \varepsilon&amp;lt;/math&amp;gt; ist &amp;lt;math&amp;gt;\varepsilon&amp;lt;/math&amp;gt; das einzige Kind.&lt;br /&gt;
* Die Blätter ergeben von links nach rechts gelesen das Wort.&lt;br /&gt;
&lt;br /&gt;
Zu jedem Ableitungsbaum gibt es genau eine Linksableitung und genau eine Rechtsableitung. Sie unterscheiden sich nur in der Reihenfolge, in der die Knoten ersetzt werden. Auch der Artikel [[Syntax#Ableitungsbaum|Syntax]] erklärt den Ableitungsbaum am Satzbau.&lt;br /&gt;
&lt;br /&gt;
==Mehrdeutigkeit==&lt;br /&gt;
Eine kontextfreie Grammatik ist &amp;#039;&amp;#039;&amp;#039;mehrdeutig&amp;#039;&amp;#039;&amp;#039;, wenn es für mindestens ein Wort zwei verschiedene Ableitungsbäume gibt. Zwei Ableitungen desselben Baums, etwa eine Links- und eine Rechtsableitung, sind keine Mehrdeutigkeit.&lt;br /&gt;
&lt;br /&gt;
Bei einem mehrdeutigen Wort legt die Grammatik nicht fest, welche Struktur gemeint ist. Mehrdeutigkeit ist eine Eigenschaft der Grammatik, nicht der Sprache: Dieselbe Sprache kann sowohl durch eine mehrdeutige als auch durch eine eindeutige Grammatik beschrieben werden.&lt;br /&gt;
&lt;br /&gt;
==Grenzen regulärer Sprachen==&lt;br /&gt;
Ein [[Deterministischer endlicher Automat|DEA]] hat endlich viele Zustände und kann deshalb nicht beliebig weit zählen. Der Grund:&lt;br /&gt;
&lt;br /&gt;
* Hat der DEA &amp;lt;math&amp;gt;n&amp;lt;/math&amp;gt; Zustände, durchläuft er beim Lesen von &amp;lt;math&amp;gt;n&amp;lt;/math&amp;gt; Zeichen &amp;lt;math&amp;gt;n + 1&amp;lt;/math&amp;gt; Zustände. Also wiederholt sich ein Zustand (Schubfachprinzip), und es entsteht eine Schleife.&lt;br /&gt;
* Die Schleife lässt sich beliebig oft durchlaufen. Nach jedem Durchlauf ist der Automat im selben Zustand.&lt;br /&gt;
* Der DEA kann deshalb nicht mehr unterscheiden, wie oft die Schleife durchlaufen wurde. Die gelesene Anzahl geht verloren.&lt;br /&gt;
&lt;br /&gt;
Verlangt eine Sprache, dass eine unbegrenzte Anzahl mitgezählt wird, erkennt kein DEA sie: Die Sprache ist nicht regulär. Eine kontextfreie Grammatik kann solche Anzahlen vergleichen, weil eine Regel das Nichtterminal in der Mitte der rechten Seite stehen lassen kann (&amp;lt;math&amp;gt;A \to \beta_1 A \beta_2&amp;lt;/math&amp;gt;). Dann entstehen links und rechts davon gleichzeitig neue Zeichen.&lt;br /&gt;
&lt;br /&gt;
Jede reguläre Sprache ist kontextfrei, denn reguläre Regeln haben auch die Form &amp;lt;math&amp;gt;A \to \beta&amp;lt;/math&amp;gt;. Die Umkehrung gilt nicht.&lt;br /&gt;
&lt;br /&gt;
==Pumping-Lemma==&lt;br /&gt;
Das &amp;#039;&amp;#039;&amp;#039;Pumping-Lemma&amp;#039;&amp;#039;&amp;#039; beschreibt eine Eigenschaft, die jede reguläre Sprache hat. Zu jeder regulären Sprache &amp;lt;math&amp;gt;L&amp;lt;/math&amp;gt; gibt es eine Zahl &amp;lt;math&amp;gt;n \geq 1&amp;lt;/math&amp;gt;, sodass jedes Wort &amp;lt;math&amp;gt;w \in L&amp;lt;/math&amp;gt; mit &amp;lt;math&amp;gt;|w| \geq n&amp;lt;/math&amp;gt; eine Zerlegung &amp;lt;math&amp;gt;w = xyz&amp;lt;/math&amp;gt; hat mit&lt;br /&gt;
&lt;br /&gt;
* &amp;lt;math&amp;gt;|xy| \leq n&amp;lt;/math&amp;gt;,&lt;br /&gt;
* &amp;lt;math&amp;gt;|y| \geq 1&amp;lt;/math&amp;gt; und&lt;br /&gt;
* &amp;lt;math&amp;gt;xy^iz \in L&amp;lt;/math&amp;gt; für alle &amp;lt;math&amp;gt;i \geq 0&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
Der Teil &amp;lt;math&amp;gt;y&amp;lt;/math&amp;gt; lässt sich also beliebig oft wiederholen („aufpumpen“) oder weglassen, ohne dass das Wort die Sprache verlässt.&lt;br /&gt;
&lt;br /&gt;
Das Lemma dient dem Nachweis, dass eine Sprache nicht regulär ist. Es ist nur eine notwendige Bedingung: Erfüllt eine Sprache das Lemma, folgt daraus nicht, dass sie regulär ist. Der Nachweis verläuft so:&lt;br /&gt;
&lt;br /&gt;
# Annahme: &amp;lt;math&amp;gt;L&amp;lt;/math&amp;gt; ist regulär. Dann gibt es eine Zahl &amp;lt;math&amp;gt;n&amp;lt;/math&amp;gt; wie im Lemma.&lt;br /&gt;
# Ein Wort &amp;lt;math&amp;gt;w \in L&amp;lt;/math&amp;gt; mit &amp;lt;math&amp;gt;|w| \geq n&amp;lt;/math&amp;gt; wählen, abhängig von &amp;lt;math&amp;gt;n&amp;lt;/math&amp;gt;.&lt;br /&gt;
# Das Lemma liefert eine Zerlegung &amp;lt;math&amp;gt;w = xyz&amp;lt;/math&amp;gt;, die nicht frei wählbar ist. Wegen &amp;lt;math&amp;gt;|xy| \leq n&amp;lt;/math&amp;gt; liegt &amp;lt;math&amp;gt;y&amp;lt;/math&amp;gt; im vorderen Teil von &amp;lt;math&amp;gt;w&amp;lt;/math&amp;gt;.&lt;br /&gt;
# Für jede solche Zerlegung ein &amp;lt;math&amp;gt;i&amp;lt;/math&amp;gt; mit &amp;lt;math&amp;gt;xy^iz \notin L&amp;lt;/math&amp;gt; zeigen. Das widerspricht dem Lemma. Also ist &amp;lt;math&amp;gt;L&amp;lt;/math&amp;gt; nicht regulär.&lt;br /&gt;
&lt;br /&gt;
==Beispiele==&lt;br /&gt;
===Klammerausdrücke ableiten===&lt;br /&gt;
Die Grammatik mit dem Startsymbol &amp;lt;math&amp;gt;S&amp;lt;/math&amp;gt; und den Terminalen &amp;lt;code&amp;gt;(&amp;lt;/code&amp;gt; und &amp;lt;code&amp;gt;)&amp;lt;/code&amp;gt; erzeugt korrekt geklammerte Ausdrücke. Ihre Regeln:&lt;br /&gt;
&lt;br /&gt;
:&amp;lt;math&amp;gt;S \to (S)S \mid \varepsilon&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Die Regel &amp;lt;math&amp;gt;S \to (S)S&amp;lt;/math&amp;gt; setzt ein Klammerpaar, in dem ein Ausdruck steht, und lässt einen weiteren Ausdruck folgen. Die Regel &amp;lt;math&amp;gt;S \to \varepsilon&amp;lt;/math&amp;gt; beendet die Ableitung. Das Wort &amp;lt;code&amp;gt;()()&amp;lt;/code&amp;gt; lässt sich auf zwei Arten ableiten.&lt;br /&gt;
&lt;br /&gt;
Die Linksableitung ersetzt immer das am weitesten links stehende &amp;lt;math&amp;gt;S&amp;lt;/math&amp;gt;:&lt;br /&gt;
&lt;br /&gt;
:&amp;lt;math&amp;gt;S \Rightarrow (S)S \Rightarrow ()S \Rightarrow ()(S)S \Rightarrow ()()S \Rightarrow ()()&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Die Rechtsableitung ersetzt immer das am weitesten rechts stehende &amp;lt;math&amp;gt;S&amp;lt;/math&amp;gt;:&lt;br /&gt;
&lt;br /&gt;
:&amp;lt;math&amp;gt;S \Rightarrow (S)S \Rightarrow (S)(S)S \Rightarrow (S)(S) \Rightarrow (S)() \Rightarrow ()()&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
[[Datei:Ableitungsbaum Klammerausdruck.png|mini|Ableitungsbaum des Wortes ()()]]&lt;br /&gt;
Der Ableitungsbaum zeigt die Struktur. Die Wurzel &amp;lt;math&amp;gt;S&amp;lt;/math&amp;gt; hat die Kinder &amp;lt;code&amp;gt;(&amp;lt;/code&amp;gt;, &amp;lt;math&amp;gt;S&amp;lt;/math&amp;gt;, &amp;lt;code&amp;gt;)&amp;lt;/code&amp;gt; und &amp;lt;math&amp;gt;S&amp;lt;/math&amp;gt;. Das erste innere &amp;lt;math&amp;gt;S&amp;lt;/math&amp;gt; wird zu &amp;lt;math&amp;gt;\varepsilon&amp;lt;/math&amp;gt;. Das letzte &amp;lt;math&amp;gt;S&amp;lt;/math&amp;gt; hat wieder die Kinder &amp;lt;code&amp;gt;(&amp;lt;/code&amp;gt;, &amp;lt;math&amp;gt;S&amp;lt;/math&amp;gt;, &amp;lt;code&amp;gt;)&amp;lt;/code&amp;gt; und &amp;lt;math&amp;gt;S&amp;lt;/math&amp;gt;, und beide &amp;lt;math&amp;gt;S&amp;lt;/math&amp;gt; werden zu &amp;lt;math&amp;gt;\varepsilon&amp;lt;/math&amp;gt;. Die Blätter ergeben von links nach rechts &amp;lt;code&amp;gt;()()&amp;lt;/code&amp;gt;. Links- und Rechtsableitung gehören zu demselben Baum.&lt;br /&gt;
&lt;br /&gt;
===Nichtzugehörigkeit begründen===&lt;br /&gt;
Gehört das Wort &amp;lt;code&amp;gt;(()&amp;lt;/code&amp;gt; zur Sprache der Grammatik &amp;lt;math&amp;gt;S \to (S)S \mid \varepsilon&amp;lt;/math&amp;gt;? Nein. Die Regel &amp;lt;math&amp;gt;S \to (S)S&amp;lt;/math&amp;gt; erzeugt je eine öffnende und eine schließende Klammer, die Regel &amp;lt;math&amp;gt;S \to \varepsilon&amp;lt;/math&amp;gt; keine. Jede Ableitung erzeugt deshalb gleich viele &amp;lt;code&amp;gt;(&amp;lt;/code&amp;gt; und &amp;lt;code&amp;gt;)&amp;lt;/code&amp;gt;. Das Wort &amp;lt;code&amp;gt;(()&amp;lt;/code&amp;gt; hat zwei &amp;lt;code&amp;gt;(&amp;lt;/code&amp;gt; und nur eine &amp;lt;code&amp;gt;)&amp;lt;/code&amp;gt;. Es gehört nicht zur Sprache.&lt;br /&gt;
&lt;br /&gt;
===Mehrdeutigkeit nachweisen===&lt;br /&gt;
Bedingte Anweisungen lassen sich mit einer Grammatik beschreiben: &amp;lt;code&amp;gt;i&amp;lt;/code&amp;gt; steht für &amp;lt;code&amp;gt;if (...)&amp;lt;/code&amp;gt; (wenn), &amp;lt;code&amp;gt;e&amp;lt;/code&amp;gt; für &amp;lt;code&amp;gt;else&amp;lt;/code&amp;gt; (sonst) und &amp;lt;code&amp;gt;a&amp;lt;/code&amp;gt; für eine Anweisung. Die Regeln:&lt;br /&gt;
&lt;br /&gt;
:&amp;lt;math&amp;gt;S \to iS \mid iSeS \mid a&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Die Regel &amp;lt;math&amp;gt;S \to iS&amp;lt;/math&amp;gt; beschreibt ein &amp;lt;code&amp;gt;if&amp;lt;/code&amp;gt; ohne &amp;lt;code&amp;gt;else&amp;lt;/code&amp;gt;, die Regel &amp;lt;math&amp;gt;S \to iSeS&amp;lt;/math&amp;gt; ein &amp;lt;code&amp;gt;if&amp;lt;/code&amp;gt; mit &amp;lt;code&amp;gt;else&amp;lt;/code&amp;gt;. Das Wort &amp;lt;code&amp;gt;iiaea&amp;lt;/code&amp;gt; hat zwei Ableitungsbäume:&lt;br /&gt;
&lt;br /&gt;
[[Datei:Mehrdeutigkeit Wenn-dann-sonst.png|mini|Zwei Ableitungsbäume für iiaea]]&lt;br /&gt;
* Linker Baum: Die Wurzel verwendet &amp;lt;math&amp;gt;S \to iS&amp;lt;/math&amp;gt;, das innere &amp;lt;math&amp;gt;S&amp;lt;/math&amp;gt; verwendet &amp;lt;math&amp;gt;S \to iSeS&amp;lt;/math&amp;gt;. Das &amp;lt;code&amp;gt;else&amp;lt;/code&amp;gt; gehört zum inneren &amp;lt;code&amp;gt;if&amp;lt;/code&amp;gt;.&lt;br /&gt;
* Rechter Baum: Die Wurzel verwendet &amp;lt;math&amp;gt;S \to iSeS&amp;lt;/math&amp;gt;, das erste &amp;lt;math&amp;gt;S&amp;lt;/math&amp;gt; darunter verwendet &amp;lt;math&amp;gt;S \to iS&amp;lt;/math&amp;gt;. Das &amp;lt;code&amp;gt;else&amp;lt;/code&amp;gt; gehört zum äußeren &amp;lt;code&amp;gt;if&amp;lt;/code&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
Das Wort hat zwei verschiedene Bäume, die Grammatik ist also mehrdeutig. Java legt zusätzlich fest: Das &amp;lt;code&amp;gt;else&amp;lt;/code&amp;gt; gehört zum nächstgelegenen &amp;lt;code&amp;gt;if&amp;lt;/code&amp;gt; davor. Das entspricht dem linken Baum.&lt;br /&gt;
&lt;br /&gt;
===Nicht-Regularität begründen===&lt;br /&gt;
Die Sprache &amp;lt;math&amp;gt;L = \{0^n 1^n \mid n \geq 1\}&amp;lt;/math&amp;gt; ist nicht regulär:&lt;br /&gt;
&lt;br /&gt;
# Annahme: Ein DEA mit &amp;lt;math&amp;gt;k&amp;lt;/math&amp;gt; Zuständen erkennt &amp;lt;math&amp;gt;L&amp;lt;/math&amp;gt;.&lt;br /&gt;
# Das Wort &amp;lt;math&amp;gt;0^k 1^k&amp;lt;/math&amp;gt; gehört zu &amp;lt;math&amp;gt;L&amp;lt;/math&amp;gt;. Beim Lesen von &amp;lt;math&amp;gt;0^k&amp;lt;/math&amp;gt; durchläuft der DEA &amp;lt;math&amp;gt;k + 1&amp;lt;/math&amp;gt; Zustände. Ein Zustand wiederholt sich (Schubfachprinzip). Die Schleife dazwischen hat die Länge &amp;lt;math&amp;gt;m \geq 1&amp;lt;/math&amp;gt;.&lt;br /&gt;
# Der DEA kann die Schleife einmal mehr durchlaufen. Nach &amp;lt;math&amp;gt;0^{k+m}&amp;lt;/math&amp;gt; ist er im selben Zustand wie nach &amp;lt;math&amp;gt;0^k&amp;lt;/math&amp;gt;.&lt;br /&gt;
# Danach liest er &amp;lt;math&amp;gt;1^k&amp;lt;/math&amp;gt; und endet im selben Endzustand wie bei &amp;lt;math&amp;gt;0^k 1^k&amp;lt;/math&amp;gt;. Er akzeptiert also &amp;lt;math&amp;gt;0^{k+m} 1^k&amp;lt;/math&amp;gt;.&lt;br /&gt;
# Dieses Wort hat mehr Nullen als Einsen und gehört nicht zu &amp;lt;math&amp;gt;L&amp;lt;/math&amp;gt;. Das ist ein Widerspruch. Also gibt es keinen DEA für &amp;lt;math&amp;gt;L&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
===Pumping-Lemma anwenden===&lt;br /&gt;
Für dieselbe Sprache &amp;lt;math&amp;gt;L = \{0^n 1^n \mid n \geq 1\}&amp;lt;/math&amp;gt; gilt:&lt;br /&gt;
&lt;br /&gt;
# Annahme: &amp;lt;math&amp;gt;L&amp;lt;/math&amp;gt; ist regulär, und &amp;lt;math&amp;gt;n&amp;lt;/math&amp;gt; ist die Zahl aus dem Pumping-Lemma.&lt;br /&gt;
# Gewählt wird &amp;lt;math&amp;gt;w = 0^n 1^n&amp;lt;/math&amp;gt;. Es gilt &amp;lt;math&amp;gt;w \in L&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;|w| = 2n \geq n&amp;lt;/math&amp;gt;.&lt;br /&gt;
# Das Lemma liefert eine Zerlegung &amp;lt;math&amp;gt;w = xyz&amp;lt;/math&amp;gt; mit &amp;lt;math&amp;gt;|xy| \leq n&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;|y| \geq 1&amp;lt;/math&amp;gt;. Die ersten &amp;lt;math&amp;gt;n&amp;lt;/math&amp;gt; Zeichen von &amp;lt;math&amp;gt;w&amp;lt;/math&amp;gt; sind Nullen. Also besteht &amp;lt;math&amp;gt;y&amp;lt;/math&amp;gt; nur aus Nullen und enthält mindestens eine.&lt;br /&gt;
# Für &amp;lt;math&amp;gt;i = 2&amp;lt;/math&amp;gt; hat &amp;lt;math&amp;gt;xy^2z&amp;lt;/math&amp;gt; mehr als &amp;lt;math&amp;gt;n&amp;lt;/math&amp;gt; Nullen, aber nur &amp;lt;math&amp;gt;n&amp;lt;/math&amp;gt; Einsen. Das Wort gehört nicht zu &amp;lt;math&amp;gt;L&amp;lt;/math&amp;gt;. Das widerspricht &amp;lt;math&amp;gt;xy^iz \in L&amp;lt;/math&amp;gt; für alle &amp;lt;math&amp;gt;i \geq 0&amp;lt;/math&amp;gt;. Also ist &amp;lt;math&amp;gt;L&amp;lt;/math&amp;gt; nicht regulär.&lt;br /&gt;
&lt;br /&gt;
[[Kategorie:Formale Sprachen]]&lt;br /&gt;
[[Kategorie:AHR I Informatik LK]]&lt;/div&gt;</summary>
		<author><name>Flbkwikiadmin</name></author>
	</entry>
</feed>