- Submission Guideline: Upload your homework file (
hw4_[your student id].doc
orhw4_[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.
- Show the ID’s of the Turing machine of Fig. 8.9 if the input tape contains:
a) $00$.
b) $000111$.
c) $00111$.
- 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$\}$.
- 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)$.
- 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 $\}$.
- 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)
- 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.