CSIT 4th Semester
Theory Of Computation Board Question Paper 2082 Old Course

CSC 262-2082 ✡
Tribhuvan University
Institute of Science and Technology
2082
✡
Bachelor Level/Second Year/Fourth Semester/Science
Computer Science Information Technology (CSC 262)
(Theory Of Computation)
(Old Course)
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 Answer Questions
Attempt any Two question.
[2x10=20]
1.

Differentiate between deterministic PDA and non-deterministic PDA. How do you convert PDA to CFG and CFG to PDA. Illustrate with an example.

2.

Describe about any two variants of Turing machine. How do you encode the Turing machine. Explain.

3.

List the properties of regular language. Show that \(L = \{0^k 1^k \mid k > 0\}\) is not regular language.

Section B

Attempt any Eight questions

[8x5=40]
4.

What is different between Kleen closure and Positive closure? Given the alphabet \(A = \{a, b\}\), find \(A^1\) and \(A^2\).

5.

State cooks theorem. Define halting and undecidable problem

6.

Design a Turing Machine that accepts palindrome binary strings.

7.

Show that for any NFA N, there is a DFA D such that L(N) = L(D).

8.

Construct a DFA that accepts binary string start with 0 and show the acceptance of the string 0101.

9.

Define language of a grammar. Discuss about parse tree.

10.

Explain the Chomsky Hierarchy.

11.

Define NFA. What is the purpose of stack in PDA?

12.

What is ambiguous grammar? Discuss about BNF.