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 ε-closure of states on an ε-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→E+T∣T
T→T+F∣F
F→(E)∣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,Σ,δ,q0,F) accepting language L=Σ, there is a DFA D=(Q′,Σ′,q0′,δ′,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={anbn∣n≥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]