CS-501 - Theory of Computation

Explain Moore and Mealy machines with examples. How do they differ in output behaviour?

Convert the given Moore machine to a Mealy machine: States: $\{A, B\}$ Output: A/0, B/1 Transitions: $A \to aB, A \to bA, B \to aA, B \to bB$

What is a 2-way DFA? How does it differ from standard DFA in terms of tape head movement?

Minimize the DFA with states $\{A,B,C,D\}$, where A is initial, C is final, and transitions: $A \to aB, A \to bA; B \to aC, B \to bA; C \to aC, C \to bD; D \to aC, D \to bA$

Explain ambiguity in context-free grammars with an example. How can it be resolved?

Convert the grammar $S \to aSb \mid SS \mid \epsilon$ to Chomsky Normal Form (CNF).

Describe the conversion from PDA to CFG using the standard algorithm.

Construct a PDA for the language $L = \{ww^R \mid w \in (a+b)\}$.

Compare multi-tape and multi-head Turing machines. How do they affect computational power?

Explain the concept of NP-complete problems with examples.

Differentiate between decidable and recursively enumerable languages.

Discuss the significance of the Recursion Theorem in computability theory.

Prove that the Halting Problem is undecidable using diagonalization.

For the regular expression $(a+b)ab(a+b)$, calculate the minimum number of states in equivalent NFA and DFA.