Finiteness problem

As a finite problem of a formal language is called in theoretical computer science problem to decide whether the language is finite. A formal language is said to be finite when the set of its “words” is finite, and one then also writes . ${\displaystyle L}$ ${\displaystyle \left|L\right|<\infty }$

For regular and context-free languages the problem of finiteness can be decided . In contrast, it is undecidable for type 1 and type 0 languages ​​of the Chomsky hierarchy .

See also

• Equivalence problem
• Optimization problem
• Cutting problem
• Word problem