Theory of Computation (AD-501) - Important Questions

Prove that $1^2 + 2^2 + 3^3 + ...\ 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 area of Mealy and Moore machine. Convert the following Mealy machine into Moore Machine.

Explain the types of Automata and prove that the Finite Automata as a language acceptor and translator.

Construct a Mealy machine for binary language to determine the residue modulo 5.

Convert given finite automata to equivalent regular expression using Arden's theorem, including applications of Arden's theorem.

Convert epsilon-NFA to NFA. Consider the example having states q0, q1, q2, q3 and q4.

Design a DFA accepting strings of $a$'s and $b$'s having exactly one $a$.

Apply minimization of the following DFA using Equivalence theorem.

Write short notes on any two of the following:

Design a DFA accepting strings with exactly two $a$'s and exactly two $b$'s.

Design an NFA accepting strings containing neither aa nor bb.

Explain Greibach Normal Form and Chomsky Normal Form.

Write given CFG for R.E $(011 + 1)^*(01)^*$.

Check whether the given grammar is ambiguous. $S \to A1B$, $A \to 0A|\varepsilon$, $B \to 0B|1B|\varepsilon$ and construct leftmost and rightmost derivations for the string 00101.

Construct an equivalent grammar in Chomsky Normal Form (CNF) for a given context-free grammar.

Construct an equivalent grammar in Greibach Normal Form (GNF) for a given context-free grammar.

What do you mean by Parsing? How left most and right most derivation helps to find out the ambiguity in a grammar?

Explain the Patri nets model with example.

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

Design a PDA by final state for the language of strings over $\{a,b\}$ with equal number of $a$'s and $b$'s.

Construct CFG for the PDA given below $A=(\{q_0,q_1\}, \{0,1\}, \{S,A\}, \delta, q_0, S, \varphi)$ where $\delta$ is given as below $\delta(q_0, 1, S)=\{(q_0, AS)\}$ $\delta(q_0, \varepsilon, S)=\{(q_0, \varepsilon)\}$ $\delta(q_0, 1, A)=\{(q_0, AA)\}$ $\delta(q_0, 0, A)=\{(q_1, A)\}$ $\delta(q_0, 1, A)=\{(q_1, \varepsilon)\}$ $\delta(q_1, 0, S)=\{(q_0, S)\}$

Construct a PDA by empty stack for odd-length palindromes over $\{a,b\}$.

Write short notes on variations of Turing machines, two-way finite automata, multitape Turing machines, and halting problem (any two).

Explain the terms P, NP, NP complete. Give suitable example. https://www.rgpvonline.com

Design a Turing machine that computes the 2's complement of a binary string.

Design a Turing machine for the language $L = \{a^n b^n c^n / n \ge 1\}$.

Discuss about the Universal Turing Machine.

Define Post Correspondence Problem (PCP) and give a solution for given lists X and Y.