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

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

TRIBHUVAN UNIVERSITY

INSTITUTE OF SCIENCE AND TECHNOLOGY

2079 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
    Show that, for any NFA accepting language $L$, there is a DFA $D = (Q, \Sigma, \delta, q_0, F)$ accepting the same language $L$.
  2. 2
    State and prove the pumping lemma for regular languages. How can you show with example the pumping lemma is used to prove that a given language is not regular?
  3. 3
    Given the following expression grammar for simple arithmetic expression with operator $+$ and $*$. [Grammar/image to be added manually]

Group B

Short Answer Questions

Attempt any Eight questions.

  1. 4
    Explain the $\epsilon$-closure of states of an $\epsilon$-NFA with a suitable example.
  2. 5
    Convert the following regular expression into equivalent Finite Automata. a. $(0+1)^*(10(1+0)$ b. $1^*0(0+1)^*1$
  3. 6
    Define the term: Parse Tree, Left-most and right-most derivation, sentential form and ambiguity with example.
  4. 7
    Give the formal definition of Push Down Automata. How CFG can be converted into equivalent PDA? Explain with an example.
  5. 8
    Define regular grammar. Also explain the method of converting right linear grammar into equivalent Finite Automata.
  6. 9
    Construct a Turing Machine that accepts a language [language definition/image to be added manually]
  7. 10
    Define Turing Machine and explain its roles.
  8. 11
    Explain about the complexity classes $P$, $NP$ and $NP\text{-}Complete$.
  9. 12
    Write short notes (Any two): a. Big $O$, Big $\Omega$ and Big $\Theta$ b. Tractable and Intractable Problems c. Chomsky Hierarchy