Theory of Computation (CS-501) - Important Questions

Explain finite automata as language acceptors and translators.

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

Design a Mealy machine that outputs 1 when the input is '1' and 0 otherwise.

Convert the given Moore machine with states $\{A, B\}$ to an equivalent Mealy machine.

Explain the differences between Mealy and Moore machines and convert the given Moore machine into its equivalent Mealy machine.

Define finite-automata machine mathematically and explain its types.

Convert a given Moore machine to its equivalent Mealy machine.

Write a regular expression for a given language description over an alphabet (e.g., containing a substring, ending with a pattern, with a count condition).

Convert the given NFA (NDFA) to an equivalent DFA.

Given a regular expression, calculate the minimum number of states in the equivalent NFA and DFA.

Explain deterministic and non-deterministic finite automata with examples.

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

Minimize the given DFA with states $\{A,B,C,D\}$, initial state $A$, final state $C$, and specified $a,b$-transitions.

Explain regular expressions and Arden's theorem.

Compute / derive the regular expression for the given DFA / finite automata.

What is a DFA machine? Design a deterministic finite automata machine over the alphabet set $\{0, 1\}$, accepting all strings starting and ending with different alphabet.

Minimize a DFA using the Myhill-Nerode theorem.

Define regular expression and find the regular expression for a given DFA.

Construct DFAs over $\{a,b\}$ for: exactly one $a$, at least one $a$, and at least one $a$ followed by exactly two $b$'s.

Convert a given context-free grammar to Chomsky Normal Form (CNF).

Explain ambiguity in context-free grammars with an example and how it can be resolved / removed.

Find the leftmost and rightmost derivations and draw the parse tree for a given string using a given grammar

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

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

Explain context-free grammar and derivation trees.

Discuss about the Chomsky hierarchy of languages with their grammar constraints rules and corresponding automata for each class.

Find a reduced Grammar equivalent to Grammar $G$, having Production rules $P$.

$P: \{ S \to AC / B, A \to a, C \to c / BC, E \to aA / e \}$

Show that $L = \{a^n b^n c^n / n \ge 1\}$ is not a context-free language.

Consider the following grammar for list structures:

$S \to a / \wedge / (T)$

$T \to T,S / S$

Find left most derivation, right most derivation and parse tree for the string $(((a,a),\wedge(a)),a)$.

Convert the grammar $S \to AB, A \to BS / b, B \to SA / a$ into Greibach normal form.

Find an equivalent reduced context-free grammar with no useless symbols.

Explain pushdown automata and compare deterministic PDA (DPDA) and non-deterministic PDA (NPDA) with a suitable example, including whether they are equivalent.

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)\}$

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

Construct an NPDA/PDA that accepts the language generated by a given CFG.

Is NPDA (non-deterministic PDA) and DPDA (deterministic PDA) equivalent or not? Illustrate with an example.

Construct a PDA accepting the language $\{(ab)^n : n \ge 1\}$ by empty stack

Construct PDAs by empty stack for i) $L=\{(ab)^n \mid n\ge 1\}$, ii) $L=\{ww^R\}$, iii) $L=\{a^{2n}b^n \mid n\ge 1\}$.

Design pushdown automata for i) $a^n b^{3n}, n\ge 1$ and ii) $ww^R$.

Construct an NPDA to accept the language $L = \{0^{n+1}1^{2n} \mid n \ge 1\}$ over $\Sigma = \{0,1\}$.

Construct the CFG corresponding to a given NPDA.

Give a deterministic PDA that accepts $\{a^{m}b^{n}c^{n} \mid m,n \ge 0\}$ over $\Sigma = \{a,b,c\}$.

What is the halting problem and prove/explain why it is undecidable

Explain recursively enumerable languages and decidable / recursive (and undecidable) languages.

Differentiate between decidable and recursively enumerable languages.

Compare multi-tape vs multi-head Turing machines and their effect on computational power.

Explain the concept of NP-complete problems with examples.

Explain Turing machines and techniques for Turing machine construction.

Prove that the Halting Problem is undecidable using diagonalization.

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

Write a short notes on the following:

Explain the difference between tractable and intractable problems with examples.

Explain the different models/variants of Turing machines.

Explain P and NP problems with examples.

Discuss the significance of the Recursion Theorem in computability theory.