16
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ "a Context Free Grammar can be converted to a regular expression, and vice versa" That's not true (unless you interpret it as "there exists a CFG that can be converted to a regular expression", but I don't think that's what you meant). Regular grammars can be converted to regular expressions. There is no algorithm to convert CFGs into regular expressions for the simple reason that most context free languages (i.e. all context free languages that aren't also regular languages) can't be described using a regular expression. $\endgroup$ – sepp2k Mar 21 '12 at 20:21
9
$\begingroup$
  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.

$\endgroup$
  • 1
    $\begingroup$ I'm having some problem following proof two . OK so you pass H to G, yes? If G returns true than H is finite, that makes sense. However, I don't get the input set being infinite, what is the input you are referrng to? $\endgroup$ – BrotherJack Mar 21 '12 at 21:18
  • 1
    $\begingroup$ @BrotherJack The $H$'s input might be of any length, its length is unbounded. It could be a string with just one symbol or it could be a million terabyte long input. This way, the possible inputs for $H$ are an infinite set because we can make it arbitrarily large. $\endgroup$ – Victor Stafusa Mar 21 '12 at 21:22
  • 1
    $\begingroup$ OK. That seems to make sense. Would it be accurate to refer to that input as "any possible string within the input language H"? $\endgroup$ – BrotherJack Mar 21 '12 at 21:28
  • 1
    $\begingroup$ @BrotherJack - I edited the answer to make that point clearer. $\endgroup$ – Victor Stafusa Mar 21 '12 at 21:29
  • 1
    $\begingroup$ Excellent explaination! Thank you very much for your time. $\endgroup$ – BrotherJack Mar 21 '12 at 21:38
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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