<?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=Chomsky-Hierarchie</id>
	<title>Chomsky-Hierarchie - Versionsgeschichte</title>
	<link rel="self" type="application/atom+xml" href="https://wiki.flbk-hamm.de/index.php?action=history&amp;feed=atom&amp;title=Chomsky-Hierarchie"/>
	<link rel="alternate" type="text/html" href="https://wiki.flbk-hamm.de/index.php?title=Chomsky-Hierarchie&amp;action=history"/>
	<updated>2026-11-16T00:45:41Z</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=Chomsky-Hierarchie&amp;diff=3116&amp;oldid=prev</id>
		<title>Flbkwikiadmin am 11. November 2026 um 21:03 Uhr</title>
		<link rel="alternate" type="text/html" href="https://wiki.flbk-hamm.de/index.php?title=Chomsky-Hierarchie&amp;diff=3116&amp;oldid=prev"/>
		<updated>2026-11-11T21:03:39Z</updated>

		<summary type="html">&lt;p&gt;&lt;/p&gt;
&lt;table style=&quot;background-color: #fff; color: #202122;&quot; data-mw-interface=&quot;&quot;&gt;
				&lt;col class=&quot;diff-marker&quot; /&gt;
				&lt;col class=&quot;diff-content&quot; /&gt;
				&lt;col class=&quot;diff-marker&quot; /&gt;
				&lt;col class=&quot;diff-content&quot; /&gt;
				&lt;tr class=&quot;diff-title&quot; lang=&quot;de&quot;&gt;
				&lt;td colspan=&quot;2&quot; style=&quot;background-color: #fff; color: #202122; text-align: center;&quot;&gt;← Nächstältere Version&lt;/td&gt;
				&lt;td colspan=&quot;2&quot; style=&quot;background-color: #fff; color: #202122; text-align: center;&quot;&gt;Version vom 11. November 2026, 22:03 Uhr&lt;/td&gt;
				&lt;/tr&gt;&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot; id=&quot;mw-diff-left-l2&quot;&gt;Zeile 2:&lt;/td&gt;
&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot;&gt;Zeile 2:&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;==Definition==&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;==Definition==&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;Die &#039;&#039;&#039;Chomsky-Hierarchie&#039;&#039;&#039; teilt Grammatiken nach der Form ihrer Regeln in vier Typen ein: Typ 0 &lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;bis &lt;/del&gt;Typ 3. Je höher die Nummer, desto strenger sind die Regeln. Eine [[Formale Sprache|Sprache]] &lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;wird dem strengsten &lt;/del&gt;Typ &lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;zugeordnet&lt;/del&gt;, für den eine Grammatik &lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;sie &lt;/del&gt;erzeugt.&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;Die &#039;&#039;&#039;Chomsky-Hierarchie&#039;&#039;&#039; teilt Grammatiken nach der Form ihrer Regeln in vier Typen ein: Typ 0 &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;(allgemeine Grammatiken), Typ 1 (kontextsensitive Grammatiken), Typ 2 (kontextfreie Grammatiken) und &lt;/ins&gt;Typ 3 &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;(reguläre Grammatiken)&lt;/ins&gt;. Je höher die Nummer, desto strenger sind &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;die Vorgaben für &lt;/ins&gt;die Regeln&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt; &lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;* Der &#039;&#039;&#039;Typ einer Grammatik&#039;&#039;&#039; ist der strengste Typ, dessen Vorgaben alle ihre Regeln erfüllen&lt;/ins&gt;. Eine &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;einzige Regel, die gegen die Vorgaben eines Typs verstößt, genügt, damit die Grammatik nicht zu diesem Typ gehört.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;* Der &#039;&#039;&#039;Typ einer &lt;/ins&gt;[[Formale Sprache|Sprache]]&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&#039;&#039;&#039; ist der strengste &lt;/ins&gt;Typ, für den &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;es &lt;/ins&gt;eine Grammatik &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;gibt, die die Sprache &lt;/ins&gt;erzeugt&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;. Eine einzelne Grammatik legt den Typ der Sprache deshalb noch nicht fest: Es kann eine andere, strengere Grammatik für dieselbe Sprache geben&lt;/ins&gt;.&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;Die Sprachklassen sind ineinander enthalten. Jede Sprache vom Typ 3 lässt sich auch mit einer Grammatik vom Typ 2 erzeugen, jede Sprache vom Typ 2 auch mit einer vom Typ 1 und jede Sprache vom Typ 1 auch mit einer vom Typ 0. Die Umkehrungen gelten nicht.&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;Die Sprachklassen sind ineinander enthalten. Jede Sprache vom Typ 3 lässt sich auch mit einer Grammatik vom Typ 2 erzeugen, jede Sprache vom Typ 2 auch mit einer vom Typ 1 und jede Sprache vom Typ 1 auch mit einer vom Typ 0. Die Umkehrungen gelten nicht.&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;:&amp;lt;math&amp;gt;\text{Typ 3} \subset \text{Typ 2} \subset \text{Typ 1} \subset \text{Typ 0}&amp;lt;/math&amp;gt;&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;:&amp;lt;math&amp;gt;\text{Typ 3} \subset \text{Typ 2} \subset \text{Typ 1} \subset \text{Typ 0}&amp;lt;/math&amp;gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;Diese Einschlüsse gelten für die Sprachklassen, nicht für jede einzelne Grammatik. Die kontextfreie Grammatik &amp;lt;math&amp;gt;S \to (S)S \mid \varepsilon&amp;lt;/math&amp;gt; zum Beispiel erfüllt die Vorgaben von Typ 1 nicht: Die rechte Seite der Regel &amp;lt;math&amp;gt;S \to \varepsilon&amp;lt;/math&amp;gt; ist kürzer als die linke, und die Ausnahme für das leere Wort (siehe [[#Sprachklassen und Automatenmodelle|Sprachklassen und Automatenmodelle]]) greift nicht, weil &amp;lt;math&amp;gt;S&amp;lt;/math&amp;gt; auch auf einer rechten Regelseite vorkommt. Zu ihr gibt es aber eine gleichwertige Grammatik, die diese Vorgaben erfüllt.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;==Sprachklassen und Automatenmodelle==&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;==Sprachklassen und Automatenmodelle==&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot; id=&quot;mw-diff-left-l17&quot;&gt;Zeile 17:&lt;/td&gt;
&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot;&gt;Zeile 22:&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;| 0 || rekursiv aufzählbar || beliebig, links mindestens ein Nichtterminal || [[Turingmaschine]]&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;| 0 || rekursiv aufzählbar || beliebig, links mindestens ein Nichtterminal || [[Turingmaschine]]&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;|-&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;|-&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;| 1 || kontextsensitiv || rechte Seite mindestens so lang wie die linke&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;, Ausnahme &amp;lt;math&amp;gt;S \to \varepsilon&amp;lt;/math&amp;gt; &lt;/del&gt;|| linear beschränkter Automat&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;| 1 || kontextsensitiv || rechte Seite mindestens so lang wie die linke || linear beschränkter Automat&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;|-&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;|-&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;| 2 || [[Kontextfreie Grammatik|kontextfrei]] || &amp;lt;math&amp;gt;A \to \beta&amp;lt;/math&amp;gt; || [[Kellerautomat]]&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;| 2 || [[Kontextfreie Grammatik|kontextfrei]] || &amp;lt;math&amp;gt;A \to \beta&amp;lt;/math&amp;gt; || [[Kellerautomat]]&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;|-&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;|-&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;| 3 || [[Reguläre Grammatik|regulär]] || &amp;lt;math&amp;gt;A \to aB&amp;lt;/math&amp;gt;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;, &lt;/del&gt;&amp;lt;math&amp;gt;A \to a&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&amp;lt;/math&amp;gt;, Ausnahme &amp;lt;math&amp;gt;S \to \varepsilon&lt;/del&gt;&amp;lt;/math&amp;gt; || [[Endlicher Automat|endlicher Automat]]&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;| 3 || [[Reguläre Grammatik|regulär]] || &amp;lt;math&amp;gt;A \to aB&amp;lt;/math&amp;gt; &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;und &lt;/ins&gt;&amp;lt;math&amp;gt;A \to a&amp;lt;/math&amp;gt; || [[Endlicher Automat|endlicher Automat]]&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;|}&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;|}&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;Für alle kontextfreien Sprachen braucht es nichtdeterministische Kellerautomaten&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;, denn deterministische &lt;/del&gt;erkennen nur einen Teil &lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;von ihnen&lt;/del&gt;.&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;Zu den Regelformen gehören diese Ergänzungen:&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;* &#039;&#039;&#039;Leeres Wort:&#039;&#039;&#039; Bei Typ 1 und bei regulären Grammatiken ist die Regel &amp;lt;math&amp;gt;S \to \varepsilon&amp;lt;/math&amp;gt; als Ausnahme erlaubt, wenn das Startsymbol &amp;lt;math&amp;gt;S&amp;lt;/math&amp;gt; auf keiner rechten Regelseite vorkommt. So kann auch das leere Wort zur Sprache gehören. Bei Typ 2 und bei rechtslinearen Grammatiken darf jedes Nichtterminal eine Regel &amp;lt;math&amp;gt;A \to \varepsilon&amp;lt;/math&amp;gt; haben.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;* &#039;&#039;&#039;Typ 0:&#039;&#039;&#039; Rekursiv aufzählbar heißt eine Sprache, wenn ein Verfahren ihre Wörter nacheinander aufzählen kann. Eine [[Turingmaschine]] akzeptiert dann jedes Wort der Sprache. Bei einer Eingabe, die nicht zur Sprache gehört, hält sie aber möglicherweise nie an.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;* &#039;&#039;&#039;Typ 1:&#039;&#039;&#039; Kontextsensitiv bedeutet, dass eine Regel ein Nichtterminal abhängig von seinen Nachbarzeichen ersetzen darf, dem Kontext. Auf der linken Seite stehen dann neben dem Nichtterminal weitere Zeichen. Die rechte Seite darf nicht kürzer sein als die linke. Einzige Ausnahme ist die Regel &amp;lt;math&amp;gt;S \to \varepsilon&amp;lt;/math&amp;gt;, wenn &amp;lt;math&amp;gt;S&amp;lt;/math&amp;gt; auf keiner rechten Regelseite vorkommt.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;* &#039;&#039;&#039;Typ 2:&#039;&#039;&#039; Links steht genau ein Nichtterminal. Es wird unabhängig von seinen Nachbarzeichen ersetzt, daher der Name kontextfrei.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;* &#039;&#039;&#039;Typ 3:&#039;&#039;&#039; Auch [[Reguläre Grammatik#Rechtslineare Grammatik|rechtslineare Grammatiken]] erzeugen genau die regulären Sprachen und werden deshalb ebenfalls zu Typ 3 gezählt. Jede endliche Sprache ist regulär: Für jedes ihrer Wörter &amp;lt;math&amp;gt;w&amp;lt;/math&amp;gt; genügt eine Regel &amp;lt;math&amp;gt;S \to w&amp;lt;/math&amp;gt;, und eine Grammatik aus solchen Regeln ist rechtslinear.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt; &lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;Die Automatenmodelle unterscheiden sich in ihrem Speicher:&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt; &lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;{| class=&quot;wikitable&quot;&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;! Automatenmodell !! Speicher !! Zugriff auf den Speicher&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;|-&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;| endlicher Automat || nur der aktuelle Zustand || kein zusätzlicher Speicher&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;|-&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;| Kellerautomat || unbegrenzter Keller || nur auf das oberste Zeichen&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;|-&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;| linear beschränkter Automat || Band, so lang wie die Eingabe || lesen und schreiben an jeder Stelle des Bandes&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;|-&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;| Turingmaschine || unbegrenztes Band || lesen und schreiben an jeder Stelle des Bandes&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;|}&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt; &lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;Für alle kontextfreien Sprachen braucht es nichtdeterministische Kellerautomaten&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;. Deterministische Kellerautomaten &lt;/ins&gt;erkennen nur einen Teil &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;der kontextfreien Sprachen, darunter alle regulären&lt;/ins&gt;.&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;==Beispiele==&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;==Beispiele==&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;===Typ einzelner Regeln bestimmen===&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;Für vier Regeln wird der strengste Typ gesucht, dessen Vorgaben die Regel erfüllt. Großbuchstaben sind Nichtterminale, Kleinbuchstaben sind Terminale.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;{| class=&quot;wikitable&quot;&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;! Regel !! strengster Typ !! Begründung&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;|-&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;| &amp;lt;math&amp;gt;B \to bC&amp;lt;/math&amp;gt; || 3 || Links steht ein Nichtterminal, rechts ein Terminal und dahinter ein Nichtterminal.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;|-&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;| &amp;lt;math&amp;gt;S \to aSb&amp;lt;/math&amp;gt; || 2 || Links steht ein Nichtterminal. Rechts steht das Nichtterminal in der Mitte, das erlaubt Typ 3 nicht.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;|-&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;| &amp;lt;math&amp;gt;AB \to BA&amp;lt;/math&amp;gt; || 1 || Links stehen zwei Zeichen, das erlaubt Typ 2 nicht. Die rechte Seite ist so lang wie die linke.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;|-&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;| &amp;lt;math&amp;gt;aAb \to ab&amp;lt;/math&amp;gt; || 0 || Die rechte Seite ist kürzer als die linke, das erlaubt Typ 1 nicht.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;|}&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;===Typ einer Grammatik bestimmen===&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;Gegeben sind drei Grammatiken über den Terminalen &amp;lt;math&amp;gt;K&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;E&amp;lt;/math&amp;gt;:&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;* &#039;&#039;&#039;Grammatik 1&#039;&#039;&#039; mit den Regeln &amp;lt;math&amp;gt;S \to KS \mid KE&amp;lt;/math&amp;gt;: Beide Regeln haben links ein Nichtterminal, und rechts steht das Nichtterminal höchstens am Ende. Die Grammatik ist rechtslinear und gehört zum &#039;&#039;&#039;Typ 3&#039;&#039;&#039;.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;* &#039;&#039;&#039;Grammatik 2&#039;&#039;&#039; mit den Regeln &amp;lt;math&amp;gt;S \to KSE \mid E&amp;lt;/math&amp;gt;: Beide Regeln haben links genau ein Nichtterminal, die Grammatik erfüllt also die Vorgaben von Typ 2. In der Regel &amp;lt;math&amp;gt;S \to KSE&amp;lt;/math&amp;gt; steht das Nichtterminal aber in der Mitte. Diese eine Regel verstößt gegen die Vorgaben von Typ 3. Die Grammatik gehört zum &#039;&#039;&#039;Typ 2&#039;&#039;&#039;.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;* &#039;&#039;&#039;Grammatik 3&#039;&#039;&#039; mit den Regeln &amp;lt;math&amp;gt;S \to KS \mid \varepsilon&amp;lt;/math&amp;gt;: Das Nichtterminal steht höchstens am Ende, die Grammatik ist rechtslinear und gehört zum &#039;&#039;&#039;Typ 3&#039;&#039;&#039;. Sie erfüllt aber nicht die engere Form der regulären Grammatik, denn dort ist &amp;lt;math&amp;gt;S \to \varepsilon&amp;lt;/math&amp;gt; nur erlaubt, wenn &amp;lt;math&amp;gt;S&amp;lt;/math&amp;gt; auf keiner rechten Regelseite vorkommt. Wie daraus eine reguläre Grammatik wird, beschreibt der Abschnitt [[Reguläre Grammatik#Rechtslineare Grammatik|Rechtslineare Grammatik]].&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;===Sprachen einordnen===&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;===Sprachen einordnen===&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;Jede Sprache wird dem strengsten Typ zugeordnet, für den eine Grammatik sie erzeugt.&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;Jede Sprache wird dem strengsten Typ zugeordnet, für den &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;es &lt;/ins&gt;eine Grammatik &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;gibt, die &lt;/ins&gt;sie erzeugt.&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;* Die Wörter des Kaffeeautomaten bilden die endliche Sprache &amp;lt;math&amp;gt;L = \{KKKK&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;, &lt;/del&gt;EE&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;, &lt;/del&gt;EKK&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;, &lt;/del&gt;KEK&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;, &lt;/del&gt;KKE\}&amp;lt;/math&amp;gt;. Ein endlicher Automat erkennt sie, und eine Grammatik mit nur den Regelformen &amp;lt;math&amp;gt;A \to aB&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;A \to a&amp;lt;/math&amp;gt; erzeugt sie, siehe [[Reguläre Grammatik]]. Die Sprache ist regulär: &#039;&#039;&#039;Typ 3&#039;&#039;&#039;.&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;* Die Wörter des Kaffeeautomaten bilden die endliche Sprache &amp;lt;math&amp;gt;L = \{KKKK&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;; &lt;/ins&gt;EE&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;; &lt;/ins&gt;EKK&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;; &lt;/ins&gt;KEK&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;; &lt;/ins&gt;KKE\}&amp;lt;/math&amp;gt;. Ein endlicher Automat erkennt sie, und eine Grammatik mit nur den Regelformen &amp;lt;math&amp;gt;A \to aB&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;A \to a&amp;lt;/math&amp;gt; erzeugt sie, siehe [[Reguläre Grammatik&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;#Grammatik zum Kaffeeautomaten angeben|Grammatik zum Kaffeeautomaten angeben&lt;/ins&gt;]]. Die Sprache ist regulär: &#039;&#039;&#039;Typ 3&#039;&#039;&#039;.&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;* Korrekt geklammerte Ausdrücke erzeugt die Grammatik &amp;lt;math&amp;gt;S \to (S)S \mid \varepsilon&amp;lt;/math&amp;gt;. Ihre Regeln haben links genau ein Nichtterminal, die Sprache ist also kontextfrei, siehe [[Kontextfreie Grammatik]]. Ein endlicher Automat kann beliebig tiefe Klammerung nicht mitzählen, die Sprache ist deshalb nicht regulär, siehe [[Kontextfreie Grammatik#Grenzen regulärer Sprachen|Grenzen regulärer Sprachen]]. Sie gehört zu &amp;#039;&amp;#039;&amp;#039;Typ 2&amp;#039;&amp;#039;&amp;#039;, nicht zu Typ 3.&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;* Korrekt geklammerte Ausdrücke erzeugt die Grammatik &amp;lt;math&amp;gt;S \to (S)S \mid \varepsilon&amp;lt;/math&amp;gt;. Ihre Regeln haben links genau ein Nichtterminal, die Sprache ist also kontextfrei, siehe [[Kontextfreie Grammatik]]. Ein endlicher Automat kann beliebig tiefe Klammerung nicht mitzählen, die Sprache ist deshalb nicht regulär, siehe [[Kontextfreie Grammatik#Grenzen regulärer Sprachen|Grenzen regulärer Sprachen]]. Sie gehört zu &amp;#039;&amp;#039;&amp;#039;Typ 2&amp;#039;&amp;#039;&amp;#039;, nicht zu Typ 3.&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;* Die Sprache &amp;lt;math&amp;gt;\{a^n b^n c^n \mid n \geq 1\}&amp;lt;/math&amp;gt; verlangt gleich viele a, b und c in dieser Reihenfolge. &lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;Sie &lt;/del&gt;ist kontextsensitiv, aber nicht kontextfrei: &#039;&#039;&#039;Typ 1&#039;&#039;&#039;, nicht Typ 2&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;. Der Beweis bleibt hier aus&lt;/del&gt;. Anschaulich &lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;gesagt &lt;/del&gt;kann &lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;ein &lt;/del&gt;Keller &lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;zwei Anzahlen vergleichen&lt;/del&gt;, &lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;aber &lt;/del&gt;nicht &lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;drei&lt;/del&gt;.&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;* Die Sprache &amp;lt;math&amp;gt;\{a^n b^n c^n \mid n \geq 1\}&amp;lt;/math&amp;gt; verlangt gleich viele &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&amp;lt;math&amp;gt;&lt;/ins&gt;a&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&amp;lt;/math&amp;gt;&lt;/ins&gt;, &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&amp;lt;math&amp;gt;&lt;/ins&gt;b&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&amp;lt;/math&amp;gt; &lt;/ins&gt;und &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&amp;lt;math&amp;gt;&lt;/ins&gt;c&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&amp;lt;/math&amp;gt; &lt;/ins&gt;in dieser Reihenfolge. &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;Die Schreibweise mit Exponenten ist eine [[Wort#Wortpotenz|Wortpotenz]]. Die Sprache &lt;/ins&gt;ist kontextsensitiv, aber nicht kontextfrei: &#039;&#039;&#039;Typ 1&#039;&#039;&#039;, nicht Typ 2. Anschaulich&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;: Ein [[Kellerautomat]] &lt;/ins&gt;kann &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;die Anzahl der &amp;lt;math&amp;gt;a&amp;lt;/math&amp;gt; im Keller ablegen und beim Lesen der &amp;lt;math&amp;gt;b&amp;lt;/math&amp;gt; wieder abbauen. Danach ist der &lt;/ins&gt;Keller &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;abgebaut&lt;/ins&gt;, &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;und für den Vergleich mit den &amp;lt;math&amp;gt;c&amp;lt;/math&amp;gt; fehlt die Anzahl.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;* Die Sprache &amp;lt;math&amp;gt;\{K^n E \mid n \geq 1\}&amp;lt;/math&amp;gt; lässt sich mit den Regeln &amp;lt;math&amp;gt;S \to AE&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;A \to KA \mid K&amp;lt;/math&amp;gt; erzeugen. Diese Grammatik ist &lt;/ins&gt;nicht &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;rechtslinear. Trotzdem ist die Sprache regulär, denn die rechtslineare Grammatik &amp;lt;math&amp;gt;S \to KS \mid KE&amp;lt;/math&amp;gt; erzeugt sie ebenfalls, siehe [[Reguläre Grammatik#Grammatik in eine rechtslineare Grammatik umformen|Grammatik in eine rechtslineare Grammatik umformen]]. Die Sprache gehört zu &#039;&#039;&#039;Typ 3&#039;&#039;&#039;: Maßgeblich ist die strengste Grammatik, die es für die Sprache gibt&lt;/ins&gt;.&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;[[Kategorie:Formale Sprachen]]&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;[[Kategorie:Formale Sprachen]]&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;[[Kategorie:Automaten]]&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;[[Kategorie:Automaten]]&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;[[Kategorie:AHR I Informatik LK]]&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;[[Kategorie:AHR I Informatik LK]]&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;

&lt;!-- diff cache key mediawiki:diff:1.41:old-3046:rev-3116:php=table --&gt;
&lt;/table&gt;</summary>
		<author><name>Flbkwikiadmin</name></author>
	</entry>
	<entry>
		<id>https://wiki.flbk-hamm.de/index.php?title=Chomsky-Hierarchie&amp;diff=3046&amp;oldid=prev</id>
		<title>Flbkwikiadmin: Die Seite wurde neu angelegt: „Die Chomsky-Hierarchie ordnet Grammatiken nach der Form ihrer Regeln. Daran lässt sich ablesen, welcher Automat eine Sprache erkennen kann.  ==Definition== Die &#039;&#039;&#039;Chomsky-Hierarchie&#039;&#039;&#039; teilt Grammatiken nach der Form ihrer Regeln in vier Typen ein: Typ 0 bis Typ 3. Je höher die Nummer, desto strenger sind die Regeln. Eine Sprache wird dem strengsten Typ zugeordnet, für den eine Grammatik sie erzeugt.  Die Sprac…“</title>
		<link rel="alternate" type="text/html" href="https://wiki.flbk-hamm.de/index.php?title=Chomsky-Hierarchie&amp;diff=3046&amp;oldid=prev"/>
		<updated>2026-11-08T08:01:14Z</updated>

		<summary type="html">&lt;p&gt;Die Seite wurde neu angelegt: „Die Chomsky-Hierarchie ordnet &lt;a href=&quot;/Formale_Grammatik&quot; title=&quot;Formale Grammatik&quot;&gt;Grammatiken&lt;/a&gt; nach der Form ihrer Regeln. Daran lässt sich ablesen, welcher Automat eine Sprache erkennen kann.  ==Definition== Die &amp;#039;&amp;#039;&amp;#039;Chomsky-Hierarchie&amp;#039;&amp;#039;&amp;#039; teilt Grammatiken nach der Form ihrer Regeln in vier Typen ein: Typ 0 bis Typ 3. Je höher die Nummer, desto strenger sind die Regeln. Eine &lt;a href=&quot;/Formale_Sprache&quot; title=&quot;Formale Sprache&quot;&gt;Sprache&lt;/a&gt; wird dem strengsten Typ zugeordnet, für den eine Grammatik sie erzeugt.  Die Sprac…“&lt;/p&gt;
&lt;p&gt;&lt;b&gt;Neue Seite&lt;/b&gt;&lt;/p&gt;&lt;div&gt;Die Chomsky-Hierarchie ordnet [[Formale Grammatik|Grammatiken]] nach der Form ihrer Regeln. Daran lässt sich ablesen, welcher Automat eine Sprache erkennen kann.&lt;br /&gt;
&lt;br /&gt;
==Definition==&lt;br /&gt;
Die &amp;#039;&amp;#039;&amp;#039;Chomsky-Hierarchie&amp;#039;&amp;#039;&amp;#039; teilt Grammatiken nach der Form ihrer Regeln in vier Typen ein: Typ 0 bis Typ 3. Je höher die Nummer, desto strenger sind die Regeln. Eine [[Formale Sprache|Sprache]] wird dem strengsten Typ zugeordnet, für den eine Grammatik sie erzeugt.&lt;br /&gt;
&lt;br /&gt;
Die Sprachklassen sind ineinander enthalten. Jede Sprache vom Typ 3 lässt sich auch mit einer Grammatik vom Typ 2 erzeugen, jede Sprache vom Typ 2 auch mit einer vom Typ 1 und jede Sprache vom Typ 1 auch mit einer vom Typ 0. Die Umkehrungen gelten nicht.&lt;br /&gt;
&lt;br /&gt;
:&amp;lt;math&amp;gt;\text{Typ 3} \subset \text{Typ 2} \subset \text{Typ 1} \subset \text{Typ 0}&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
==Sprachklassen und Automatenmodelle==&lt;br /&gt;
[[Datei:Chomsky-Hierarchie Übersicht.png|mini|Die Sprachklassen der Chomsky-Hierarchie sind ineinander enthalten]]&lt;br /&gt;
Die Tabelle nennt zu jedem Typ die Sprachklasse, die erlaubte Regelform und den Automaten, der genau diese Sprachen erkennt. Dabei sind &amp;lt;math&amp;gt;A&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;B&amp;lt;/math&amp;gt; Nichtterminale, &amp;lt;math&amp;gt;a&amp;lt;/math&amp;gt; ist ein Terminal und &amp;lt;math&amp;gt;\beta&amp;lt;/math&amp;gt; ist eine beliebige, auch leere Folge aus Nichtterminalen und Terminalen.&lt;br /&gt;
&lt;br /&gt;
{| class=&amp;quot;wikitable&amp;quot;&lt;br /&gt;
! Typ !! Sprachklasse !! Regelform !! Automatenmodell&lt;br /&gt;
|-&lt;br /&gt;
| 0 || rekursiv aufzählbar || beliebig, links mindestens ein Nichtterminal || [[Turingmaschine]]&lt;br /&gt;
|-&lt;br /&gt;
| 1 || kontextsensitiv || rechte Seite mindestens so lang wie die linke, Ausnahme &amp;lt;math&amp;gt;S \to \varepsilon&amp;lt;/math&amp;gt; || linear beschränkter Automat&lt;br /&gt;
|-&lt;br /&gt;
| 2 || [[Kontextfreie Grammatik|kontextfrei]] || &amp;lt;math&amp;gt;A \to \beta&amp;lt;/math&amp;gt; || [[Kellerautomat]]&lt;br /&gt;
|-&lt;br /&gt;
| 3 || [[Reguläre Grammatik|regulär]] || &amp;lt;math&amp;gt;A \to aB&amp;lt;/math&amp;gt;, &amp;lt;math&amp;gt;A \to a&amp;lt;/math&amp;gt;, Ausnahme &amp;lt;math&amp;gt;S \to \varepsilon&amp;lt;/math&amp;gt; || [[Endlicher Automat|endlicher Automat]]&lt;br /&gt;
|}&lt;br /&gt;
&lt;br /&gt;
Für alle kontextfreien Sprachen braucht es nichtdeterministische Kellerautomaten, denn deterministische erkennen nur einen Teil von ihnen.&lt;br /&gt;
&lt;br /&gt;
==Beispiele==&lt;br /&gt;
===Sprachen einordnen===&lt;br /&gt;
Jede Sprache wird dem strengsten Typ zugeordnet, für den eine Grammatik sie erzeugt.&lt;br /&gt;
&lt;br /&gt;
* Die Wörter des Kaffeeautomaten bilden die endliche Sprache &amp;lt;math&amp;gt;L = \{KKKK, EE, EKK, KEK, KKE\}&amp;lt;/math&amp;gt;. Ein endlicher Automat erkennt sie, und eine Grammatik mit nur den Regelformen &amp;lt;math&amp;gt;A \to aB&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;A \to a&amp;lt;/math&amp;gt; erzeugt sie, siehe [[Reguläre Grammatik]]. Die Sprache ist regulär: &amp;#039;&amp;#039;&amp;#039;Typ 3&amp;#039;&amp;#039;&amp;#039;.&lt;br /&gt;
* Korrekt geklammerte Ausdrücke erzeugt die Grammatik &amp;lt;math&amp;gt;S \to (S)S \mid \varepsilon&amp;lt;/math&amp;gt;. Ihre Regeln haben links genau ein Nichtterminal, die Sprache ist also kontextfrei, siehe [[Kontextfreie Grammatik]]. Ein endlicher Automat kann beliebig tiefe Klammerung nicht mitzählen, die Sprache ist deshalb nicht regulär, siehe [[Kontextfreie Grammatik#Grenzen regulärer Sprachen|Grenzen regulärer Sprachen]]. Sie gehört zu &amp;#039;&amp;#039;&amp;#039;Typ 2&amp;#039;&amp;#039;&amp;#039;, nicht zu Typ 3.&lt;br /&gt;
* Die Sprache &amp;lt;math&amp;gt;\{a^n b^n c^n \mid n \geq 1\}&amp;lt;/math&amp;gt; verlangt gleich viele a, b und c in dieser Reihenfolge. Sie ist kontextsensitiv, aber nicht kontextfrei: &amp;#039;&amp;#039;&amp;#039;Typ 1&amp;#039;&amp;#039;&amp;#039;, nicht Typ 2. Der Beweis bleibt hier aus. Anschaulich gesagt kann ein Keller zwei Anzahlen vergleichen, aber nicht drei.&lt;br /&gt;
&lt;br /&gt;
[[Kategorie:Formale Sprachen]]&lt;br /&gt;
[[Kategorie:Automaten]]&lt;br /&gt;
[[Kategorie:AHR I Informatik LK]]&lt;/div&gt;</summary>
		<author><name>Flbkwikiadmin</name></author>
	</entry>
</feed>