CSIT-503 (A) - Theory of Computation

Compute the Regular Expression for the DFA as shown below. alt=''

Design DFA's for detecting 1100 Sequence with Overlap over the alphabet $\Sigma = \{0, 1\}$.

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.

Identify the language, L generated by the following grammar, G: $G = (\{A, B\}, \{a, b\}, \{S \to Aaa \mid A\}, \{B \to bbb \mid B\}, S)$

Convert the following NFA to an equivalent DFA. alt=''

Find a regular grammar that generates the language on $\{a, b\}$ consisting of all strings with at most one a's and more than two b's.

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

Construct context free grammars to accept the language $L(G) = \{a^n b^m c^p d^n \mid n \ge 0, m > 0\}$ over the alphabet, $\Sigma = \{a, b, c, d\}$.

Give a Deterministic PDA that accepts $\{a^n b^m \mid n \ge m + 2\}$ over the alphabet, $\Sigma = \{a, b\}$.

Construct a Turing Machine (TM) to accept the language $L = \{0^n 1^n 2^n \mid n > 0\}$ over the alphabet, $\Sigma = \{0, 1, 2\}$.

Construct corresponding CFG for the following NPDA. alt=''

Give a Deterministic PDA that accepts $\{a^n b^m \mid n \ge m + 2\}$ over the alphabet, $\Sigma = \{a, b\}$.

Give an NPDA that simulates the following grammar (S is start symbol): $S \to aABB \mid aAA$ $A \to bBB \mid a$ $B \to bBB \mid A$

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

Prove that the recursive languages are closed under union, intersection, and complement.

Given the following ambiguous context free grammar $S \to aAb \mid aAa$ $A \to a \mid Aa$ $B \to b$

i) Find the string S generated by the grammar that has two leftmost derivations. Show the derivations.

ii) Show the two derivation trees for the string S.

iii) Find an equivalent unambiguous context-free grammar.

iv) Give the unique leftmost derivation and derivation tree for the string S generated from the unambiguous grammar above.