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

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

TRIBHUVAN UNIVERSITY

INSTITUTE OF SCIENCE AND TECHNOLOGY

2080 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
    Describe the extended transition function of NFA. Construct a NFA, using transition table and transition diagram, over $\Sigma = \{0, 1\}$ that accepts the strings having substring $01$ and ends with $1$. Show the acceptance of $0111$.
  2. 2
    Define CFG. Construct a CFG that generates the language of all palindromes over $\Sigma = \{a, b\}$ that do not contain the substring $aa$. Show the leftmost derivation and construct the equivalent parse tree for string $babbbab$.
  3. 3
    How Turing Machine is used as a computing function? Construct a TM for simulating a function $f(x) = 2x$ for $x = \{1\}$. Iterate the TM for input $11$ and generate the output $1111$.

Group B

Short Answer Questions

Attempt any Eight questions.

  1. 4
    Differentiate Kleen closure from Positive closure. Compute Positive and Kleen closure of $\{ab\}$.
  2. 5
    Design a Mealy machine over $\Sigma = \{a, b\}$ that generates output 'A' if the input string ends with $aa$ else output 'B' if the string ends with $bb$.
  3. 6
    Construct regular expression over $\{1, \ldots, 9\}$ that represents: a. strings of even numbers with length $4$ starting with $2$ and ending with $8$ b. strings starting with odd numbers and ending with even numbers
  4. 7
    Prove that the language $L = \{a^n b^n c^n \mid n \geq 0\}$ is not context free.
  5. 8
    Construct a PDA that accepts strings over $\Sigma = \{a, b\}$ that contains equal number of $a$'s followed by equal number of $b$'s. Show acceptance of $aabb$ and $aab$.
  6. 9
    Describe how multi-stack TM is different from the semi-infinite tape TM?
  7. 10
    What is intractability? Define time and space complexity of Turing Machine.
  8. 11
    How conversion of PDA to CFG is done? Illustrate with an example.
  9. 12
    State Arden's theorem. Convert following DFA into its regular expression using Arden theorem.
    Theory of Computation 2080 Question 12