AL-601 - Theory of Computation

Say whether the NFA accepts the following or not: (i) abaa (ii) abab.

Construct a NFA such that the second last symbol is zero over the alphabet (0, 1) then convert in DFA.

Explain 'Finite State Machines with Outputs'. Discriminate between Mealy and Moore machines.

Design a DFA which accept the string starting symbol differ from ending symbol over the alphabet {0, 1}. Show dead state if any.

Minimize the following automata.

Construct context free grammar for $L = \{wcw^R \mid w \in (a + b)^*\}$. Reverse of $w$ is denoted as $w^R$.

Define a deterministic PDA. How a DPDA differs from a non-deterministic PDA?

Find the Greibach normal form grammar equivalent to the following: CFG: $S \to AB$, $A \to BS \mid 1$, $B \to SA \mid 0$.

What do you mean by Parsing? How left most and right most derivation helps to find out the ambiguity in a grammar?

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

Design a Turing Machine which computes the multiplication of two numbers.

State pumping lemma for regular languages. Prove that the language $\{a^n \mid n \text{ is a prime number}\}$ is not regular.

Write short note on (any three): (i) Halting problem (ii) Decidability (iii) Mealy Machine (iv) CNF.