Questions
Syllabus
Qns. By Syllabus

Semester

Subject

Year

Tribhuwan University

Institute of Science and Technology

2080.1

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.
Describe the extended transition function of NFA. Construct a NFA, using transition table and transition diagram, over {0, 1} that accept the string having substring 01 and ends with 1. Show the acceptance of 0111.[10]
2.
Define CFG. Construct a CFG that generates the language of all palindromes over {a,b} that do not contain the substring aa. Show the leftmost derivation and construct the equivalent parse tree for string babbbab.[10]
3.
How Turing Machine is used as a computing function? Construct a TM for simulating a function f(x) = 2x for x = {1}. Iterate the TM for input 11 and generate the output 1111.[10]
Section B

Short Answers Questions

Attempt any Eight questions.
[8*5=40]
4.
Differentiate Kleen closure from positive closure. Compute positive and Kleen closure of {ab}. [5]
5.
Design a Mealy machine over {a, b} that generates output 'A' if the input string ends with aa else output 'B' if the string ends with bb. [5]
6.
Construct regular expression over {1,2,...,9} that represents a. strings of even numbers with length 4 starting with 2 and ending with 8. b. strings starting with odd numbers and ending with even numbers. [5]
7.
Prove that th language is not a context free grammar.

$L = \{a^n b^n c^n \mid n \geq 0\}$
[5]
8.
Construct a PDA that accepts string over $\Sigma = \{ a, b \}$ that contains equal number of a's followed by equal number of b's. Show acceptance of aabb and aab. [5]
9.
Describe how multi-stack TM is different from the semi-infinite tape TM? [5]
10.
What is intractability? Define time and space complexity of turing machine. [5]
11.
How is conversion of PDA to CFG done? Illustrate with example. [5]
12.
State Arden's theorem. Convert following DFA into its regular expression using Arden theorem.

$\begin{array}{|c|c|c|} \hline & 0 & 1 \\ \hline \rightarrow *Q1 & Q1 & Q2 \\ Q2 & Q3 & Q2 \\ Q3 & Q1 & Q2 \\ \hline \end{array}$
[5]