Questions
Syllabus
Qns. By Syllabus

Semester

Subject

Year

Tribhuwan University

Institute of Science and Technology

2079

Bachelor Level / Second Year / Fourth Semester / Science

B.Sc in Computer Science and Information Technology (CSC262)

(Theory of Computation)

Full Marks: 60

Pass Marks: 24

Time: 3 Hours

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

The figures in the margin indicate full marks.

Section A

Long Answers Questions

Attempt any TWO questions.
[2*10=20]
1.
Show that, for any NFA $N = (Q, \Sigma, \delta, q_0, F)$ accepting language $L = \Sigma$, there is a DFA $D = (Q', \Sigma', q_0', \delta', F')$ accepting the same language $L$.[10]
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.[10]
3.
Given the following expression grammar for simple arithmetic expression with operator + and *. Remove the left recursion from this grammar then simplify and convert to CNF.

$E \rightarrow E+T \mid T$

$T \rightarrow T+F \mid F$

$F \rightarrow (E) \mid a$
[10]
Section B

Short Answers Questions

Attempt any Eight questions.
[8*5=40]
4.
Explain the $\varepsilon$-closure of states on an $\varepsilon$-NFA with suitable examples. [5]
5.
Convert the following regular expression into equivalent Finite Automata.

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

$b. 1*0(0+1)*1$
[5]
6.
Define the term: Parse Tree, left-most and right-most derivation, sentential form and ambiguity with example. [5]
7.
Give the formal definition of Push Down Automata. How CFG can be converted into equivalent PDA. Explain with an example. [5]
8.
Define regular grammar. Also explain the method of converting right linear grammar into equivalent finite automata. [5]
9.
Construct a Turing machine that accepts the language,

$L = \{a^n b^n \mid n \geq 0\}$
[5]
10.
Define Turing machine and its roles. [5]
11.
Explain about the complexity classes p, NP and NP-Complete. [5]
12.
Write short notes (Any two): a) Big Oh, Big Omega and Big Theta b) Tractable and Intractable Problems c) Chomsky Hierarchy [5]