Theory of Computation Homework 4

   

  • Submission Guideline: Upload your homework file (hw4_[your student id].doc or hw4_[your student id].hwp) to online Uclass classroom. You are allowed to write down your answers either in Korean or English at your convenience.
  • Deadline: 23:59 PM, Friday, June 21

       

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

   

8.9

  1. Show the ID’s of the Turing machine of Fig. 8.9 if the input tape contains:

a) $00$.

b) $000111$.

c) $00111$.

   

  1. Design Turing machines for the following languages:

a) The set of strings with an equal number of $0$’s and $1$’s.

b) ${\{a^nb^nc^n \mid n\ge 1}\}$.

c) $\{ww^R \mid w$ is any string of $0$’s and $1$’s$\}$.

   

  1. Consider the Turing machine

$M=({\{q_0,q_1,q_2,q_f}\},{\{0,1}\},{\{0,1,B}\},\delta,q_0,B,{\{q_f}\})$

Informally but clearly describe the language $L(M)$ if $\delta$ consists of the following sets of rules:

a) $\delta(q_0,0) = (q_1,1,R); \delta(q_1,1) = (q_0,0,R); \delta(q_1,B)=(q_f,B,R)$.

b) $\delta(q_0,0) = (q_0,B,R); \delta(q_0,1) = (q_1,B,R); \delta(q_1,1)=(q_1,B,R); \delta(q_1,B) = (q_f,B,R)$.

c) $\delta(q_0,0) = (q_1,1,R); \delta(q_1,1) = (q_2,0,L); \delta(q_2,1)=(q_0,1,R); \delta(q_1,B) = (q_f,B,R)$.

  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 $\}$.

   

  1. 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)

   

  1. 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.