Schnittproblem
Das Schnittproblem ist ein Problem der theoretischen Informatik. Es ist die Frage, ob die Schnittmenge zweier formaler Sprachen, die durch Grammatiken gegeben sein sollen, leer ist.<ref name="Socher" />
Für zwei reguläre Sprachen 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 berechenbar ist.
Für zwei kontextfreie Sprachen ist das Schnittproblem unentscheidbar.<ref name="Socher" />
Siehe auch
Einzelnachweise
<references> <ref name="Socher">{{#invoke:Vorlage:Literatur|f}}</ref> </references>