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.

1

What is NFA? How is it different from DFA? How is NFA to DFA conversion done? Convert the following NFA into DFA.

- Hamro CSIT

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.

3

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.

4

Define string, substring, empty string, and empty language over alphabet {a,b}.

5

Design a DFA that accepts single line and multi-line comments of the C-Language.

6

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

Using pumping lemma, prove that the language L = {aibjck | j=i+k} is not regular.

8

Design a PDA over {x,y} which accepts strings defined by the language L = {xnynxy | n>=0}. Show acceptance of xyxy.

9

Design a Turing machine that computes a function f(n)=0.

10

How abstract, decision and optimization problems are different from each other?

11

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

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?