Question Paper of CS-73 Theory of Computer Science June 2003

Ql(a). Define the following concepts formally:

(i) Mealy Automation

(ii) Godel number

(iii) Context-free language

(iv) Non-Deterministic Pushdown Automata

(v) Regular Grammar

(vi) Primitive Recursive function

(vii) Non-Deterministic Finite Automata

(viii) Universal Turing Machine

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

(i) Languages accepted by finite automata

(ii) Languages generated by context-free grammars

(iii) Languages accepted by Push-Down Automata

Q2(a). Construct a deterministic finite automata accepting the following set:

(b) Describe informally the language accepted by the Deterministic Finite Automata shown below:

Image No.12

where E denoted initial state and F denotes final state and (a, b) is the set of inputs.

Image No. 13

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

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

Q4. Construct Turing Machines that compute the following function:

(a) f(m,n) = m*n.

Q5. Show that the following function are primitive recursive:

(i)f(m,n)=2m + 3n

Q6. Mention two problems, for each of the following domains, which are undecidable:
(i) Turing Machines

(ii) Context-free Grammars

(iii) Grammars (Non-context-free)