https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=Schnittproblem 2026-05-23T08:16:52Z Versionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale Kopie MediaWiki 1.43.8 https://wiki-de.moshellshocker.dns64.de/index.php?title=Schnittproblem&diff=678226&oldid=prev 2021-03-21T12:15:22Z

<p>Form, typo</p> <p><b>Neue Seite</b></p><div>Das &#039;&#039;&#039;Schnittproblem&#039;&#039;&#039; ist ein Problem der [[Theoretische Informatik|theoretischen Informatik]]. Es ist die Frage, ob die Schnittmenge zweier [[Formale Sprache|formaler Sprachen]], die durch [[Formale Grammatik|Grammatiken]] gegeben sein sollen, leer ist.&lt;ref name=&quot;Socher&quot; /&gt;<br /> <br /> Für zwei [[reguläre Sprache]]n ist der Schnitt wieder regulär. Damit ist das Problem äquivalent zum [[Leerheitsproblem]] für reguläre Sprachen, das heißt, dass die Antwort auf die Frage zum Schnittproblem [[Berechenbarkeit|berechenbar]] ist.<br /> <br /> Für zwei [[kontextfreie Sprache]]n ist das Schnittproblem unentscheidbar.&lt;ref name=&quot;Socher&quot; /&gt;<br /> <br /> == Siehe auch ==<br /> * [[Äquivalenzproblem]]<br /> <br /> == Einzelnachweise ==<br /> &lt;references&gt;<br /> &lt;ref name=&quot;Socher&quot;&gt;{{Literatur |Autor=Rolf Socher |Titel=Theoretische Grundlagen der Informatik |Auflage=3. aktualisierte und erweiterte |Verlag=Hanser Fachbuchverlag |Datum=2007 |ISBN=978-3-446-41260-6 |Seiten=156 |Online={{Google Buch|BuchID=rnkfsy-uMG8C|Seite=156|Hervorhebung=Schnittproblem}}}}&lt;/ref&gt;<br /> &lt;/references&gt;<br /> <br /> [[Kategorie:Theorie formaler Sprachen]]</div>

imported>Phzh