3
$\begingroup$

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?

  • 4
    In use by whom? For what? Would "English" count?2012-02-25
  • 1
    Does something PSPACE-complete count as useful? Because those certainly can't.2012-02-25
  • 0
    Automated 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

2 Answers 2