Theory of Computation (AD-501) - Important Questions

Prove that $1^2 + 2^2 + 3^2 + ... + n^2 = \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ using mathematical induction.

Explain the purpose of Mealy machine and Moore machine. Write application areas of Mealy and Moore machine. Convert the following Mealy machine into an equivalent Moore machine.

Construct a regular expression corresponding to the given finite automata using Arden's theorem. Write the applications of Arden's theorem.

Design a DFA accepting strings of a's and b's having exactly one a over alphabet {a, b}.

Explain Greibach Normal Form (GNF) and Chomsky Normal Form (CNF) with suitable examples.

Write the context-free grammar (CFG) for the regular expression $(011 + 1)^(01)^.

What do you mean by Parsing? How do leftmost and rightmost derivations help to find out the ambiguity in a grammar?

Design a pushdown automaton for the language $L = \{a^n b^n \mid n \ge 1\}$ and test the acceptability of the string "aaaabbab".

Explain the terms P, NP and NP-complete with suitable examples.

Design a Turing machine that computes the 2's complement of a given binary string over $\Sigma = \{0,1\}$. Show the output of your machine for the string "00000".

Apply minimization to the following DFA using the Equivalence theorem and construct the minimal DFA.

Convert the given epsilon-NFA with states q0, q1, q2, q3 and q4 into an equivalent NFA without epsilon moves.

Design a deterministic finite automaton (DFA) accepting the set of all strings over {a,b} containing exactly two a's and exactly two b's.

Design a pushdown automaton by final state for the language $L = \{x \mid n_a(x) = n_b(x), x \in \{a,b\}^*\}$ having equal number of a's and b's.

Write short notes on any two of the following: (i) Halting problem of Turing machine (ii) Post Correspondence Problem with example (iii) Turing machine as acceptor.