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

CSC 262-2081 ✡
Tribhuvan University
Institute of Science and Technology
2081
✡
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.

Define regular expression with its operators. How do you convert DFA to regular expression? Explain with an example.

2.

What is finite state machine? Convert the following NFA to DFA, where \(q_0\) is starting state.
NFA diagram for conversion to DFA

3.

Design a PDA that accepts palindrome string over alphabet \(\{a, b\}\), and convert it into CFG.

Section B

Attempt any Eight questions

[8x5=40]
4.

Define alphabet, string and substring.

5.

When a grammar is said to be ambiguous? Remove the left recursion from the following grammar.
\(A \rightarrow A0 \mid 1A \mid 00 \mid 11 \mid 01\)

6.

Define halting problem. Discuss about satisfiability problem with an example.

7.

Write the formal definition of Turing machine and define it as subroutine.

8.

What is counter machine? Differentiate between Turing machine and universal Turing machine.

9.

Find out whether the language \(L = \{x^n y^n z^n \mid n > 1\}\) is context free or not using Pumping lemma.

10.

Prove that every multi-tape Turing machine has an equivalent single-tape Turing machine.

11.

Convert the following grammar to GNF.
\(S \rightarrow ABCD \mid aD\), \(D \rightarrow BD \mid \epsilon\), \(A \rightarrow 0\), \(C \rightarrow 1\)

12.

Define abstract and optimization problem. Discuss about Moore machine.