Questions
Syllabus
Qns. By Syllabus

Semester

Subject

Year

Tribhuwan University

Institute of Science and Technology

2078

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.
Give the formal definition of DFA and NFA. How NFA can be converted into equivalent DFA? Explain with suitable example. [10]
2.
Find the minimum state DFA for the given DFA below:
States01ABFBECCBD∗DEFEBCFBA\begin{array}{|c|c|c|} \hline \text{States} & 0 & 1 \\ \hline A & B & F \\ B & E & C \\ C & B & D \\ *D & E & F \\ E & B & C \\ F & B & A \\ \hline \end{array}
[10]
3.
Construct a Turing Machine that accepts the language of odd length strings over alphabet {a, b}. Give the complete encoding for this TM as well as its input string w = abb in binary alphabet that is recognized by Universal Turing Machine. [10]
Section B

Short Answers Questions

Attempt any Eight questions.
[8*5=40]
4.
Define the term alphabet, prefix and suffix of string, concatenation and Kleen closure with example. [5]
5.
Give the regular expressions for the following language over alphabet {a, b}. a. Set of all strings with substring bab or abb. b. Set of all strings whose 3rd symbol is 'a' and 5th symbol is 'b'. [5]
6.
Show that L = {ana^n | n is a prime number} is not a regular language. [5]
7.
Explain about the Chomsky's Hierarchy about the language and programs. [5]
8.
Define a Push Down Automata. Construct a PDA that accepts L = {anbn∣n>0a^n b^n | n > 0}. [5]
9.
Construct the following grammar into Chomsky Normal Form.
S→abSb∣a∣aAbS \rightarrow abSb \mid a \mid aAb
A→bS∣aAAb∣εA \rightarrow bS \mid aAAb \mid \varepsilon
[5]
10.
Define Turing Machine and explain its different variations. [5]
11.
What do you mean by computational Complexity? Explain about the time and space complexity of a Turing machine. [5]
12.
Explain the term Intractability. Is SAT problem is intractable? Justify [5]