Quelltext der Seite Schnittproblem

Das '''Schnittproblem''' 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.<ref name="Socher" />

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.

Für zwei [[kontextfreie Sprache]]n ist das Schnittproblem unentscheidbar.<ref name="Socher" />

== Siehe auch ==
* [[Äquivalenzproblem]]

== Einzelnachweise ==
<references>
<ref name="Socher">{{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}}}}</ref>
</references>

[[Kategorie:Theorie formaler Sprachen]]