Winter 2020 Midterm Test CSCC63HS
Duration: 110 minutes
Aids Allowed: NONE
Student Number:
Last (Family) Name:
First (Given) Name(s):
Do not turn this page until you have received the signal to start.
(In the meantime, please fill out the identification section above,
and read the instructions below carefully.)
This term test consists of 6 questions on 7 pages (including this
one), When you receive the signal to start, please make sure that
your copy of the test is complete.
Answer each question directly on the test paper, in the space pro-
vided, and use the reverse side of the last page for rough work. If
you need more space for one of your solutions, use the reverse side of
the final page and indicate clearly the part of your work that should
be marked.
General Hints: We were careful to leave ample space on the
test paper to answer each question. Note that the exam is worth 60
marks, so if you average more than 2min per mark, you may run out
of time.
Marking Guide
# 1: /10
# 2: /10
# 3: /10
# 4: /10
# 5: /10
# 6: /10
TOTAL: /60
Good Luck!
Total Pages = 7 Page 1 over. . .
Winter 2020 Midterm Test CSCC63HS
Question 1. [10 marks]
Consider the following Turing machine:
q0start q1 q2
q3q4q5 q6
qaccept
$ → R
xy→ R
1 → x, R xy→ R
1→
L
1,y,z → L
x → z, R $ → R
y,z → R
1 → y, R
y,z → R
1 → y, R
y → R
z → x, R
1 →
x, R
If this machine is run on the input $1111$, its first configuration will be q0$1111$. What will the remaining
configurations be? Fill in the chart below.
C1: $q1 1111 $ xy C5: C9: $q3 z y y 1 $ xy C13:
C2: C6: C10: C14: $xy y q6 1 $ xy
C3: C7: C11: $q6 z y y 1 $ xy C15:
C4: $ z q4 111 $ xy C8: $ z q3 y y 1 $ xy C12: C16:
Student #: Page 2 of 7 over. . .
Winter 2020 Midterm Test CSCC63HS
Question 2. [10 marks]
Suppose that you have three languages: A, B, and C. You know that A 6m B and B 6m C
Prove that A 6m C.
Student #: Page 3 of 7 over. . .
Winter 2020 Midterm Test CSCC63HS
Question 3. [10 marks]
Consider the language L3:
L3 =
{
〈M〉
∣∣∣∣ M is a TM, and if M accepts any string,then M loops on some (other) string with the same length
}
.
Prove that L3 is co-recognizable.
Student #: Page 4 of 7 over. . .
Winter 2020 Midterm Test CSCC63HS
Question 4. [10 marks]
Consider the language L4:
L4 =
{
〈M,N〉
∣∣∣∣ There exists some input w such thatM accepts w, N loops on w, or both
}
.
Is L4 recognizable? Prove your answer.
Student #: Page 5 of 7 over. . .
Winter 2020 Midterm Test CSCC63HS
Question 5. [10 marks]
Consider the language L4 from the previous question:
L4 =
{
〈M,N〉
∣∣∣∣ There exists some input w such thatM accepts w, N loops on w, or both
}
.
Is L4 co-recognizable? Prove your answer.
Student #: Page 6 of 7 over. . .
Winter 2020 Midterm Test CSCC63HS
Question 6. [10 marks]
Consider the language L6:
L6 =
{
〈M〉
∣∣∣∣ ∃ a TM N such that for all inputs w,N loops on w iff M accepts w
}
.
Prove that L6 is not recognizable.
Student #: Page 7 of 7 End of Test

欢迎咨询51作业君