Name: _______________________________, ___________________________________ (Last name) (First name)
Student ID#: __________________________________
Section: E
Instructor: Ali Mahmoodi
York University
Department of Electrical Engineering & Computer Science Lassonde School of Engineering
EECS 2001 E Quiz 3 (Version A) July 26, 2019
Guidelines and Instructions:
1. This is a 50-minute, closed-book test.
2. This exam paper has 4 pages (including this page) and 5 questions.
3. Print your name and write down your student number clearly.
4. If you need more space to write your answer use the back of the pages but clearly indicate which question you are answering.
5. You may not leave within the first and last 10 minutes of the exam. Remain seated until all exams are collected.
Question 1
/4
Question 2
/2
Question 3
/4
Question 4
/6
Question 5
/4
Total
/20
EECS 2001 Quiz 3 – Summer 2019 Section E
Question 1. [4 marks]
a) [2] Explain what is a recursively enumerable language and how it differs from a
recursive language.
Answer: A recursively enumerable language (or Turing-recognizable) is a language that is recognized by some Turing machine. A recursive language (or Turing-decidable) is a language that is decided by a Turing machine. (1 mark) In the latter case the TM that recognizes the language always halts either in an accept state or a reject state. In the case of Turing-recognizable the machine may go into infinite loop on strings not in the language. (1 mark)
b) [2] Provide an example of a language that is recursively enumerable but not recursive. Briefly explain your answer.
Answer:Thelanguage𝐴𝑇𝑀 = {<𝑀,𝑤> |𝑀𝑖𝑠𝑎𝑇𝑀𝑎𝑛𝑑𝑀𝑎𝑐𝑐𝑒𝑝𝑡𝑠𝑤}isrecursively enumerable since there is a TM that recognizes it (1 mark). However the language is proven to be undecidable. (1 mark)
Equality of CFGs is co-Turing recognizable (means its complement is Turing recognizable). Only 1 mark for this example.
Hilbert’s 10th Problem deserves full mark if proper justification is given (i.e. “one can arrange all possible tuples of values of the unknowns in a sequence and then, for a given value of the parameter(s), test these tuples, one after another, to see whether they are solutions of the corresponding equation.” Wikipedia)
Page 2 of 4
EECS 2001 Quiz 3 – Summer 2019 Section E
Question 2. [2 marks] Given the following TM, M2, state what each of the following configurations yield (i.e. what is the next configuration when you run M2 starting from the given configuration).
Answer: See Sipser (3rd Ed) Page 172
Page 3 of 4
EECS 2001 Quiz 3 – Summer 2019 Section E
Question 3. [4 marks] Describe how a single tape deterministic Turing machine simulates a k-tape deterministic Turing machine.
Answer: See slides or Sipser, 3rd Edition, Theorem 3.13.
Question 4. [6 marks] Give an implementation level description of a deterministic Turing machine that decides the following language. Note that you do not need to give state diagram, but need to describe how the Turing machine behaves.
{𝑎𝑖𝑏𝑗𝑐𝑘 |𝑖×𝑗 = 𝑘𝑎𝑛𝑑𝑖,𝑗,𝑘 ≥ 1}
Answer: See Sipser (3rd Ed) Example 3.11.
Question 5. [4 marks] Is the set ECFG = { G | G is a CFG with L(G)= } decidable?
Justify your answer by giving a high level proof.
Answer: See slides and Sipser 3rd Edition (Theorem 4.8).
Page 4 of 4