First the year in which the question appears would be mentioned followed by the question and its answer.

**DECEMBER 2004**

1. The context-free languages are closed for :

(i) Intersection (ii) Union

(iii) Complementation (iv) Kleene Star

then

(A) (i) and (iv) (B) (i) and (iii)

(C ) (ii) and (iv) (D) (ii) and (iii)

**Ans:-C**

**Explanation:-**
Context-free languages are closed under union,intersection and star-closure. Context-free languages are not closed under intersection and complementation.

**June - 2005**

2. Which of the following is not true ?

(A) Power of deterministic automata is equivalent to power of non-deterministic
automata.

(B) Power of deterministic pushdown automata is equivalent to power of
non-deterministic pushdown automata.

(C) Power of deterministic turing machine is equivalent to power of non-deterministic

turing machine.
(D) All the above

**Ans:-B**

**Explanation:-**
Deterministic and nondeterministic finite automata have equivalent computational capabilities.

Deterministic and nondeterministic Turing machines have the same computational capabilities.

However, the computational capabilities of deterministic push-down automata are less than those of nondeterministic push-down automata. So, the answer is B.

3. Identify the language which is not context - free.

(A) L={wwR|w is a member of {0,1}*}

(B) L={a

^{n}b

^{n}|n>=0}

(C )L={ww|w is a member of {0,1}*}

(D) L={a

^{n}b

^{m}c

^{m}d

^{n}|n,m>=0}

**Ans:-B**

**December 2005**

4. Which sentence can be generated by S → d/bA, A → d/ccA :

(A) bccddd

(B) aabccd

(C) ababccd

(D) abbbd

**Ans:-A**

**Explanation:-**
The most closest answer seems to be A only. The terminals in the grammar are d,b and c. There is no terminal 'a' at all. So the options B,C and D are ruled out. option A can also be derived at something like this.

S->bA

->bccA

->bccccA

->bccccd

So the sentence generated should be bccccd. If there are any other explanations for the same please post them.

5. Regular expression a+b denotes the set :

(A) {a}

(B) {Epsilon, a, b}

(C) {a, b}

(D) None of these

**Ans:-C**

**June 2006**

S → OA, A → 1A/0A/1

(A) 01100

(B) 00101

(C ) 10011

(D) 11111

**Ans:-B**

**Explanation:-**
Non terminals in the above grammar are S, and A. Terminals are 0 and 1. The start symbol of the grammar is S.
S->0A. So rule out strings beginning with 1. so that leaves us with two options A and B.
S->0A

->00A

->001A

->0010A

->00101

So the option B is correct. If you try to derive the string for option A you would not be able to get it. So, the correct answer is option A.

7. The logic of pumping lemma is a good example of :

(A) pigeon hole principle

(B) recursion

(C) divide and conquer technique

(D) iteration

**Ans:-A**

**December - 2006**

8. Which of the regular expressions corresponds to this grammar ? S → AB/AS, A → a/aA, B → b

(A) aa*b+

(B) aa*b

(C ) (ab)*

(D) a(ab)*

**Ans:-B**

**JUNE 2007**

9. The regular expression given below describes :

r=(1+01)*(0+λ)

(A) Set of all string not containing '11'

(B) Set of all string not containing '00'

(C) Set of all string containing '01'

(D) Set of all string ending in '0'

**Ans:-B**

**Explanation:-**

The meaning of (1+01)* means that the set of strings of 1 and 01 of any length including the NULL string. (0+λ) means either 0 or λ. So the full regular expression stands for the set of strings of 1's and 01's of any length ending with 0 or λ. So we cannot say the string will only end in '0'. It could end in λ also. The string can begin with 1 or 01 and multiple times it can get repeated.But the string '11' cannot be together. So the option could be B.