Theory of Computation
This course presents a study of Finite State Machines and their languages. It covers the details of finite state automata, regular expressions, context free grammars. More, the course includes design of the Push-down automata and Turing Machines. The course also includes basics of undecidability and intractability.
Tribhuvan University
Institute of Science and Technology
2079
Bachelor Level / fourth-semester / Science
Computer Science and Information Technology( CSC262 )
Theory of Computation
Full Marks: 60 + 20 + 20
Pass Marks: 24 + 8 + 8
Time: 3 Hours
Candidates are required to give their answers in their own words as far as practicable.
The figures in the margin indicate full marks.
Section A
Attempt any TWO questions
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.
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.
Given the following expression grammar for simple arithematic expression with operator + and *.
E→ E+T | T
T → T+F | F
F → (E) | a
Remove the left recursion from this grammar then simplify and convert to CNF.
Section B
Attempt any EIGHT questions
Explain the ε-closure of states on an ε-NFA with suitable examples.
Convert the following regular expression into equivalent Finite Automata
a. (0+1)*10(1+0)
b. 1*0(0+1)*1
Define the term: Parse Tree, left-most and right-most derivation, sentential form and ambiguity with example.
Give the formal definiton of Push Down Automata. How CFG can be converted into equivalent PDA. Explain with an example.
Define regular grammar. Also explain the method of converting right linear grammar into equivalent finite automata.
Construct a Turing machine that accepts the language, L = { an bn | n≥0}
Define Turing machine and its roles.
Explain about the complexity classes p, NP and NP-Complete.
Write short notes ( Any two ) :
a) Big Oh, Big Omega and Big Theta
b) Tractable and Intractable Problems
c) Chomsky Hierarchy