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

Views: ...
CSC 262-2082 ✡

Tribhuvan University

Institute of Science and Technology

TUpapers.com TUpapers.com
Bachelor Level/Second Year/Fourth Semester/Science
Bachelors in Computer Science and Information Technology (CSC 262)
(Theory Of Computation) <br> <b class='underline'>(Old Course</b>)
Full Marks: 60 Pass Marks: 24 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
Long Answer Questions
Attempt any Two questions.
[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

[8×5=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.