Theory of Computation

Define Finite Automata.

What is a Non-deterministic Finite Automata (NFA)?

Define Regular Expression.

What is the difference between Moore and Mealy machines?

State Kleene's Theorem.

Define Context-Free Grammar (CFG).

What is Ambiguity in grammar?

Define Pushdown Automata (PDA).

What is a Turing Machine?

Define Halting Problem.

Construct a DFA that accepts strings over {0, 1} ending with '101'.

Convert the given NFA to an equivalent DFA.

Explain the Pumping Lemma for regular languages.

Simplify the given CFG by removing null and unit productions.

Construct a PDA for the language L = {w w^R | w ∈ {a, b}*}.

Explain the Church-Turing Thesis.

Describe the various types of Turing Machines.

Explain the Chomsky Hierarchy of languages in detail.

(a) State and prove the Pumping Lemma for Context-Free Languages. (b) Use Pumping Lemma to show that L = {a^n b^n c^n | n ≥ 1} is not context-free.

Design a Turing Machine to accept the language L = {a^n b^n | n ≥ 1}.

Explain the conversion of Regular Expression to Finite Automata using Thompson's construction.

Discuss the decidability and undecidability of languages. Explain Rice's Theorem.