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?
A. 
B. 
C. 
D. 
2.
Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?
A. 
B. 
C. 
L is context free but not regular
D. 
3.
Consider the following two statements:S1: { 0^2n |n >= l} is a regu1ar languageS2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar languageWhich of the following statements is correct?
A. 
B. 
C. 
Both S1 and S2 are correct
D. 
None of S1 and S2 is correct
4.
Which of the following statements in true?
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
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.
A. 
B. 
C. 
D. 
6.
Let L={w (0 + 1)*|w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?
A. 
B. 
C. 
D. 
7.
Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
A. 
L2 – L1 is recursively enumerable.
B. 
L1 – L3 is recursively enumberable
C. 
L2 \cap L1 is recursively enumberable
D. 
L2 \cup L1 is recursively enumberable
8.
Consider the languages L1={|i != j}, L2={|i = j}, L3 = {|i = 2j+1}, L4 = {|i != 2j}. Which one of the following statements is true?
A. 
B. 
Only L2 and L3 are context free
C. 
Only L1 and L2 are context free
D. 
9.
Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?
A. 
B. 
C. 
D. 
10.
Given the language L = {ab, aa, baa}, whih of the following strings are in L*?….1) abaabaaabaa….2) aaaabaaaa….3) baaaaabaaaab….4) baaaaabaa
A. 
B. 
C. 
D. 
11.
Which of the following problems are decidable?….1) Does a given program ever produce an output?….2) If L is a context-free language, then is L’ (complement of L) also context-free?….3) If L is a regular language, then is L’ also regular?….4) If L is a recursive language, then, is L’ also recursive?
A. 
B. 
C. 
D. 
12.
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. 
B. 
C. 
D. 
13.
Consider the language L1,L2,L3 as given below.L1={ | p,q N}L2={ | p,q N and p=q}L3={ | 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. 
C. 
All the three languages are context free
D. 
Turing machine can be used to recognize all the three languages
14.
S –> aSa| bSb| a| b ;The language generated by the above grammar over the alphabet {a,b} is the set of
A. 
B. 
All odd length palindromes.
C. 
Strings that begin and end with the same symbol
D. 
All even length palindromes.
15.
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.
16.
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.
17.
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. 
B. 
C. 
D. 
18.
How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?
A. 
B. 
C. 
D. 
19.
Which of the following is true?
A. 
B. 
(0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)*
C. 
(0+1)*01(0+1)*+1*0* = (0+1)*
D. 
20.
A language is regular if and only if
A. 
B. 
C. 
D. 
Accepted by Turing machine
21.
Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then
A. 
B. 
C. 
D. 
22.
Which of the following is not a regular expression?
A. 
B. 
C. 
D. 
23.
Regular expression are
A. 
B. 
C. 
D. 
24.
Which of the following is true?
A. 
Every subset of a regular set is regular
B. 
Every finite subset of non-regular set is regular
C. 
The union of two non regular set is not regular
D. 
Infinite union of finite set is regular
25.
L and ~L are recursive enumerable then L is
A. 
B. 
C. 
D.