AL-601 - Theory of Computation

Define finite automata and list the features of finite automata with an example.

Design a finite automata with $\Sigma = \{0,1\}$ accepts those strings which starts with $1$ and ends with $0$.

Differentiate between Mealy and Moore machines with a suitable example.

Design a regular expression for the following DFA.

Consider the following NFA with epsilon: compute the $\varepsilon$-closure of each state; give all the strings of length 4 or less accepted by the automation; convert the automation to DFA.

Show that the language $L = \{0^n 1^m \mid n = m \text{ and } n \ge 1\}$ is deterministic context free language.

Define parse tree and construct a parse tree for the string 'abaabb' from the following given grammar: $S \to SS \mid aSb \mid \varepsilon$.

Convert the given CFG into GNF: $S \to ABA \mid AAB \mid BA \mid AA \mid B$; $A \to aA \mid a$; $B \to bB \mid b$.

Define pushdown automata and explain its model with a neat sketch.

Construct a PDA for the given language $L = \{WW^R \mid W \in \{a,b\}^*\}$.

Convert the following grammar into PDA which accepts the same language by empty stack: $S \to 0S1 \mid A$; $A \to 1A0 \mid S \mid \varepsilon$.

Design a Turing machine over {0,1} for the language L = {W/W is a multiple of 3}.

Find whether the post correspondence problem P = {(ba, bab), (abb, bb), (bab, abb)} has a match? Explain in detail.

Write a short note on any two of the following: (a) Arden's theorem (b) Chomsky hierarchy of the grammar (c) NPDA (d) N-P Complete problem.