Tribhuvan University
Bachelor of Science in Computer Science and Information Technology
Semester 4 · TU Board 2080
Course Title: Theory of Computation (CSC262)
Full Marks: 60Pass Marks: 24Time: 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.
Group A
Attempt any two questions.(2 × 10 = 20)
- 1.10
What is NFA? How is it different from DFA? How is NFA to DFA conversion done? Convert the following NFA into DFA.
[figure in the original paper]
- 2.10
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.
- 3.10
Define context free grammar with an example. Explain with example, how context free grammar is converted to Chomsky Normal Form.
Group B
Attempt any eight questions.(8 × 5 = 40)
- 4.5
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.
- 6.5
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.
- 7.5
Using pumping lemma, prove that the language L = {a^ib^jc^k | j=i+k} is not regular.
- 8.5
Design a PDA over {x,y} which accepts strings defined by the language L = {x^ny^nxy | n>=0}. Show acceptance of xyxy.
- 9.5
Design a Turing machine that computes a function f(n)=0.
- 10.5
How abstract, decision and optimization problems are different from each other?
Answer comingAlso asked in 2082
- 11.5
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.
- 12.5
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?
— The End —