Cutting problem

from Wikipedia, the free encyclopedia

The intersection problem is a problem of theoretical computer science . The question is whether the intersection of two formal languages that should be given by grammars is empty.

The cut is regular again for two regular languages . The problem is thus equivalent to the emptiness problem for regular languages, that is, the answer to the question about the intersection problem is computable .

For two context-free languages the intersection problem is undecidable.

See also

Individual evidence

  1. ↑ a b Rolf Socher: Theoretical Foundations of Computer Science . 3rd updated and expanded edition. Hanser Fachbuchverlag, 2007, ISBN 978-3-446-41260-6 , p. 156 ( limited preview in Google Book search).