Semester
Subject
Year
Tribhuwan University
Institute of Science and Technology
2080
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.
What is NFA? How is it different from DFA? How is NFA to DFA conversion done? Convert the following NFA into DFA.
[10]
2.
How does Turing machine accept a string? Design a Turing Machine over the alphabet {0,1,a} that processes the string defined by L = {a01a,a10a,a0101a}. Show both transition diagram and table. Show acceptance of a0101a.[10]
3.
Define context free grammar with an example. Explain with example, how context free grammar is converted to Chomsky Normal Form.[10]
Section B
Short Answers Questions
Attempt any Eight questions.
[8*5=40]
4.
Define string, substring, empty string, and empty language over alphabet {a,b}. [5]
5.
Design a DFA that accepts single line and multi-line comments of the C-Language. [5]
6.
Write regular expression over {a,b} that represents a. Strings having exactly two a's and at least two b's. b. Strings having an even number of a's and each a followed by at least one b. [5]
7.
Using pumping lemma, prove that the language is not regular.
$L = \{a^i b^j c^k \mid j=i+k\}$ [5]
$L = \{a^i b^j c^k \mid j=i+k\}$
8.
Design a PDA over {x,y} which accepts strings defined by the language Show acceptance of xxyy.
$L = \{x^n y^n xy \mid n \geq 0\}$ [5]
$L = \{x^n y^n xy \mid n \geq 0\}$
9.
Design a Turing machine that computes a function f(n)=0. [5]
10.
How abstract, decision and optimization problems are different from each other? [5]
11.
How is PDA to CFG conversion done? Consider a PDA that accepts by empty stack, Now construct an equivalent CFG.
$P = ((p,q);\{0,1\},\{Z\},\delta,p,Z);$
$\delta(p,0,Z)=(p,0z), \delta(p,0,0)=(p,00), \delta(p,1,0)=(p,\varepsilon), \delta(p,\varepsilon,z)=(q,\varepsilon)$
[5]
$P = ((p,q);\{0,1\},\{Z\},\delta,p,Z);$
$\delta(p,0,Z)=(p,0z), \delta(p,0,0)=(p,00), \delta(p,1,0)=(p,\varepsilon), \delta(p,\varepsilon,z)=(q,\varepsilon)$
12.
What is the meaning of the term 'Context Free' in context free grammar? Justify with a suitable example. What is the need of a parse tree? [5]