Theory of Computation (TOC) BSc CSIT 2074 Question Paper

Tribhuvan University
Institute of Science and Technology

Bachelor Level/Second Year/ Fourth Semester/ Science            Full Marks: 80
Computer Science and Information Technology (CSc.251)        Pass Marks: 32
(Thoery of Computation)                          Time: 3 hours

Candidates are required to give their answers in their own words as far as possible.
The figures in the margin indicate full marks.

Attempt all the questions.
Group A     [8x4=32]

1. Convert the NFA-ε into NFA without ε.
   



2. Find the regular expressions describing the following languages over alphabet {0, 1}^*.
   (a) The language of all strings containing atleast two 0's.
   (b) The language of all strings containing both 00 and 010 as substrings.


3. Construct FA recognizing the languages described by following regular expressions.
   (a) (10^* + 01^*)11^*
   (b) (0 + 1)^*(01+1000)0^*
   


4. What do you mean by a CFG in CNF? What are the criteria to be a CFG in CNF? Explain.


5. Define the term Regular Grammar. What is the relation of Regular Grammar with other grammars? Explain


6. Define the universal Turing machine and describe its role.


7. Show that the complement of a recursive language is recursive.


8. Explain, how can you encode a Turing machine into universal language.

Group B    [6x8=48]

1. Describe the extended transition function of a NFA. Construct a NFA accepting the language over {a, b}^* with each strings containing three consecutive b's. Show by extended function that it accepts abbb.


2. Define the term immediate left recursion. How can you convert a grammar with immediate left recursion into equivalent grammar without left recursion? Remove left recursion from the following grammar.
   S -> S₁S
   S₁ -> S₁ + T| T
   T -> T^*F| F
   F -> (S₁)| a


3. Contruct a PDA that accepts the strings of language L ={ww^R| w is in {a,b}^*}.


4. Describe multi tape Turing machine. Show that multi-tape Turing machine and one tape Turing machines are equivalent.


5. Define class P and NP with example. Show that: If P₁ is NP complete and three is a polynomial time reduction of P₁ to P₂ then P₂ is NP-complete.


6. Write short notes on (Any two)
   (a) Solvable vs Unsolvable problems
   (b) CNF Satisfiability
   (c) Recursive and Recursively Enumerable Languages

For PDF Click Here