Theory of Computation (CSC262) 2081 BS Past Questions & Solutions

Tribhuvan University (TU) 2081 BS board exam question paper with verified step-by-step solutions for BSc CSIT Fourth Semester.

TRIBHUVAN UNIVERSITY

INSTITUTE OF SCIENCE AND TECHNOLOGY

2081 B.S.

Bachelor Level: B.Sc. CSIT

Semester: Fourth Semester

Subject: Theory of Computation (CSC262)

Full Marks: 60 / 80

Pass Marks: 24 / 32

Candidates are required to give their answers in their own words as far as practicable.

Group A

Long Answer Questions

Attempt any Two questions.

  1. 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 \epsilon$ $B \rightarrow aAb \mid Bb \mid ab$
  2. 2
    List any two regular operators. Minimize the following finite state machine using Table Filling algorithm. [Finite state machine diagram/image to be added manually]
    Theory of Computation 2081 Question 2
  3. 3
    Define Turing machine as enumerators of strings of a language. Encode the Turing machine $TM = (\{q_0, q_1, q_2\}, \{a, b\}, \{a, b, B\}, \delta, q_0, B, F)$, with input $w = ba$ and $\delta$ is defined as follows. $\delta(q_0, b) = (q_2, a, R)$, $\delta(q_2, a) = (q_1, b, R)$, $\delta(q_2, b) = (q_1, a, R)$, $\delta(q_2, B) = (q_2, b, L)$

Group B

Short Answer Questions

Attempt any Eight questions.

  1. 4
    Does machine always refer to hardware? Justify. Define positive closure and kleene closure.
  2. 5
    What is undecidable problem? Discuss about Post's Correspondence Problem.
  3. 6
    Define the language of a grammar. For the grammar $S \rightarrow 0S0 \mid 0 \mid 1 \mid \epsilon$, show the leftmost derivation for the string $00100$ with its parse tree.
  4. 7
    Define $\epsilon$-closure of a state. Differentiate between Moore and Mealy machine.
  5. 8
    Represent the following regular grammar to finite automata. $S \rightarrow a \mid aA \mid bB \mid \epsilon$ $A \rightarrow aA \mid aS$ $B \rightarrow bS \mid \epsilon$
  6. 9
    Design the DFA that accepts binary string ending with "$00$" and show its extended transition function for the string $111000$.
  7. 10
    Convert the following grammar to CNF. $S \rightarrow AAB$, $A \rightarrow aAb \mid \epsilon$, $B \rightarrow aB \mid a$
  8. 11
    For the following Turing Machine, test whether the string "$())($" is accepted or rejected and represent it in transition diagram.
    Theory of Computation 2081 Question 11
  9. 12
    Differentiate between Class $P$ and Class $NP$ problem. Mention the transition function of DFA, NFA and $\epsilon$-NFA.