CSIT 4th Semester
Theory Of Computation Board Question Paper 2082

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)
(New 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.

List the application of Pumping Lemma. Minimize the following DFA using Table Filling Algorithm.
DFA diagram for minimization

2.

Define yield in parse tree with example. Convert the following grammar to CNF
\(A \rightarrow ASB \mid \epsilon\)
\(A \rightarrow 0AS \mid 0\)
\(B \rightarrow S \mid S \mid A \mid 1 \mid 1\)
\(S \rightarrow \epsilon\)

3.

Distinguish between multi - tape and multi - track Turing Machine. Design a TM that accepts a string over alphabet \(\Sigma = \{a, b\}\), such that \(L = \{a^n b^n \mid n > 0\}\).

Section B

Attempt any Eight questions

[8x5=40]
4.

Why do we need asymptotic notation? Discuss about alphabet and power of alphabet.

5.

Define ambiguous grammar. How do you use parse tree to show the ambiguity of a grammar?

6.

Given the non-deterministic Turing machine, \(TM: (\{q_0, q_1, q_2, q_3\}, \{0, 1\}, \{0, 1, B\}, \delta, q_0, B, \{q_3\})\) with the following transition rules, describe the language accepted by given Turing machine.
\(\delta(q_0, 0) = \{(q_0, 1, R), (q_1, 1, R)\}\); \(\delta(q_1, 1) = \{q_2, 0, L\}\); \(\delta(q_2, 1) = \{q_0, 1, R\}\); \(\delta(q_1, B) = \{q_3, B, R\}\)

7.

Given two DFAs \(M_1\) and \(M_2\) over the same alphabet \(\Sigma\), design a third DFA \(M_3\) such that \(M_3\) will accept the string \(w \in \Sigma^*\) if it is accepted by both \(M_1\) and \(M_2\).

8.

Differentiate between Moore and Mealy machines.

9.

Design a DFA that accepts the odd length of binary strings

10.

How do you convert CFG to PDA? Explain.

11.

Why do we need \(\epsilon\) transition? Give the formal definition of PDA.

12.

Describe about abstract, decision and optimization problems.