CSIT 4th Semester
Theory Of Computation Board Question Paper 2079

CSC 262-2079 ✡
Tribhuvan University
Institute of Science and Technology
2079
✡
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.

Show that, For any NFA \(N = (Q_N, \Sigma, \delta_N, q_0, F_N)\), there exists a DFA \(D = (Q_D, \Sigma, \delta_D, q_0, F_D)\) such that \(L(N) = L(D)\) for \(L \subseteq \Sigma^*\).

2.

State and prove the Pumping Lemma for regular languages. How can you show with example that pumping lemma is used to prove that a given language is not a regular? Explain.

3.

Given the following expression grammar for simple arithmetic expression with operator + and *. Remove left recursions from this grammar then simplify and convert to CNF.
\(E \rightarrow E + T \mid T\)
\(T \rightarrow T * F \mid F\)
\(F \rightarrow (E) \mid a\)

Section B

Attempt any Eight questions

[8x5=40]
4.

Explain the \(\epsilon\)-closure of states of an \(\epsilon\)-NFA with a suitable example

5.

Convert the following regular expression into equivalent Finite Automata.
a. \((0 + 1)^* 10(1 + 0)\)
b. \(1^* 0(0 + 1)^* 1\)

6.

Define the term: Parse Tree, Left-most and right-most derivation, sentential form and ambiguity with example.

7.

Give the formal definition of Push Down Automata. How CFG can be converted into equivalent PDA? Explain with an example.

8.

Define regular grammar. Also explain the method of converting right linear grammar into equivalent Finite Automata.

9.

Construct a Turing Machine that accept a language \(L = \{a^n b^n \mid n > 0\}\)

10.

Define Turing Machine and explain its roles.

11.

Explain about the complexity classes P, NP and NP-complete.

12.

Write short notes (Any two)
a. Big Oh, Big Omega and Big Theta
b. Tractable and Intractable problems
c. Chomsky Hierarchy.