CS-501 - Theory of Computation

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

Design DFA's for detecting 1001 Sequence without 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 3.

Identify the language, L, generated by the following grammar, G: $G = (\{S, A, B\}, \{a, b\}, \{S \to Aa, A \to aB, B \to bB | 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 exactly one a's and no more than two b's.

Construct context free grammars to accept the language $L = \{a^{n+2} b^{n+1} | n=m\}$ over the alphabet, $\Sigma = \{a, b\}$

Construct Non-Deterministic Pushdown Automata (NPDA) to accept the language $L = \{0^{n+1} 2^{n} | n > m\}$ over the alphabet, $\Sigma = \{0, 1\}$

Construct Turing Machine (TM) to accept the language $L = \{0^{n} 1^{2n} | 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^{n} c^{n} | m, n \ge 0\}$ over the alphabet, $\Sigma = \{a, b, c\}$.

Give an NPDA that simulates the following grammar (S is start symbol): $S \to aBb | cDD$ $B \to cd | aS$ $D \to dD | d$

Show that the following language on $\Sigma = \{a, b, c\}$ is not context-free. $L = \{a^{i} b^{n} a^{j} | i \ge 0\}$

Prove that a language L is recursive if and only if L and $\bar{L}$ are recursively enumerable.

Prove that there is no algorithm that determines whether an arbitrary Turing Machine halts when run with the input string 101.

Prove that the problem of determining whether for a Turing Machine M the language L(M) is regular is undecidable.