Theory of Computation (CS-501) - Important Questions

Convert the given Moore machine to its equivalent Mealy machine with states {A, B}, outputs A/0, B/1 and transitions A-a->B, A-b->A, B-a->A, B-b->B.

What is a deterministic finite automata (DFA)? Design a DFA over alphabet {0,1} accepting all strings starting and ending with different symbols.

Convert the given NFA to an equivalent DFA where states={q0,q1}, alphabet={a,b}, delta(q0,a)={q0,q1}, delta(q0,b)={q0}, delta(q1,b)={q1} and final state is q1.

Write a regular expression for the language over {a,b} consisting of all strings ending with the substring 'ab'.

Derive the regular expression for the given DFA using Arden's theorem. State Arden's theorem.

Explain ambiguity in context-free grammars with a suitable example and explain how ambiguity can be removed.

For the grammar S -> aSb | ab, find the leftmost and rightmost derivations and draw the parse tree for the string 'aabb'.

Convert the given context-free grammar to Chomsky Normal Form (CNF): S -> AB | a, A -> a, B -> b.

Find an equivalent reduced context-free grammar with no useless symbols for G with productions S -> AC/B, A -> a, C -> c/BC, E -> aA/e.

Explain pushdown automata and compare deterministic PDA (DPDA) and non-deterministic PDA (NPDA) with a suitable example. Are they equivalent?

Design a PDA for the language L = {a^n b^n | n >= 1}.

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

Explain recursively enumerable languages and decidable/recursive and undecidable languages with examples.

What is the halting problem of Turing machine? Prove/explain why it is undecidable.

Differentiate between decidable (recursive) and recursively enumerable languages.

Explain the concept of NP-complete problems with suitable examples.