Quastione Paper of CS-73:Theory of Computer Science Dec-2001

Ql(a). Define the following concepts formally:
(i) Deterministic Finite Automata

(ii) Regular Grammar

(iii) Context free language

(iv) Non-Deterministic Pushdown Automata .

(v) Turing Machine

(vi) Primitive Recursive function

(b) State the operations under which each of the following class of languages are closed:

(i) Regular languages

(ii) Languages generated by context free grammers.

(iii) Languages accepted by Turing machines.

© State the relation between regular languages and finite automata.

Q2(a). Construct Deterministic Finite Automata accepting the following language:

{w e {a,b} * : each b is immediately preceded and immediately followed by an a}

(b) Describe the language accepted by the Deterministic Finite Automata shown below, infomally

Image No. 12

where F denotes the initial state which is also the final state. E is another state. Also {a, b} is the set of inputs.

Q3. Construct one grammer for each of the following languages:

(a) w e {a,b} * w has twice as many b’s as a’s}

(b)wwR:we{a,b}*}

Q4. Construct Turing Machines that compute the following function:

(a) li(m, n) = m - n.

(b)II(ni,n) = m*n.

Q5(a). In context of primitive recursive functions, state the initial functions and rules of primitive recursion and composition.

Initial function

(b) Show that the product function f(m, n) = m*n is primitive recursive.

Q6. Mention two problems from each of the following domains, which are undecidable:

(1) Context-free Grammars

(2) Grammars (non-context-free)

(3) Turing Machine