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

(a) Distinguish between a Deterministic Finite Automaton (DFA) and a Non-deterministic Finite Automaton (NFA), clearly stating the role of the transition function in each. (5)

(b) Consider the NFA with $\epsilon$-transitions over the alphabet $\Sigma = \{0, 1\}$ that accepts strings containing the substring 01 or ending in 00. Construct an equivalent DFA using the subset (powerset) construction method, showing the resulting state-transition table and the final transition diagram. (10)

(a) Define a Context-Free Grammar (CFG) formally as a 4-tuple. Design a CFG that generates the language $L = \{ a^n b^m c^m d^n \mid n \ge 1,\ m \ge 0 \}$ and show a leftmost derivation for the string aabccbb... if it belongs to $L$ (justify your answer). (7)

(b) Convert the following grammar into Chomsky Normal Form (CNF), showing each step (removal of $\epsilon$-productions, unit productions, and useless symbols): (8)

(a) Describe the formal model of a standard (single-tape) Turing Machine as a 7-tuple and explain how it accepts, rejects, or loops on an input string. (5)

(b) Design a Turing Machine that accepts the language $L = \{ w c w^{R} \mid w \in \{a, b\}^{*} \}$, where $w^{R}$ denotes the reverse of $w$. Give the complete transition table and trace the computation of the machine on the input string abcba. (10)

(a) Explain the formal definition of a Pushdown Automaton (PDA) and distinguish between acceptance by final state and acceptance by empty stack. (5)

(b) Construct a PDA that accepts the language $L = \{ a^n b^{2n} \mid n \ge 1 \}$ by empty stack. Give the transition function and show the sequence of instantaneous descriptions (moves) for the input string aabbbb. (10)

State the pumping lemma for regular languages. Using it, prove that the language $L = \{ a^{i} b^{j} \mid i > j \ge 0 \}$ is not regular.

(a) Write regular expressions over $\Sigma = \{0, 1\}$ for: (i) all strings of even length, and (ii) all strings in which every 0 is immediately followed by at least one 1. (4)

(b) State the identities used to simplify regular expressions and use them to simplify $(\epsilon + 0)^{*} 1 (\epsilon + 0)^{*}$. (3)

Differentiate between a decidable and an undecidable problem. State the Halting Problem and give an outline of the argument (proof by contradiction) showing that it is undecidable.

(a) Define the complexity classes P, NP, and NP-Complete, and explain the significance of the $P \stackrel{?}{=} NP$ question. (4)

(b) What is a polynomial-time reduction? Explain its role in proving that a problem is NP-complete. (3)

Differentiate between a Moore machine and a Mealy machine. Design a Mealy machine over $\Sigma = \{0, 1\}$ that outputs 1 whenever the input sequence ends in the substring 101, and 0 otherwise.

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.

(a) State and briefly justify any three closure properties of regular languages (e.g. under union, concatenation, and complementation). (4)

(b) Define the terms recursive language and recursively enumerable language, and state the relationship between them. (3)

(a) State the Church-Turing thesis and explain its significance in the theory of computation. (4)

(b) Briefly explain how a multi-tape Turing machine is equivalent in computational power to a single-tape Turing machine. (3)