### Exam Year

Tribhuvan University

Institute of Science and Technology

2079

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.

Section A

Attempt any TWO questions

1

Show that, For any NFA N=(Q, ∑, δ, q0, F) accepting language L=∑, There is a DFA D= (Q’, ∑’, q0′, δ’, F’) accepting the same language L.

2

State and prove the Pumping Lemma for regular languages. How can you show with example that pumping lemma is used to prove that a given language is not a regular? Explain.

3

Given the following expression grammar for simple arithematic  expression with operator + and *.

E→ E+T  | T

T  → T+F  | F

F → (E)  | a

Remove the left recursion from this grammar then simplify and convert to CNF.

Section B

Attempt any EIGHT questions

4

Explain the ε-closure of states on an ε-NFA with suitable examples.

5

Convert the following regular expression into equivalent Finite Automata

a. (0+1)*10(1+0)

b. 1*0(0+1)*1

6

Define the term: Parse Tree, left-most and right-most derivation, sentential form and ambiguity with example.

7

Give the formal definiton of Push Down Automata. How CFG can be converted into equivalent PDA. Explain with an example.

8

Define regular grammar. Also explain the method of converting right linear grammar into equivalent finite automata.

9

Construct a Turing machine that accepts the language, L = { an bn | n≥0}

10

Define Turing machine and its roles.

11

Explain about the complexity classes p, NP and NP-Complete.

12

Write short notes ( Any two ) :

a) Big Oh, Big Omega and Big Theta

b) Tractable and Intractable Problems

c) Chomsky Hierarchy