BE Computer Engineering (Pokhara University) Theory of Computation (PU, CMP 264) Question Paper 2079

(a) Distinguish between a Deterministic Finite Automaton (DFA) and a Non-deterministic Finite Automaton (NFA) with respect to their transition functions and computational power. (4)

(b) Consider the NFA $M$ over the alphabet $\Sigma = \{0,1\}$ with start state $q_0$, accepting state $q_2$, and the following transitions: $\delta(q_0,0)=\{q_0,q_1\}$, $\delta(q_0,1)=\{q_0\}$, $\delta(q_1,1)=\{q_2\}$. Convert $M$ into an equivalent DFA using the subset construction method, showing the resulting state table and the corresponding state diagram. (8)

(a) Define a Context-Free Grammar (CFG) formally as a 4-tuple. Show that the grammar with productions $E \rightarrow E + E \mid E * E \mid (E) \mid \text{id}$ is ambiguous by giving two distinct parse trees for the string $\text{id} + \text{id} * \text{id}$. (6)

(b) Construct a Pushdown Automaton (PDA) that accepts the language $L = \{ a^n b^n \mid n \geq 1 \}$ by final state. Clearly specify the transition function and trace the acceptance of the string $aabb$. (6)

(a) Design a Turing Machine that accepts the language $L = \{ w \in \{a,b\}^* \mid w \text{ contains an equal number of } a\text{'s and } b\text{'s} \}$. Give the transition table and explain the working of your machine on the input $abba$. (8)

(b) State the Halting Problem and prove that it is undecidable. (4)

(a) State the rules for constructing regular expressions and write a regular expression over $\Sigma = \{0,1\}$ for the language of all strings that contain at least two consecutive $0$'s and end with a $1$. (5)

(b) State the Pumping Lemma for regular languages and use it to prove that the language $L = \{ a^n b^n \mid n \geq 0 \}$ is not regular. (7)

Design a DFA over the alphabet $\Sigma = \{0,1\}$ that accepts all strings in which the number represented by the binary string is divisible by $3$ (read most significant bit first). Draw the state diagram and briefly justify each state.

Convert the regular expression $(a \mid b)^* ab$ into an equivalent NFA with epsilon-transitions using Thompson's construction. Show each step of the construction.

Convert the following context-free grammar into Chomsky Normal Form (CNF):

$S \rightarrow ASA \mid aB$

$A \rightarrow B \mid S$

$B \rightarrow b \mid \varepsilon$

Differentiate between deterministic and non-deterministic pushdown automata. Construct a PDA equivalent to the grammar $S \rightarrow aSb \mid \varepsilon$ and explain why this language cannot be accepted by any finite automaton.

(a) Explain the formal definition of a standard (single-tape) Turing Machine as a 7-tuple. (3)

(b) Briefly describe a multi-tape Turing Machine and state whether it is more powerful than a single-tape Turing Machine, justifying your answer. (3)

Differentiate between recursive (decidable) and recursively enumerable languages with the help of suitable examples. Explain the relationship between the two classes using a closure-under-complement argument.

(a) Define the complexity classes $P$ and $NP$ and explain what is meant by an $NP$-complete problem. (4)

(b) State the significance of the $P$ versus $NP$ question and give one example of a well-known $NP$-complete problem. (3)

Using the principle of mathematical induction, prove that for every integer $n \geq 1$, the number of distinct strings of length $n$ over an alphabet $\Sigma$ with $|\Sigma| = k$ is exactly $k^n$. Clearly state the basis and the inductive step.