Decidablity of Languages of Grammars and Automata

Question

Note this is a question related to study in a CS course at a university, it is NOT homework and can be found here under Fall 2011 exam2.

Here are the two questions I'm looking at from a past exam. They seem to be related, the first:

Let

$\qquad \mathrm{FINITE}_{\mathrm{CFG}} = \{ < \! G \! > \mid G \text{ is a Context Free Grammar with } |\mathcal{L}(G)|<\infty \} $

Prove that $\mathrm{FINITE}_{\mathrm{CFG}}$ is a decidable language.

and...

Let

$\qquad \mathrm{FINITE}_{\mathrm{TM}} = \{ < \! M\!> \mid M \text{ is a Turing Machine with } |\mathcal{L}(M)|<\infty \}$

Prove that $\mathrm{FINITE}_{\mathrm{TM}}$ is an undecidable language.

I am a bit lost on how to tackle these problems, but I have a few insights which I think may be in the right direction. The first thing is that I am aware of is that the language $A_{\mathrm{REX}}$, where

$\qquad A_{\mathrm{REX}} = \{ <\! R, w \!> \mid R \text{ is a regular expression with } w \in\mathcal{L}(R)\}$

is a decidable language (proof is in Michael Sipser's Theory of Computation, pg. 168). The same source also proves that a Context Free Grammar can be converted to a regular expression, and vice versa. Thus $A_{\mathrm{CFG}}$, must also be decidable as it can be converted to a regular expression. This, and the fact that $A_{\mathrm{TM}}$ is un-decidable, seems to be related to this problem.

The only thing I can think of is passing G to Turing machines for $A_{\mathrm{REX}}$ (after converting G to a regular expression) and $A_{\mathrm{TM}}$. Then accepting if G does and rejecting if G doesn't. As $A_{\mathrm{TM}}$ is undecidable, this will never happen. Somehow I feel like I'm making a mistake here, but I'm not sure of what it is. Could someone please lend me a hand here?

Answer 1

1. Convert G to Chomsky Normal form. This way, the only empty derivation would be the start symbol that does not appears anywhere else and thus if there is some production that may able to eventually generate itself, then the grammar is infinite. If no such production exists, each symbol will only be able to generate a finite set of strings, and then the grammar is finite. So, build a directed graph where each production is a node and each symbol inside a production is an edge targeting that symbol. If the graph has some cycle, the CFG is infinite, otherwise it is not. Hence a Turing machine for $FINITE_{CFG}$ could be construct doing exactly that, and then $FINITE_{CFG}$ is decidable.

2. Suppose that $FINITE_{TM}$ is decidable. Lets say that $H$ is a Turing machine that has some string as input and uses itself as an input to $FINITE_{TM}$. If $FINITE_{TM}$ returns true (i.e, $H$ accepts only a finite language), then $H$ accepts the input, which leads to a contradiction since the input set is infinite (the input's length is unbounded, so accept any possible string as input means accepting an infinite set of strings). If $FINITE_{TM}$ returns false (i.e $H$'s language is infinite), then $H$ rejects the input, meaning that $H$'s language is finite because it does not accepts any input (i.e. its language is empty), which leads to a contradiction too. This way, the supposition that $H$ exists leads to contradiction, and this supposition is based in the supposition that $FINITE_{TM}$ is decidable. So, by contradiction, we have that $FINITE_{TM}$ is not decidable.

The same source also proves that a Context Free Grammar can be converted to a regular expression, and vice versa.

I really doubt that Sipser would state that, you probably misread or misunderstood. This would mean that context-free grammars generate exactly the same langauges as right-linear grammars. This is false; the right-linear grammars generate are a proper subset of the languages context-free grammars dp. That said, the way you tried to use regular languages to answer the questions just leads you to nowhere.

As you can see above in my proofs, the two questions are indeed two very distinct, unrelated questions. It just happens that they were worded similarly.

Answer 2

Another way to decide $FINITE_{CFG}$ is via the pumping lemma.

The pumping lemma says that each CFL $L$ has a number $N$ (which can be computed from the grammar, or at least an upper bound of it can easily be computed), such that any $x\in L$ which is longer than $N$ can be "pumped".

This means that if $L$ is finite, all the words in $L$ are shorter than $N$.

Now, all that one needs to check is words with lengths between $N$ and $2N$. If any such word exists, then $L$ is infinite. It is not too difficult to see that this statement is "if and only if", thus if you find no word withing this range, $L$ is finite. The efficiency here is much worse than the answer of Victor, but it teaches something about the structure of CFLs.