Theory of Computation (AL-601) - Important Questions

Define finite automata and list the features of finite automata with an example.

Differentiate between Mealy and Moore machines (finite state machines with outputs) with a suitable example.

Design a finite automaton over {0,1} accepting strings that start with 1 and end with 0.

Derive the regular expression corresponding to a given DFA / finite automaton.

Given an NFA with epsilon-transitions, compute epsilon-closure of each state, list strings of length at most 4 accepted, and convert to an equivalent DFA.

Convert a given context-free grammar (CFG) into Greibach Normal Form (GNF).

Define parse tree and construct a parse tree for the string 'abaabb' from the given grammar: S -> SS / aSb / epsilon.

Define formally Type 0, Type 1, Type 2 and Type 3 grammar. Show the corresponding automata for each class.

Define pushdown automata and explain its model with a neat sketch.

Construct a PDA for the language of even-length palindromes L = { WW^R | W in {a,b}* } over {a,b}.

Convert the following grammar into PDA which accepts the same language by empty stack: S -> 0S1 / A, A -> 1A0 / S / epsilon.

Design a Turing Machine that accepts the language a^n b^n (or 1^n 0^n) where n >= 1.

Find whether the post correspondence problem P = {(ba, bab), (abb, bb), (bab, abb)} has a match? Explain in detail.

Write short notes on any three of the following: (i) Halting problem of Turing machine (ii) Decidability and Recursively Enumerable Languages (iii) Post Correspondence Problem (iv) NP-complete problems.