• Submission Guideline: Upload your homework file (hw11_[your student id].doc, hw11_[your student id].hwp or hw11_[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, Friday, December 2

       

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

       

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

a) $00$.

b) $000111$.

c) $00111$.

   

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

   

3. 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)$.