Semester
Subject
Year
Tribhuwan University
Institute of Science and Technology
2081
Bachelor Level / Second Year / Fourth Semester / Science
B.Sc in Computer Science and Information Technology (CSC262)
(Theory of Computation)
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 Answers Questions
Attempt any TWO questions.
[2*10=20]
1.
Mention the transition function of PDA. List the two ways that PDA accepts the string. Convert the following CFG to PDA.
$S \rightarrow AS \mid \varepsilon$
$A \rightarrow Ab \mid Bb \mid ab$[10]
$S \rightarrow AS \mid \varepsilon$
$A \rightarrow Ab \mid Bb \mid ab$
2.
List any two regular operators. Minimize the following finite state machine using Table Filling algorithm.
[10]
3.
Define Turing machine as enumerators of strings of a language. Encode the Turing machine TM = ({q0, q1, q2}, {a, b}, {a, b, B}, δ, q2, B, F) with input w = ba and δ is defined as follows: δ(q0, b) → (q1, b, R), δ(q1, a) → (q2, a, R), δ(q2, a) → (q1, a, R), δ(q2, b) → (q2, b, L)[10]
Section B
Short Answers Questions
Attempt any Eight questions.
[8*5=40]
4.
Does machine always refer to hardware? Justify. Define positive closure and Kleene closure. [5]
5.
What is undecidable problem? Discuss about Post Correspondence Problem. [5]
6.
Define the language of a grammar. For the grammar , show the leftmost derivation for the string 00100 with its parse tree.
$S \rightarrow 0S0 \mid 1 \mid \varepsilon$ [5]
$S \rightarrow 0S0 \mid 1 \mid \varepsilon$
7.
Define $\varepsilon$-closure of a state. Differentiate between Moore and Mealy machine. [5]
8.
Represent the following regular grammar to finite automata.
$S \rightarrow aA \mid aB \mid \varepsilon$
$A \rightarrow aA \mid aS$
$B \rightarrow bB \mid \varepsilon$ [5]
$S \rightarrow aA \mid aB \mid \varepsilon$
$A \rightarrow aA \mid aS$
$B \rightarrow bB \mid \varepsilon$
9.
Design the DFA that accepts binary string ending with '00' and show its extended transition function for the string 111000. [5]
10.
Convert the following grammar to CNF.
$S \rightarrow AAB, \quad A \rightarrow aA \mid \varepsilon, \quad B \rightarrow ab \mid a$ [5]
$S \rightarrow AAB, \quad A \rightarrow aA \mid \varepsilon, \quad B \rightarrow ab \mid a$
11.
For the following Turing Machine, test whether the string “())))” is accepted or rejected and represent it in transition diagram.
$\begin{array}{|c|c|c|c|c|c|c|} \hline \text{State} & X & \text{Action (Write, Move, New State)} & Y & \text{Action (Write, Move, New State)} & B & \text{Action (Write, Move, New State)} \\ \hline q_0 & ( & X,R,q_1 & & , ,q_0 & & , ,q_4 \\ q_1 & ) & X,L,q_2 & & Y,L,q_2 & & Y,L,q_2 \\ q_2 & X & X,R,q_0 & Y & Y,R,q_3 & & ,R,q_4 \\ q_3 & ( & , ,q_3 & & , ,q_3 & & ,R,q_4 \\ \hline \end{array}$
[5]
$\begin{array}{|c|c|c|c|c|c|c|} \hline \text{State} & X & \text{Action (Write, Move, New State)} & Y & \text{Action (Write, Move, New State)} & B & \text{Action (Write, Move, New State)} \\ \hline q_0 & ( & X,R,q_1 & & , ,q_0 & & , ,q_4 \\ q_1 & ) & X,L,q_2 & & Y,L,q_2 & & Y,L,q_2 \\ q_2 & X & X,R,q_0 & Y & Y,R,q_3 & & ,R,q_4 \\ q_3 & ( & , ,q_3 & & , ,q_3 & & ,R,q_4 \\ \hline \end{array}$
12.
Differentiate between Class P and Class NP problem. Mention the transition function of DFA, NFA, and ε-NFA. [5]