Semester
Subject
Year
B.Sc Computer Science and Information Technology
Institute of Science and Technology, TU
Theory of Computation (CSC262)
Year Asked: 2081, syllabus wise question
Basic Foundations
1.
Does machine always refer to hardware? Justify. Define positive closure and Kleene closure. [5]
2.
Define $\varepsilon$-closure of a state. Differentiate between Moore and Mealy machine. [5]
Context Free Grammar
1.
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$
2.
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$
Introduction to Finite Automata
1.
Design the DFA that accepts binary string ending with '00' and show its extended transition function for the string 111000. [5]
Push Down Automata
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$
Regular Expressions
1.
List any two regular operators. Minimize the following finite state machine using Table Filling algorithm.
[10]
2.
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$
Turing Machines
1.
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]
2.
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}$
Undecidability and Intractability
1.
What is undecidable problem? Discuss about Post Correspondence Problem. [5]
2.
Differentiate between Class P and Class NP problem. Mention the transition function of DFA, NFA, and ε-NFA. [5]