Is there a language actually in use that can't be recognized by a linear bounded automaton? I only know of ones that don't have a practical use, like "the set of pairs of equivalent regular expressions with exponentiation" (Wikipedia). Or would any such language be too slow to recognize to be useful?
A language that is not even context-sensitive?
3
$\begingroup$
computer-science
-
4In use by whom? For what? Would "English" count? – 2012-02-25
-
1Does something PSPACE-complete count as useful? Because those certainly can't. – 2012-02-25
-
0Automated proof checkers are computer programs that recognize the language of all valid proofs in some system. I don't think this language can be recognized by a linear bounded automaton, but I don't actually know. – 2012-02-25