CS-501 - Theory of Computation

Explain finite automata as language acceptors and translators.

Design a Mealy machine that outputs '1' whenever the input symbol is '1', otherwise outputs '0'.

Explain deterministic and non-deterministic finite automata with examples.

Convert the given NDFA to an equivalent DFA: States $\{q0, q1\}$, Alphabet $\{a, b\}$, Transitions: $\delta(q0, a)=\{q0, q1\}$, $\delta(q0, b)=\{q0\}$, $\delta(q1, b)=\{q1\}$. Final state= $q1$

Explain regular expressions and Arden's theorem.

Write a regular expression for the language over $\{a, b\}$ that contains strings ending with "ab".

Explain context free grammar and derivation trees.

For the grammar: $S \to aSb \mid ab$, derive the string "aabb" and draw its parse tree.

Explain ambiguity in grammar and methods to remove it.

Convert the grammar into Chomsky Normal Form: $S \to AB \mid A, A \to a, B \to b$

Explain pushdown automata and deterministic and non-deterministic PDAs.

Design a PDA for the language $L={a^n b^n \mid n \ge 1}$.

Explain Turing machines and techniques for their construction.

Design a Turing machine to accept strings over $\{0,1\}$ having even number of 1's.

Explain decidable, undecidable, recursive, and recursively enumerable languages.

What is the halting problem? Explain why it is undecidable.