### Exam Year

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.

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.

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

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