1
$\begingroup$

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

is L finite or infinite?

is undecidable.

  • where was this 1st proved/ published?

  • 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.)

Improve this question
$\endgroup$
3
  • $\begingroup$ 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"? $\endgroup$
    – Raphael ♦
    Apr 5, 2016 at 16:45
  • $\begingroup$ (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 $\endgroup$
    – vzn
    Apr 5, 2016 at 16:53
  • $\begingroup$ 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? $\endgroup$
    – D.W. ♦
    Apr 6, 2016 at 5:36

1 Answer 1

Reset to default
4
$\begingroup$

It's a standard theorem that it's undecidable whether a given context-sensitive grammar generates the empty language or not.

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.

Therefore, determining whether a given context-sensitive grammar generates a finite or infinite language is undecidable.

Footnote: You can find a proof of the standard theorem above in many places; e.g., these lecture notes from CS 373 at U Illinois. The result is also mentioned in passing on Wikipedia, which cites Hopcroft and Ullman -- a standard resource on formal languages. The same Wikipedia article also mentions some smaller classes of languages that are contained in CSL.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.