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,Σ,δ,q0,F)N = (Q, \Sigma, \delta, q_0, F) accepting language L=ΣL = \Sigma, there is a DFA D=(Q′,Σ′,q0′,δ′,F′)D = (Q', \Sigma', q_0', \delta', F') accepting the same language LL. [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→E+T∣TE \rightarrow E+T \mid T
T→T+F∣FT \rightarrow T+F \mid F
F→(E)∣aF \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)a. (0+1)*10(1+0)
b.1∗0(0+1)∗1b. 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={anbn∣n≥0}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]