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

(a) Define a Non-deterministic Finite Automaton (NFA) formally as a 5-tuple and explain how it differs from a Deterministic Finite Automaton (DFA). (b) Construct an NFA that accepts the language of all strings over $\{0,1\}$ that contain the substring $011$. Convert the obtained NFA into an equivalent DFA using the subset construction method, clearly showing the transition table and the resulting state diagram.

(a) Define a Context-Free Grammar (CFG) and a Pushdown Automaton (PDA). Explain the equivalence between CFGs and PDAs. (b) Consider the grammar $S \rightarrow aSb \mid ab$. Show that it generates the language $L = \{a^n b^n \mid n \geq 1\}$ and construct a PDA (accepting by empty stack) that recognizes this language, giving its complete set of transition rules.

(a) Describe the formal model of a standard (single-tape) Turing machine and explain the Church-Turing thesis. (b) Design a Turing machine that accepts the language $L = \{a^n b^n c^n \mid n \geq 1\}$. Give the transition function and trace the computation of the machine on the input string $aabbcc$.

(a) State the precedence and meaning of the regular expression operators. (b) Write regular expressions for: (i) all strings over $\{0,1\}$ whose length is a multiple of 3, and (ii) all strings over $\{a,b\}$ that begin and end with the same symbol.

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

Explain the Chomsky hierarchy of grammars. For each of the four types, give the form of production rules and the corresponding class of accepting automaton, illustrating with a suitable example for each type.

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 (or leftmost derivations) for the string $id + id * id$, and suggest how the ambiguity can be removed.

Differentiate between a decidable and an undecidable problem. State the Halting Problem and explain, with the essential argument, why it is undecidable.

Given the regular grammar with productions $S \rightarrow aA \mid bS \mid \varepsilon$ and $A \rightarrow aS \mid bA$, construct the equivalent finite automaton and describe the language it accepts.

Convert the following context-free grammar into Chomsky Normal Form (CNF): $S \rightarrow ASB \mid \varepsilon$, $A \rightarrow aAS \mid a$, $B \rightarrow SbS \mid A \mid bb$. Show all intermediate steps including removal of $\varepsilon$-productions and unit productions.

Distinguish between recursive (decidable) languages and recursively enumerable languages. Explain why every recursive language is recursively enumerable but the converse is not necessarily true.