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

Construct an NFA for a given language and convert the NFA to an equivalent DFA.

Design a DFA to accept binary strings interpreted as binary numbers that are multiples of 4.

Write short note on: (Any three)

What are the components of finite automata model?

Construct a DFA to recognize strings with odd number of 1's and even number of 0's.

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

Design a DFA over $\Sigma = \{0,1\}$ to detect the substring $1100$ with overlap.

Design a NFA that accepts the language over the alphabet, $\Sigma = \{0, 1, 2\}$ where the decimal equivalent of the language is divisible by 4

Derive the regular expression accepted by a given DFA / finite automaton.

Construct an equivalent finite automaton / DFA directly from a given regular expression.

Identify the language generated by the given grammar G.

Construct a regular grammar generating all strings over {a,b} with at most one a and more than two b's.

Consider the following productions, $S \to aB|bA, A \to aS|bAA|a, B \to bS|aBB|b$ For the string aabbabbba, find the :

Construct a CFG for $L = \{a^i b^j c^k \mid i,j,k \ge 0, i = j+k\}$.

How $\epsilon$-productions are eliminated from a grammar whose language doesn't have empty string? Remove $\epsilon$-productions from the grammar given below. $S \to a|aA|B|C, A \to aB | \epsilon, B \to Aa, C \to aCD,$ $D \to ddd$

Define ambiguous grammar and show that $S \to aSbS | bSaS | \epsilon$ is ambiguous.

Convert the given CFG into Greibach Normal Form.

Show that $id+id*id$ has two distinct leftmost derivations in the grammar $E \rightarrow E+E / E*E / (E) / id$.

Explain whether an ambiguous CFG can be converted into Chomsky Normal Form.

Construct a CFG equivalent to the regular expression $(01+1)^*(00+1)$.

For the given ambiguous grammar $S \to Ab | aaB$, $A \to a | Aa$, $B \to b$, find a string with two leftmost derivations and trees, give an equivalent unambiguous grammar with unique derivation.

Construct a CFG for $L = \{a^n b^m c^m d^{2n} \mid n \ge 0, m>0\}$.

Construct an (N)PDA that accepts the language generated by the grammar $S \to aABB \mid aAA$, $A \to aBB \mid a$, $B \to bBB \mid A$.

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

Construct a PDA for $L=\{a^n b^{n+m} c^m \mid n \geq 0, m \geq 0\}$.

Construct a PDA for the grammar $X \to 0X3 \mid 0A3$, $A \to 1A2 \mid 12$.

Construct Non-Deterministic Pushdown Automata (NPDA) to accept the language $\{w | w \text{ starts and ends with the same symbol}\}$ over the alphabet, $\Sigma = \{0, 1\}$

Construct corresponding CFG for the following NPDA.

Design a deterministic PDA accepting $\{a^n b^m : m \ge n+2\}$ over $\Sigma = \{a,b\}$.

Write a short notes (any three):

Explain the difference between recursive and recursively enumerable languages.

What are NP-complete and NP-hard problems? Explain them with examples.

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

Design a Turing Machine to accept strings over $\{a,b\}$ with even total length, i.e., $N(a)+N(b)$ is even.

Prove that recursive languages are closed under complement (and union and intersection).

Construct a Turing Machine to accept the language $L = \{0^{2n}1^n 2^{2n} \mid n \ge 0\}$.

Prove that the problem of determining whether for a Turing machine M there is some input string for which M halts is undecidable.

Explain Chomsky hierarchy of grammar with suitable example.