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.[1]

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.[1]

Siehe auch

Äquivalenzproblem

Einzelnachweise

Rolf Socher: Theoretische Grundlagen der Informatik. 3. aktualisierte und erweiterte Auflage. Hanser Fachbuchverlag, 2007, ISBN 978-3-446-41260-6, S. 156 (eingeschränkte Vorschau in der Google-Buchsuche).

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

[Socher-1] Rolf Socher: Theoretische Grundlagen der Informatik. 3. aktualisierte und erweiterte Auflage. Hanser Fachbuchverlag, 2007, ISBN 978-3-446-41260-6, S. 156 (eingeschränkte Vorschau in der Google-Buchsuche).