Tribhuvan University

Institute of Science and Technology


Bachelor Level / fourth-semester / Science

Computer Science and Information Technology( CSC257 )

Theory of Computation

Full Marks: 60 + 20 + 20

Pass Marks: 24 + 8 + 8

Time: 3 Hours

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

The figures in the margin indicate full marks.

Section A

Attempt any Two questions. (2x10=20)


Define the NFA with ε-transition and ε-closure of a state. Show that for every regular expression r, representing a language L, there is ε-NFA accepting the same language. Also convert regular expression (a+b)*ab* into equivalent Finite Automata.


How can you define the language accepted by a PDA? Explain how a PDA accepting language by empty stack is converted into an equivalent PDA accepting by final state and vice-versa.


Define a Turing machine. Construct a TM that accept L = {wcwR | w∈(0, 1) and c is ε or 0 or 1. Show that string 0110 is accepted by this TM with sequence of Instantaneous Description (ID).

Section B

Attempt any Eight questions. (8x5=40)


Give the formal definition of DFA. Construct a DFA accepting all strings of {0, 1} with even number of 0’s and even number of 1’s.


Define Chomsky Normal Form and Greibach Normal Form in reference to CFG. Give a suitable example of each.


Give the regular expressions for following language over alphabet {0, 1}.

  1. Set of all strings with 2nd symbol from right is 1.
  2. Set of all strings starting with 00 or 11 and ending with 10 or 01.

Show that language L={0m1m | m>=1} is not a regular language.


Describe the Turing machines with multiple tape, multiple track and storage in state.


Construct a NFA accepting language of {0, 1} with each string ending with 01 and convert it into equivalent DFA.


Construct a PDA accepting language over {0, 1} representing strings with equal no of 0s and1s. Show by sequence of IDs that 0101 is accepted by this PDA.


Define complexity of a Turing machine. Explain about big Oh, big Omega and big Theta notation used for complexity measurement.


What do you mean by tractable and Intractable problems? Explain with reference to TM.