Questions
Syllabus
Qns. By Syllabus

Semester

Subject

Year

Tribhuwan University

Institute of Science and Technology

2076

Bachelor Level / Second Year / Fourth Semester / Science

B.Sc in Computer Science and Information Technology (CSC262)

(Theory of Computation)

Full Marks: 60

Pass Marks: 24

Time: 3 Hours

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

The figures in the margin indicate full marks.

Section A

Long Answers Questions

Attempt any TWO questions.
[2*10=20]
1.
Define the NFA with ϵ−transition\epsilon-transition and ϵ−closure\epsilon-closure of a state. Show that for every regular expression r, representing a language L, there is ϵ−NFA\epsilon-NFA accepting the same language. Also convert regular expression (a+b)*ab* into equivalent Finite Automata. [10]
2.
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. [10]
3.
Define a Turing machine. Construct a TM that accept L={wcwR∣w∈{0,1} and c is ε or 0 or 1}L = \{ wcw^R \mid w \in \{0, 1\} \text{ and } c \text{ is } \varepsilon \text{ or } 0 \text{ or } 1 \}. Show that string 0110 is accepted by this TM with sequence of Instantaneous Description (ID). [10]
Section B

Short Answers Questions

Attempt any Eight questions.
[8*5=40]
4.
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. [5]
5.
Define Chomsky Normal Form and Greibach Normal Form in reference to CFG. Give a suitable example of each. [5]
6.
Give the regular expressions for following language over alphabet {0, 1}. a. Set of all strings with 2nd symbol from right is 1. b. Set of all strings starting with 00 or 11 and ending with 10 or 01. [5]
7.
Show that language is not a regular language.
L={0m1m∣m≥1}L = \{ 0^m 1^m \mid m \geq 1 \}
[5]
8.
Describe the Turing machines with multiple tape, multiple track and storage in state. [5]
9.
Construct a NFA accepting language of {0, 1} with each string ending with 01 and convert it into equivalent DFA. [5]
10.
Construct a PDA accepting language over {0, 1} representing strings with equal no of 0s and 1s. Show by sequence of IDs that 0101 is accepted by this PDA. [5]
11.
Define complexity of a Turing machine. Explain about big Oh, big Omega and big Theta notation used for complexity measurement. [5]
12.
What do you mean by tractable and Intractable problems? Explain with reference to TM. [5]