Scribd
Upload
52 views3 pages

Us College: Department of Computer Science

This document is a midterm exam for a complexity theory course in computer science. It is divided into three parts testing different concepts: Part I contains 5 multiple choice questions testing topics like unsolvable problems, components of a Turing machine, and properties of recursively enumerable languages. Part II contains 5 true/false statements testing closures of language classes under operations and properties of Turing machines and languages. Part III requires short explanations of concepts like Turing machines, recursively enumerable languages, decidability, applications of Turing machines, and unsolvable problems.

Uploaded by

Dawit Bassa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
52 views3 pages

Us College: Department of Computer Science

This document is a midterm exam for a complexity theory course in computer science. It is divided into three parts testing different concepts: Part I contains 5 multiple choice questions testing topics like unsolvable problems, components of a Turing machine, and properties of recursively enumerable languages. Part II contains 5 true/false statements testing closures of language classes under operations and properties of Turing machines and languages. Part III requires short explanations of concepts like Turing machines, recursively enumerable languages, decidability, applications of Turing machines, and unsolvable problems.

Uploaded by

Dawit Bassa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

US COLLEGE

Department of Computer Science

mid Exam for computer science

Course: complexity theory

Prepared by: Bereket B. Max Weight: 30 % Allowed Time: 1:20 hr.

Name: - _________________________________ID___________

Department ______________________

Year______________________

General Direction

 Switch of your mobile


 Read the instructions carefully
 Any kind of Cheating activity will nullify your result
 Don’t forget to write your Name and ID number
 Check the exam booklet have 4 pages including the cover page

For instructor only

PART I PART II PART III TOTAL

Part I: choose the correct answer from the given alternatives (2pts each)
1. Which of the problems are unsolvable?
a) Halting problem
b) Boolean Satisfiability problem
c) Both (a) and (b)
d) None of the mentioned
2.  Which of the following a Turing machine does not consist of?
a) input tape
b) head
c) state register
d) none of the mentioned
3. The value of n if Turing machine is defined using n-tuples:
a) 6
b) 7
c) 8
d) 5
4. If d is not defined on the current state and the current tape symbol,
then the machine ______
a) does not halts
b) halts
c) goes into loop forever
d) none of the mentioned

5.If L and L’ are recursively enumerable then L is:

a. regular

b. context free

c. context sensitive

d. recursive

Part II: Write true if the statement is correct otherwise write false (2pts each)
1. For every non-deterministic Turing machine, there exists an equivalent deterministic
Turing machine.

2. Turing recognizable languages are closed under union and complementation.


3. Turing decidable languages are closed under intersection and complementation.
4. Turing recognizable languages are closed under union and intersection.
5. Recursive languages are closed under complement.

Part III: Explain (2pts each)

1. Turing machine
2. Recursive and recursively enumerable language
3. Decidability and undecidability
4. Application of Turing machine
5. Unsolvable problems

ANSWER SHEET

PART I PART II
1. 1.
2. 2.
3. 3.
4. 4.
5. 5.

You might also like