Theory of Computation (IT-503 (A)) - Important Questions

Construct an NFA for the language over alphabet {0,1} where the second last symbol is 0 and convert the NFA to an equivalent DFA.

Design a DFA to accept strings of 0's and 1's which when interpreted as binary numbers are multiples of 4.

Derive the regular expression accepted by the given DFA / finite automaton using Arden's theorem.

Construct an equivalent finite automaton / DFA directly from the given regular expression (101)(01+11)(10+10).

Define ambiguous grammar and show that the grammar S -> aSbS | bSaS | epsilon is ambiguous.

Write a CFG to accept the language defined by L = {a^i b^j c^k | i,j,k >= 0, i = j+k}.

How are epsilon-productions eliminated from a grammar whose language does not contain empty string? Remove epsilon-productions from the grammar S -> a|aA|B|C, A -> aB|epsilon, B -> Aa, C -> aCD.

Convert a given Mealy machine to an equivalent Moore machine using tabular format with a suitable example.

Convert the given CFG into Greibach Normal Form: A -> BB | 1, B -> AA | 0.

Let G be the grammar S -> aABB | aAA, A -> aBB | a, B -> bBB | A. Construct the PDA that accepts the language generated by this grammar G.

Construct PDAs by empty stack for i) L={a^n b^{2n} | n >= 1}, ii) L={wCw^R | w in (a+b)*}, iii) L={a^n b^n c^m | n >= 1}.

Explain the Turing machine model, including its formal tuple definition, components, working of the read/write head, and its representations.

Write short notes (any three): i) Recursive vs recursively enumerable languages ii) NP-complete and NP-hard problems with examples iii) Chomsky hierarchy iv) Deterministic PDA.