AL-601 - Theory of Computation

Design a Moore machine to determine the residue of mod 2 of the input treated as a binary string.

Find an equivalent $\varepsilon$-NFA for the following regular expression $(0 + 1)^*011$.

Convert the $\lambda$-NFA to NFA.

Convert the grammar $\{S \to ABaC \mid ABa,\; A \to Aa \mid a,\; B \to BaB \mid b,\; C \to CC\}$ to Chomsky normal form.

Define formally Type 0, Type 1, Type 2 and Type 3 grammar. Show the corresponding automata for each class.

Construct PDA for the language $wcw^R$ where $w$ is string of zeroes and ones.

Derive regular expression from this Finite Automata.

Define regular language and regular expressions. Find regular expression for the following: Language of all strings that do not end with 01.

Construct a PDA accepting by empty stack each of the following language: (i) $a^n b^m c^m d^n$ where $n,m \ge 1$ (ii) $a^{3n}b^n$, $n \ge 0$.

Convert to Greibach normal form: $S \to AB$, $A \to SA \mid AA \mid a$, $B \to SB \mid b$.

Derive any two representative strings with minimum length 4 from the following context free grammar. $G = (\{S, A, B\}, \{a,b\}, P, S)$; $S \to bA \mid aB$; $A \to bAA \mid aS \mid a$; $B \to aBB \mid bS \mid b$.

Design a Turing Machine that accepts the language $1^n 0^n$ where $n > 0$.

What is a Turing machine? Give the specification of a Turing machine and explain.

Write a short note (any three): (i) Recursively Enumerable (ii) GNF (iii) Derivation Tree (iv) Mealy Machine.