CSIT 4th Semester
Theory Of Computation Board Question Paper 2080

CSC 262-2080 ✡
Tribhuvan University
Institute of Science and Technology
2080
✡
Bachelor Level/Second Year/Fourth Semester/Science
Computer Science Information Technology (CSC 262)
(Theory Of Computation)
(New Course)
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 Answer Questions
Attempt any Two question.
[2x10=20]
1.

Describe the extended transition function of NFA. Construct a NFA, using transition table or transition diagram, over \(\Sigma = \{0, 1\}\) that accepts the strings having substring 01 and ends with 1. Show the acceptance of 01111.

2.

Define CFG. Construct a CFG that generates the language of all palindromes over \(\Sigma = \{a, b\}\) that do not contain the substring ab. Show the leftmost derivation and construct the equivalent parse tree for string babbbab.

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 to compute 111 and generate the output.

Section B

Attempt any Eight questions

[8x5=40]
4.

Differentiate Kleen closure from Positive closure. Compute positive and Kleen closure over \(\Sigma = \{a, b\}\).

5.

Design a Mealy machine over \(\Sigma = \{1, 0\}\) that generates output 'A' if the input string ends with 11 else output 'B' if the string ends with 00.

6.

Construct regular expression over \(\{1 \ldots 9\}\) that represents
a. strings of even number with length 4 starting with 1 and ending with 8
b. strings starting with odd number and ending with even numbers

7.

Prove that the language \(L = \{a^n b^n c^n \mid n > 0\}\) is not context free.

8.

Construct a PDA that accepts strings over \(\Sigma = \{a, b\}\) that contains equal number of a's followed by equal number of b's. Show acceptance of aabb and aaabbb.

9.

Describe how multi-stack TM is different from the semi-infinite tape TM?

10.

What is intractability? Define time and space complexity of Turing Machine.

11.

How conversion of PDA to CFG is done? Illustrate with an example

12.

State Arden's theorem. Convert following DFA into its regular expression using Arden theorem.

01
\(\rightarrow q_0\)\(q_1\)\(q_2\)
\(q_1\)\(q_3\)\(q_2\)
\(q_2\)\(q_1\)\(q_2\)