BE Computer Engineering (IOE, TU) Theory of Computation (IOE, CT 502) Question Paper 2078

(a) Define a Non-deterministic Finite Automaton (NFA) formally as a 5-tuple and explain the role of each component. State how an NFA differs from a DFA.

(b) Consider the NFA with $\varepsilon$-transitions over the alphabet $\Sigma = \{a, b\}$ that accepts all strings containing the substring aba. Using the subset construction algorithm, convert the given NFA into an equivalent DFA. Show the transition table and draw the resulting DFA, clearly marking the start and final states.

(a) Consider the context-free grammar $G$ with productions:

$S \rightarrow aSb \mid SS \mid \varepsilon$

Show the leftmost derivation and draw the parse tree for the string aabbab. State the language $L(G)$ generated by this grammar.

(b) Construct a Pushdown Automaton (PDA) that accepts the language $L = \{ a^n b^n \mid n \geq 1 \}$ by final state. Describe its transition function and trace the moves of your PDA on the input string aaabbb.

(a) Design a Turing Machine that accepts the language $L = \{ a^n b^n c^n \mid n \geq 1 \}$. Give the formal definition (states, tape symbols, transition function) and show the sequence of configurations (instantaneous descriptions) when the machine processes the input aabbcc.

(b) State the Halting Problem and prove that it is undecidable. Explain the significance of this result in the theory of computation.

Explain the Chomsky hierarchy of grammars. For each of the four types (Type 0, Type 1, Type 2, Type 3), describe the form of the production rules, the class of language generated, and the corresponding accepting automaton. Illustrate each grammar type with one suitable example.

(a) Write a regular expression for the language over $\Sigma = \{0, 1\}$ consisting of all strings that have an even number of 0's and end with 1.

(b) State Arden's theorem and use it to find the regular expression accepted by a finite automaton with states $q_1, q_2$ where $q_1$ is the start state, $q_1 \xrightarrow{a} q_1$, $q_1 \xrightarrow{b} q_2$, and $q_2$ is the final state with $q_2 \xrightarrow{a,b} q_2$.

State the pumping lemma for regular languages. Using the pumping lemma, prove that the language $L = \{ a^n b^n \mid n \geq 0 \}$ is not regular.

(a) Define an ambiguous grammar. Show that the grammar $E \rightarrow E + E \mid E * E \mid (E) \mid id$ is ambiguous by giving two distinct parse trees for the string id + id * id.

(b) Briefly explain how the ambiguity in this grammar can be removed.

Convert the following context-free grammar into Chomsky Normal Form (CNF), showing each step of the conversion:

$S \rightarrow ASA \mid aB$ $A \rightarrow B \mid S$ $B \rightarrow b \mid \varepsilon$

Differentiate between a Mealy machine and a Moore machine with respect to output behaviour. Design a Moore machine over $\Sigma = \{0, 1\}$ that outputs the residue (remainder) of the input binary number when divided by 3.

(a) Distinguish between a recursive language and a recursively enumerable language.

(b) State Rice's theorem and give one example of a non-trivial property of recursively enumerable languages that is undecidable as a consequence of it.

(a) Explain the difference between a deterministic PDA (DPDA) and a non-deterministic PDA (NPDA), and state which class of languages each accepts.

(b) State the pumping lemma for context-free languages and explain how it is used to show that a language is not context-free.