1) S –> aSa| bSb| a| b ;The language generated by the above grammar over the alphabet {a,b} is the set of
(A) All palindromes.
(B) All odd length palindromes.
(C) Strings that begin and end with the same symbol
(D) All even length palindromes.

Answer (B)
The strings accepted by language are {a, b, aaa, bbb, aba, bab, ..}. All of these strings are odd length palindromes.

2) Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?
(A) The set of all strings containing the substring 00.
(B) The set of all strings containing at most two 0’s.
(C) The set of all strings containing at least two 0’s.
(D) The set of all strings that begin and end with either 0 or 1.

Answer (C)
The regular expression has two 0’s surrounded by (0+1)* which means accepted strings must have at least 2 0’s.

3) Which one of the following is FALSE?
(A) There is unique minimal DFA for every regular language
(B) Every NFA can be converted to an equivalent PDA.
(C) Complement of every context-free language is recursive.
(D) Every nondeterministic PDA can be converted to an equivalent deterministic PDA.

Answer (D)
Deterministic PDA cannot handle languages or grammars with ambiguity, but NDPDA can handle languages with ambiguity and any context-free grammar. So every nondeterministic PDA can not be converted to an equivalent deterministic PDA.

4) Match all items in Group 1 with correct options from those given in Group 2.

Group 1                          Group 2
P. Regular expression        1. Syntax analysis
Q. Pushdown automata         2. Code generation
R. Dataflow analysis         3. Lexical analysis
S. Register allocation       4. Code optimization

(A) P-4. Q-1, R-2, S-3
(B) P-3, Q-1, R-4, S-2
(C) P-3, Q-4, R-1, S-2
(D) P-2, Q-1, R-4, S-3

Answer (B)

5) . Let L = L1 ∩ L2, where L1 and L2 are languages as defined below:
L1 = {a^mb^mcaⁿbⁿ | m, n >= 0 }
L2 = {aⁱb^jc^k | i, j, k >= 0 }
Then L is
(A) Not recursive
(B) Regular
(C) Context free but not regular
(D) Recursively enumerable but not context free.

Answer (C)
The language L1 accept strings {c, abc, abcab, aabbcab, aabbcaabb, …} and L2 accept strings {a, b, c, ab, abc, aabc, aabbc, … }. Intersection of these two languages is L1 ∩L2 = {a^kb^kc | k >= 0} which is context free, but not regular.

8) Let P be a regular language and Q be context-free language such that Q ⊆ P. (For example, let P be the language represented by the regular expression p*q* and Q be {pⁿqⁿ|n ∈ N}). Then which of the following is ALWAYS regular?
(A) P ∩ Q
(B) P – Q
(C) ∑* – P
(D) ∑* – Q

Answer (C)
The expression ∑* – P represents complement of P which is a regular language. Complement of Regular languages is also regular. Then a DFA that accepts the complement of L, i.e. ∑* – L, can be obtained by swapping its accepting states with its non-accepting states.

7) Consider the language L1,L2,L3 as given below.
L1={0^p1^q | p,q ∈ N}
L2={0^p1^q| p,q ∈ N and p=q}
L3={0^p1^q0^r | p,q,r ∈N and p=q=r}
Which of the following statements is NOT TRUE?
(A) Push Down Automata (PDA) can be used to recognize L1 and L2
(B) L1 is a regular language
(C) All the three languages are context free
(D) Turing machine can be used to recognize all the three languages

Answer (C)
The language L3 is not context free. Refer this for more details.

6. Definition of a language L with alphabet {a} is given as following. L= { a^nk | k > 0, and n is a positive integer constant} What is the minimum number of states needed in a DFA to recognize L?
(A) k+1
(B) n+1
(C) 2ⁿ⁺¹
(D) 2^k+1

Answer (B)
Note that n is a constant and k is any positive integer. For example, if n is given as 3, then the DFA must be able to accept 3a, 6a, 9a, 12a, .. To build such a DFA, we need 4 states.

ANSWER IS A