Tribhuvan University
Institute of Science and Technology
2080
Bachelor Level / fourth-semester / Science
Computer Science and Information Technology( CSC262 )
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.
What is NFA? How is it different from DFA? How is NFA to DFA conversion done? Convert the following NFA into DFA.
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.
Define context free grammar with an example. Explain with example, how context free grammar is converted to Chomsky Normal Form.
Section B
Attempt any eight questions.
Define string, substring, empty string, and empty language over alphabet {a,b}.
Design a DFA that accepts single line and multi-line comments of the C-Language.
Write regular expression over {a,b} that represents
a. Strings having exactly two a’s and atleast two b’s.
b. Strings having an even number of a’s and each a followed by at least one b.
Using pumping lemma, prove that the language L = {aibjck | j=i+k} is not regular.
Design a PDA over {x,y} which accepts strings defined by the language L = {xnynxy | n>=0}. Show acceptance of xyxy.
Design a Turing machine that computes a function f(n)=0.
How abstract, decision and optimization problems are different from each other?
How is PDA to CFG conversion done? Consider a PDA that accepts by empty stack, P=({p,q},{0,1},{Z},δ,p,z); with δ defined as
δ(p,0,z)=(p,0z), δ(p,0,0)=(p,00), δ(p,1,0)=(p,ε), δ(p,ε,z)=(q,ε),
Now construct an equivalent CFG.
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?