• Submission Guideline: Upload your homework file (hw12_[your student id].doc, hw12_[your student id].hwp or hw12_[your student id].pdf) to online Eruri classroom. You are allowed to write down your answers either in Korean or English at your convenience.
• Deadline : 18:00 PM, Tuesday, December 9

       

Please feel free to leave your questions about homework problems in the online Eruri classroom.

       

1. Determine whether each language is decidable and prove your answer without using Rice’s theorem.

a) $A = \{ \langle M \rangle \mid M$ is a TM and $L(M) = \emptyset \}$.

b) $A = \{ \langle M \rangle \mid$ given a blank input, $M$ uses at most 20 cells of tape $\}$.

c) $A = \{ \langle M \rangle \mid$ $L(M)$ is finite $\}$.

   

2. For each of the following PCP problems, either find a solution or prove that a solution does not exist.

a) (11, 101), (11, 11011), (110, 1)

b) (10, 1), (10, 01), (01, 10), (0, 10)

c) (1110, 1), (1, 0111)

   

3. Let $L$ be the set of (codes for) context-free grammars $G$ such that $L(G)$ contains at least one palindrome. Show that $L$ is undecidable. Hint: Reduce PCP to $L$ by constructing, from each instance of PCP a grammar whose language contains a palindrome if and only if the PCP instance has a solution.