# context sensitive language finite or infinite

let L be a CSL. (my understanding/ memory/ expectation is) the problem

is L finite or infinite?

is undecidable.

• are there any cases in the literature of analyzing a CSL L in some "limited context" and determining whether it is finite or infinite? (also wondering about machine learning contexts.)

(brief background: the question can arise in analysis/ application of automated theorem proving. one might reduce a theorem "there exist an infinite x" to a CSL L which enumerates x and the question of whether L is finite or infinite.)

• 1) How is $L$ given? 2) The proof is probably not too hard; something like this should work. 3) I don't understand the question in the second bullet. What is "limited context"?
– Raphael
Apr 5 '16 at 16:45
• (1) L can be specified in any CSL format eg CSG etc. (2) ML or heuristics are sometimes used to attack undecidable problems and get "limited solutions" ie sometimes solutions are found in limited contexts. one near-classic example is the busy beaver problem etc. can give more bkg in Computer Science Chat for anyone interested
– vzn
Apr 5 '16 at 16:53
• 1. One question per post, please. 2. When folks ask for clarification, please edit the post to incorporate all relevant information. People shouldn't have to read the comments to understand what you are asking. I still don't understand what you mean by "limited context". Are you asking for an algorithm that doesn't always terminate, but when it does terminate, its answer is always correct? (There is a trivial such algorithm: always enter an infinite loop.) Are you asking for a class of languages, contained in CSL but containing CFL, for finiteness is decidable?
– D.W.
Apr 6 '16 at 5:36

From this, we can prove that it's undecidable whether a context-sensitive grammar is finite or infinite. Let $L$ be a context-sensitive language. By the standard closure properties for CSL's, if $L$ is context-sensitive, then so is $L^+$. Now if $L$ is empty, then $L^+$ is empty (and thus finite); but if $L$ is non-empty, then $L^+$ is infinite. Consequently, if it were decidable to check whether a CSL is finite or infinite, we could apply that decider to $L^+$ and learn whether $L$ was empty or not -- but the theorem mentioned above implies this is impossible.