Tribhuvan University

Institute of Science and Technology

2078

Bachelor Level / fourth-semester / Science

Computer Science and Information Technology( CSC262 )

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 NFA can be converted into eqivalent DFA? Explain with suitable example.

2

Find the minimum state DFA for the given DFA below:

 States Input 0 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 alphabet {a, b}. Give the complete encoding for this TM as well as its input string w = abb in binary alphabet that is recognized by Universal Turing Machine.

Short Answer Questions

Attempt any Eight Questions

4

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

5

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

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

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

7

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

8

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

9

Construct the following grammer into Chomsky Normal Form.

S → abSb | a | aAb

A → bS | aAAb | ε

10

Define Turing Machine and explain its different variations.

11

Whar do you mean by computational Complexity? Explian about the time and space complexity of a Turing machine.

12

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