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 = {ambmcanbn | m, n >= 0 }
L2 = {aibjck | 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 = {akbkc | 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 {pnqn|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={0p1q | p,q ∈ N}
L2={0p1q| p,q ∈ N and p=q}
L3={0p1q0r | 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= { ank | 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) 2n+1
(D) 2k+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.


9. Assume the statements S1 and S2 given as :
S1 : Given a context free grammarG, there exists an algorithm for determining whether L(G) is infinite.
S2 : There exists an algorithm to determine whether two context free grammars generate the same language.
Which of the following is true ?
A. S1 is correct and S2 is not correct.
B. Both S1 and S2 are correct.
C. Both S1 and S2 are not correct.
D. S1 is not correct and S2 is correct.
10. The number of eight-bit strings beginning with either 111 or 101 is ______.
A. 64
B. 128
C. 265
D. None of the above
11. Which of the following conversion is not possible (algorithmically)?
A. regular grammar to context-free grammar
B. nondeterministic FSA to deterministic FSA
C. nondeterministic PDA to deterministic PDA
D. nondeterministic TM to deterministic TM
12. Regular expression for the language L = { w ∈ {0, 1}* | w has no pair of consecutive zeros} is
A. (1 + 010)*
B. (01 + 10)*
C. (1 + 010)* (0 + λ)
D. (1 + 01)* (0 + λ)
13. Recursively enumerable languages are not closed under:
A. Union
B. Intersection
C. Complementation
D. Concatenation
14. Grammar that produce more than one Parse tree for same sentence is:
A. Ambiguous
B. Unambiguous
C. Complementation
D. Concatenation Intersection
15. The finite automata accept the following language:
A. context free language
B. regular language
C. context sensitive language
D. all of the above
16. Write regular expression to denote a language L which accepts all the strings which begin or end with either 00 or 11
A. [(00(0+1)* 11] + [11( 0 + 1)* 00]
B. [(00+11) (0+1)+] + [( 0 + 1)+ (00+11)].
C. [(00+11) (0+1)*] + [( 0 + 1)* (00+11)]
D. (00+11) (0+1)* (00+11).
17. Write the regular expression to denote the language L over ? ={ a,b} such that all the string do not contain the substring “ ab”.
A. a*b*
B. b*a*
C. (ab)*
D. (ba)*
18. Recognize the CFL for the given CFG.
S-> aB| bA, 
A-> a|aS|bAA, 
B-> b|bS|aBB
A. strings contain equal number of a’s and equal number of b’s.
B. strings contain odd number of a’s and odd number of b’s.
C. strings contain odd number of a’s and even number of b’s.
D. strings contain even number of a’s and even number of b’s.