Theory of Computation

Define Alphabet, String and Language.

What is a transition table?

Define ε-closure of a state.

State the Arden's Theorem.

Define Derivation Tree.

What is Greibach Normal Form (GNF)?

Define Instantaneous Description (ID) of a PDA.

What is a multi-tape Turing Machine?

Define Recursive and Recursively Enumerable languages.

What is NP-completeness?

Differentiate between DFA and NFA.

Design a DFA to accept binary numbers divisible by 3.

Convert the regular expression (a+b)* abb to an NFA.

Explain the closure properties of regular languages.

Convert the given grammar into Chomsky Normal Form (CNF).

Design a PDA for L = {a^n b^{2n} | n ≥ 1}.

Explain the Universal Turing Machine.

Discuss the minimization of DFA with an example.

Explain Myhill-Nerode Theorem in detail.

(a) Design a Turing Machine for L = {a^n b^n c^n | n ≥ 1}. (b) Explain the variations of Turing Machines.

Design a PDA for a given CFG. Explain the equivalence of PDA and CFG.

Write short notes on: (i) Post Correspondence Problem (ii) Linear Bounded Automata.