Open Mind Tree

1. Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true? (GATE CS 2000)
(a) ScT (S is a subset of T)
(b) TcS (T is a subset of S)
(c) S=T
(d) SnT=Ø

Answer: (c).

2. Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true? (GATE CS 2000)
(a) L = O
(b) L is regular but not O
(c) L is context free but not regular
(d) L is not context free

Answer: (b)
Explanation: Please note that grammar itself is not regular but language L is regular as L can be represented using a regular grammar, for example S -> S00/00.
References:
http://en.wikipedia.org/wiki/Regular_grammar

3. Consider the following two statements:
S1: { 0^2n |n >= l} is a regu1ar language
S2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar language
Which of the following statements is correct? (GATE CS 2001)a) Only S1 is correct
b) Only S2 is correct
c) Both S1 and S2 are correct
d) None of S1 and S2 is correct

Answer: (c)
Explanation:
S1 can be written as (00)^n where n >= 1. And S2 can be written as (00)^(m+n) where m >=2 and n >= 1. S2 can be further reduced to (00)^x where x >= 3.
We can easily write regular grammars for both S1 and S2.
G1 -> G100/00 (For S1)
G2 -> G200/000000 (For S2)

4. Which of the following statements in true? (GATE CS 2001) 
(a) If a language is context free it can always be accepted by a deterministic push-down automaton
(b) The union of two context free languages is context free
(c) The intersection of two context free languages is context free
(d) The complement of a context free language is context free

Answer: (b)
Explanation:
Context-free languages are closed under the following operations. That is, if L and P are context-free languages and D is a regular language, the following languages are context-free as well:
• the Kleene star L * of L
• the image Ø(L) of L under a homomorphism Ø
• the concatenation of L and P
• the union of L and P
• the intersection of L with a regular language D (L n D).
Context-free languages are not closed under complement, intersection, or difference.
Why a) is not true?
The language recognized by deterministic pushdown automaton is deterministic context free language. Not all context-free languages are deterministic. This is unlike the situation for deterministic finite automata, which are also a subset of the nondeterministic finite automata but can recognize the same class of languages (as demonstrated by the subset construction).
References:
http://en.wikipedia.org/wiki/Context-free_language
http://en.wikipedia.org/wiki/Deterministic_pushdown_automaton

5. Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least. (GATE CS 2001)(a) N^2
(b) 2^N
(c) 2N
(d) N!

Answer: (b)