retagged by
1,300 views
5 votes
5 votes
Which of the following is not a recursive language?

a. Regular language

b. {$\langle M,w \rangle$ | $M$ is a DFA that accepts $w$}

c. {$\langle M \rangle$ | $M$ is a TM and there exists an input which halts within $100$ steps}

d. {$\langle M \rangle$ | $M$ is a TM and $L(M)$ is regular }
retagged by

1 Answer

Best answer
7 votes
7 votes

Option A) Every Regular Language is decidable.

Option B) We are given a DFA and asked to determine if a word $w$ belongs to it. Simulate and see if the word $w$ goes to a final state- always decidable. (Same works for PDA, LBA and even always halting TMs)

Option C) Give an input to TM and if the input is accepted by TM in 100 steps then it will say "yes" else "no". But there is a catch here- we are not given the input and there are infinite possible inputs. But, in 100 steps a TM cannot process more than 100 length of the input. So, we can simulate the given TM for 100 steps for all possible strings of length 100 (this number is finite) and decide our problem. 

Option D) $L(T_{yes}) = \Sigma^*$ and $L(T_{no}) = \{a^nb^n \mid n > 0\}$. So, this is a non-trivial property of LANGUAGE OF TM, and hence according to Rice's First Theorem, it is undecidable. Source : http://gatecse.in/wiki/Rice%27s_Theorem_with_Examples

Option D is actually non-even semi decidable and for this we can take $L(T_{yes}) = \phi$ and $L(T_{no}) =\{a^nb^n \mid n > 0\}$, making $L(T_{yes}) \subset L(T_{no})$. 

More problems: http://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf

Related questions