Tribhuvan University
Institute of Science and Technology
2080
Bachelor Level / fourth-semester / Science
Computer Science and Information Technology (CSC257)
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.
- Hamro CSIT
-
How does a 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 the transition diagram and table. Show acceptance of a0101a.
-
Define context-free grammar with an example. Explain with an 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 the alphabet {a,b}.
-
Design a DFA that accepts single-line and multi-line comments of the C-Language.
-
Write a regular expression over {a,b} that represents
- Strings having exactly two a’s and at least two b’s.
- 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 an 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 the context-free grammar? Justify with a suitable example. What is the need for a parse tree?