Bachelors Level/Second Year/Fourth Semester/Science csit/fourth semester/theory of computation/syllabus wise questions
B.Sc Computer Science and Information Technology
Institute of Science and Technology, TU
Theory of Computation (CSC262)
Year Asked: 2079, syllabus wise question
Basic Foundations
1.
Explain the $\varepsilon$-closure of states on an $\varepsilon$-NFA with suitable examples. [5]
2.
Write short notes (Any two): a) Big Oh, Big Omega and Big Theta b) Tractable and Intractable Problems c) Chomsky Hierarchy [5]
Context Free Grammar
1.
Given the following expression grammar for simple arithmetic expression with operator + and *. Remove the left recursion 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$
[10]
2.
Define the term: Parse Tree, left-most and right-most derivation, sentential form and ambiguity with example. [5]
Introduction to Finite Automata
1.
Show that, for any NFA $N = (Q, \Sigma, \delta, q_0, F)$ accepting language $L = \Sigma$, there is a DFA $D = (Q', \Sigma', q_0', \delta', F')$ accepting the same language $L$. [10]
Push Down Automata
1.
Give the formal definition of Push Down Automata. How CFG can be converted into equivalent PDA. Explain with an example. [5]
Regular Expressions
1.
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. [10]
2.
Convert the following regular expression into equivalent Finite Automata.
$a. (0+1)*10(1+0)$
$b. 1*0(0+1)*1$
[5]
3.
Define regular grammar. Also explain the method of converting right linear grammar into equivalent finite automata. [5]
Turing Machines
1.
Construct a Turing machine that accepts the language,
$L = \{a^n b^n \mid n \geq 0\}$
[5]
2.
Define Turing machine and its roles. [5]
Undecidability and Intractability
1.
Explain about the complexity classes p, NP and NP-Complete. [5]