Note this is a question related to study in a CS course at a university, it is N

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

FINITECFG={<G>?G is a Context Free Grammar with |L(G)|<?}

Prove that FINITECFG is a decidable language.

and...

Let

FINITETM={<M>?M is a Turing Machine with |L(M)|<?}

Prove that FINITETM 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 AREX, where

AREX={<R,w>?R is a regular expression with w?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 ACFG, must also be decidable as it can be converted to a regular expression. This, and the fact that ATM is un-decidable, seems to be related to this problem.

The only thing I can think of is passing G to Turing machines for AREX (after converting G to a regular expression) and ATM. Then accepting if G does and rejecting if G doesn't. As ATM 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?

Explanation / Answer

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 FINITECFG could be construct doing exactly that, and then FINITECFG is decidable.

Suppose that FINITETM is decidable. Lets say that H is a Turing machine that has some string as input and uses itself as an input to FINITETM. If FINITETM 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 FINITETM 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 FINITETM is decidable. So, by contradiction, we have that FINITETM 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.

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.