TOC Question Bank 2078 - With Solution

Tribhuvan University

Institute of Science and Technology

2078

Bachelor Level / fourth-semester / Science

Computer Science and Information Technology (CSC257)

Theory of Computation

Full Marks: 60 + 20 + 20

Pass Marks: 24 + 8 + 8

Time: 3 Hours

Candidates are required to give their answers in their own words as far as practicable.

The figures in the margin indicate full marks.

Long Answer Questions

Attempt any two Questions (2 x 10 = 20)

1. Give the formal definition of DFA and NFA. How can NFA be converted into equivalent DFA? Explain with a suitable example.

2. Find the minimum state DFA for the given DFA below:

   States	Input 0	Input 1
   A	B	F
   B	E	C
   C	B	D
   *D	E	F
   E	B	C
   F	B	A

3. Construct a Turing Machine that accepts the language of odd-length strings over the alphabet {a, b}. Give the complete encoding for this TM as well as its input string w = abb in the binary alphabet that is recognized by the Universal Turing Machine.

Short Answer Questions

Attempt any Eight Questions

1. Define the term alphabet, prefix and suffix of string, concatenation and Kleen closure with example.

2. Give the regular expressions for the following language over alphabet {a, b}.

   • Set of all strings with a substring bab or abb.
   • Set of all strings whose 3rd symbol is ‘a’ and 5th symbol is ‘b’.

3. Show that L = { an | n is a prime number } is not a regular language.

4. Explain about Chomsky’s Hierarchy about the language and programs.

5. Define a Push Down Automata. Construct a PDA that accepts L = {anbn | n > 0}

6. Construct the following grammar into Chomsky Normal Form.

   • S → abSb | a | aAb
   • A → bS | aAAb | ε

7. Define Turing Machine and explain its different variations.

8. What do you mean by computational Complexity? Explain about the time and space complexity of a Turing machine.

9. Explain the term Intractability. Is the SAT problem intractable? Justify.