1.

Number of states of FSM required to simulate behaviour of a computer with a

memory capable of storing “m” words, each of length ‘n’.
a) m x 2n
b) 2mn
c) 2(m+n)
d) all of the mentioned
2. An FSM with __________
a) M can be transformed to Numeral relabeling its states
b) M can be transformed to N, merely relabeling its edges
c) Both of the mentioned
d) None of the mentioned
3. Which of the following statement is correct?
a) A Context free language can be accepted by a deterministic PDA
b) union of 2 CFLs is context free
c) The intersection of two CFLs is context free
d) The complement of CFLs is context free
4. Which of the following pairs of regular expressions are equivalent?
a) 1(01)* and (10)*1
b) x (xx)* and (xx)*x
c) x+ and x+ x(*+)
d) All of the mentioned
5. Given a NFA with N states, the maximum number of states in an equivalent
minimized DFA is at least.
a) N2
b) 2N
c) 2N
d) N!
6. Let L denotes the language generated by the grammar S – OSO/00. Which of the
following is true?
a) L = O
b) L is regular but not O
c) L is context free but not regular
d) L is not context free
7. Which of the following are not regular?
a) String of )’s which has length that is a perfect square
b) Palindromes Consisting of 0’s 1’s
c) String of 0’s whose length is a prime number
d) All of the mentioned
8. If ∑ = {a, b, c, d, e, f} then number of strings in ∑ of length 4 such that no symbol
is used more than once in a string is
a) 35
b) 360
c) 49
d) 720
9. Which one of the following statement is FALSE?
a) Context-free languages are closed under union
b) Context-free languages are closed under concatenation
c) Context-free languages are closed under intersection
d) Context-free languages are closed under Kleene closure
10. What is the Regular Expression Matching Zero or More Specific Characters?
a) x
b) #
c) *
d) &
11. All __________ are automatically treated as regular expressions.
a) Programmatic description
b) Window
c) Win Object
d) Collection
12. The production Grammar is {S->aSbb,S->abb} is __________ grammar.
a) Type-3
b) Type-2
c) Type-1
d) Type-0
13. Regular expression (x/y)(x/y) denotes which of the following set?
a) {xy,xy}
b) {xx,xy,yx,yy}
c) {x,y}
d) {x,y,xy}
14. Regular expression x/y denotes which of the following set?
a) {x,y}
b) {xy}
c) {x}
d) {y}
15. A system program that combines separately compiled modules of a program
into a form suitable for execution is called ___________
 a) Assembler
b) Linking loader
c) Cross compiler
d) None of the mentioned
16. A compiler for a high-level language that runs on one machine and produces
code for a different machine is called ___________
a) Optimizing compiler
b) One pass compiler
c) Cross compiler
d) Multipass compiler
17. The __________ is a technique for building cross compilers for other machines.
a) Brazilian Cross
b) Canadian Cross
c) Mexican Cross
d) X-cross
18.  __________ was developed from the beginning as a cross compiler.
a) Free Pascal
b) GCC
c) Pascal
d) None of the mentioned
19. If we compile the sam.c file with the command “gcc -o samsam.c”, then the
executable file will be?
a) a.out
b) sam
c) sam.out
d) None of the mentioned
20. What is the output of lexical analyzer?
a) A set of RE
b) Syntax Tree
c) Set of Tokens
d) String Character
21. Which symbol table implementation is based on the property of locality of
reference?
a) Linear list
b) Search tree
c) Hash Table
d) Self Organisation
22. Which of the following is true for operator precedence parsing?
a) For all pair of non-terminal
b) For all pair of non-terminals
c) To delimit the handle
d) None of the mentioned
23. What is an Object program?
a) Program written in machine language
b) Program to be translated into machine language
c) Translation of high-level language into machine language
d) None of the mentioned
24. Which concept of FSA is used in the compiler?
a) Lexical analysis
b) Parser
c) Code generation
d) Code optimization
25. Which concept of grammar is used in the compiler?
a) Lexical analysis
b) Parser
c) Code generation
d) Code optimization
26. Which of the following are Lexemes?
a) Identifiers
b) Constants
c) Keywords
d) All of the mentioned
27. Parsing is also known as ________
a) Lexical Analysis
b) Syntax Analysis
c) Semantic Analysis
d) Code Generation
28. System program such a compiler are designed so that they are ________
a) Re-enterable
b) Non-Usable
c) Serially usable
d) None of the mentioned
29. Which of the following is not a feature of compiler?
a) Scan the entire program first and translate into machine code
b) To remove syntax errors
 c) Slow for debugging
d) Execution time is more
30. A system program that brings together separately compiled modules of a
program into a form language that is suitable for execution.
a) Assembler
b) Linking loader
c) Cross compiler
d) None of the mentioned
31. A programmer by mistakes writes a program to multiply two numbers instead of
dividing them, how can this error be detected?
a) Compiler
b) Interpreter
c) Compiler or interpreter
d) None of the mentioned
32. The regular expression denotes a language comprising all possible strings of
even length over the alphabet (0, 1).
a) 1 + 0(1+0)*
b) (0+1) (1+0)*
c) (1+0)
d) (00+0111+10)*
33. The RE gives none or many instances of an x or y is?
a) (x+y)
b) (x+y)*
c) (x* + y)
d) (xy)*
34. The RE in which any number of 0′s is followed by any number of 1′s followed by
any number of 2′s is?
a) (0+1+2)*
b) 0*1*2*
c) 0* + 1 + 2
d) (0+1)*2*
35. The regular expression have all strings of 0′s and 1′s with no two consecutive 0′s
is?
a) (0+1)
b) (0+1)*
c) (0+∈) (1+10)*
d) (0+1)* 011
36. Which of the following is NOT the set of regular expression R = (ab + abb)*bbab?
a) ababbbbab
b) abbbab
c) ababbabbbab
d) abababab
37. Consider the production of the grammar S->AA A->aa A->bb Describe the
language specified by the production grammar.
a) L = {aaaa,aabb,bbaa,bbbb}
b) L = {abab,abaa,aaab,baaa}
c) L = {aaab,baba,bbaa,bbbb}
d) L = {aaaa,abab,bbaa,aaab}
38. If R is regular language and Q is any language (regular/ non regular), then Pref (Q
in R) is _____________
a) Non-regular
b) Equal
c) Infinite
d) Regular
39. (a,b) what is a?
a) Domain
b) Range
c) Domain & Range
d) None of the mentioned
40. (a,b) what is b?
a) Domain
b) Range
c) Domain & Range
d) None of the mentioned
41. The smallest set A such that A ∪ {1, 2} = {1, 2, 3, 5, 9} is?
a) {2,3,5}
b) {1, 2, 5, 9}
c) {3, 5, 9}
d) None of the mentioned
42. If A ∩ B = B, then?
a) A ⊂ B
b) A = ø
c) B ⊂ A
d) B = ø
43. Empty set is a _____________
a) Invalid set
b) Infinite set
c) Finite set
d) None of the mentioned
44. If A, B and C are any three sets, then A – (B ∪ C) is equal to _____________
a) (A – B) ∪ (A – C)
b) (A – B) ∪ C
c) (A – B) ∩ (A – C)
d) (A – B) ∩ C
45. If A, B, C be three sets such that A ∪ B = A ∪ C and A ∩ B = A ∩ C, then?
a) A=B
b) A=C
c) B=C
d) A=B=C
46. The number of proper subsets of the set {1, 2, and 3} is?
a) 8
b) 6
c) 7
d) 5
47. If A and B are any two sets, then A ∪ (A ∩ B) is equal to _____________
a) A
b) B
c) A^C
d) B^C
48. If A, B and C are any three sets, then A × (B ∪ C) is equal to _____________
a) (A × B) ∪ (A × C)
b) (A × B) ∩ (A × C)
c) (A ∪ B) × (A ∪ C)
d) None of the mentioned
49. A language L from a grammar G = { VN, Σ, P, S} is?
a) Set of symbols over VN
b) Set of symbols over Σ
c) Set of symbols over P
d) Set of symbols over S
50. What is the transitional function of a DFA?
a) Q X Σ→Q
b) Q X Σ→2Q
 c) Q X Σ→2n
d) Q X Σ→Qn
51. What is the transitional function of an NFA?
a) Q X Σ→Q
b) Q X Σ→2Q
c) Q X Σ→2n
d) Q X Σ→Qn
52. Maximum number of states of a DFA converted from an NFA with nstates is?
a) n
b) n2
c) 2n
d) None of the mentioned
53. What are the basic limitations of finite state machine?
a) It cannot remember arbitrarily large amount of information
b) In cannot remember state transitions
c) In cannot remember grammar for a language
d) It cannot remember language generated from a grammar
54. The string WWR is not recognized by any FSM because _____________
a) An FSM cannot remember arbitrarily large amount of information
b) An FSM cannot fix the midpoint
c) An FSM cannot match W with WR
d) An FSM cannot remember first and last inputs
55. A finite automata recognizes ____________
a) Any Language
b) Context Sensitive Language
c) Context Free Language
d) Regular Language
56. Which of the following statement is true for Dead State?
a) It cannot be reached anytime
b) There is no necessity of the state
c) If control enters no way to come out from the state
d) If control enters FA deads
57. sWhich of the following statement is true for Moore Machine?
a) Output depends on present state
b) Output depends on present input
c) Output depends on present state and present input
d) Output depends on present state and past input
58. Which of the following statement is true for Mealy Machine?
a) Output depends on present state
b) Output depends on present input
c) Output depends on present state and present input
d) Output depends on present state and past input
59. Which is true for in accessible state?
a) It cannot be reached anytime
b) There is no necessity of the state
c) If control enters no way to come out from the state
d) If control enters FA deads
60. In Mealy Machine O/P is associated with ____________
a) Present state
b) Next state
c) Input
d) None of the mentioned
61.  In Moore Machine O/P is associated with ____________
a) Present state
b) Next state
c) Input
d) None of the mentioned
62. Which type of string is accepted by the following finite automata?
a) All string
b) Null string
c) No string
d) None of the mentioned
63. Myhill-Nerode Theorem is used for __________
a) Minimization of DFA
b) Maximization of NFA
c) Conversion of NFA
d) Conversion of DFA
64. NDFAs where introduced by ____________
a) Michael O Rabin & Dana Scott
b) Dan Brown
c) Sun micro system Labs
d) SAP Labs
65. The regular languages are not closed under ___________
a) Concatenation
b) Union
 c) Kleene star
d) Complement
66. Conversion of a DFA to an NFA __________
a) Is impossible
b) Requires the subset construction
c) Is Chancy
d) Is nondeterministic
67. A regular language corresponds to __________
a) An alphabet
b) Set of strings over an alphabet
c) A DFA only
d) A DFA or an NFA
68. An NFA may be converted to a DFA using __________
a) Induction
b) A construction
c) Contradiction
d) Compilation
69. The subset construction shows that every NFA accepts a __________
a) String
b) Function
c) Regular language
d) Context-free language
70. Which is the application of NFA?
a) A regular language is produced by union of two regular languages
b) The concatenation of two regular languages is regular
c) The Kleene closure of a regular language is regular
d) All of the mentioned
71. Find the wrong statement?
a) The language accepted by finite automata are the languages denoted by
regular expression
b) Every DFA has a regular expression denoting its language
c) For a regular expression r, there does not exists NDFA with L® ant transit that
accept
d) None of the mentioned
72. Which behaviour of a NFA can be stimulated by DFA?
a) Always
b) Sometimes
 c) Never
d) Depends on NFA
73. What is the relation between NFA-accepted languages and DFA accepted
languages?
a) >
b) <
c) =
d) <=
74.  In regular expressions, the operator ‘*’ stands for?
a) Concatenation
b) Selection
c) Iteration
d) Addition
75. The lexical analysis for a modern language such as Java needs the power of
which one of the following machine models in a necessary and sufficient sense?
a) Finite state automata
b) Deterministic pushdown automata
c) Non-deterministic pushdown automata
d) Turing machine
76. What is the complement of the language accepted by the NFA shown below?
Assume ∑ = {a} and ε is the empty string.

a) Φ
b) ε
c) a
d) {a, ε}
77. The 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
78. S –>aSa| bSb| a| b; the language generated by the above grammar is the set of
____________
 a) All palindromes
b) All odd length palindromes
c) Strings beginning and ending with the same symbol
d) All even length palindromes
79. Which of the following CFG’s can’t be simulated by an FSM?
a) S->Sa/b
b) S->aSb/ab
c) S->abX, X->cY, Y->d/aX
d) None of the mentioned
80. The transitions which does not take an input symbol are called ___________
a) ε-transitions
b) λ-transitions
c) ε-transitions & λ-transitions
d) none of the mentioned
81. Which of the following is a correct statement?
a) { If an bn | n = 0,1, 2, 3 ..} is regular language
b) Strings with equal number of a’s and b’s denies a regular language
c) L (A* B*)∩ B gives the set A
d) None of the mentioned
82. Which of the following strings is NOT in the Kleene star of the language {011, 10,
110}?
a) 01
b) 10
c) 110
d) 10011101
83. Which grammar is not regular?
a) 0^n
b) 0^n 1^n n
c) 0^m 0^n n
d) 0^n 0^n n
84.  If is a language, and is a symbol, then, the quotient of and, is the set of strings
such that is in: is in. Suppose is regular, which of the following statements is
true?
a) L/a is always a regular language
b) L/a is not a regular language
c) All of the mentioned
d) None of the mentioned
85. Here is a context-free grammar G: S → AB A → 0A1 | 2 B → 1B | 3A which of the
following strings are in L (G)?
a) 021300211
b) 022111300211
c) None of the mentioned
d) 021300211 & 022111300211
86. The grammar G: S → SS | a | b is ambiguous. Check all and only the strings that
have exactly two leftmost derivations in G.
a) bbb
b) ab
c) All of the mentioned
d) None of the mentioned
87.  For the following grammar: S → A | B | 2 A → C0 | D B → C1 | E C → D | E | 3 D
→ E0 | S E → D1 | S Identify all the unit pairs.
a) D,C
b) A,B
c) B,C
d) A,C
88. _________an IR-to-IR transformer that tries to improve the IR program in some
way.
a) Optimizer
b) Parser
c) All of the mentioned
d) None of the mentioned
89. _________ a phase of a compiler that maps the IR program into the instruction set
and the finite resources of the target machine.
a) Optimizer
b) Parser
c) Optimizer & Parser
d) None of the mentioned
90. Consider the languages L1 = and L2 = {a}. Which one of the following represents
L1 L2* U L1*?
a) €
b) a*
c) All of the mentioned
d) None of the mentioned
91. W hat is the complement of the language accepted by the NFA shown below?

a) A,B
b) B
c) C
d) D,C
92. Let w be any string of length n is {0,1}*. Let L be the set of all substring of w.
State the minimum number of states in a NDFA that accepts L?

a) n – 1
b) n
c) n + 1
d) 2n – 1
93. Which one of the following is FALSE?
a) Every NFA can be converted to DFA
b) Every subset of a recursively enumerable set is recursive
c) All of the mentioned
d) None of the mentioned
94. Which one of the following is TRUE?
a) The language L={a^nb^n |n>0 } is regular
b) The language L={a^n |n is prime } is regular
c) The language L={w|w has 3k+1 b’s for some k } is regular
d) None of the mentioned
95. Let L1 = {w ∈ {0,1}∗ | w has at least as many occurrences of (110)’s as (011)’s}.
Let L2 = { ∈ {0,1}∗ | w has at least as many occurrences of (000)’s as (111)’s}.
Which one of the following is TRUE?
a) L1 is regular but not L2
b) L2 is regular
c) L1 and L2 are regular
d) Neither of them are regular
96. The length of the shortest string NOT in the language (over Σ = {a, b}) of the
following regular expression is _____________
 a*b*(ba)*a*
a) 2
b) 3
c) 4
d) 5
97. Consider the following deterministic finite state automaton M.

S denotes the set of seven bit in which the 1st ,4th and last bits are 1. The
number of strings that are accepted by M is
a) 1
b) 5
c) 7
d) 8
98.  L1 is accepted by the NFA, obtained by changing the accepting state of M to a
non-accepting state and vice versa. Which of the following statements is true?

a) L1 = {0, 1}* – L
b) L1 = {0, 1}* – L
c) L1 ⊆ L
d) L1=L
99. 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) N2
b) 2N
c) 2N
d) N!
100. What can be said about a regular language L over {a} whose minimal
finite state automaton has two states?
 a) L must be {an| n is odd}
b) L must be {an| n is even}
c) L must be {an| n is even}
d) Either L must be {an | n is odd}, or L must be {an | n is even}
101. How many minimum states are required to find whether a string has odd
number of 0’s or not?
a) 1
b) 2
c) 3
d) 4
102. The number of states in DFA that accepts the language L(M) ∩ L(N) is
_________

a) 0
b) 1
c) 2
d) 3
103. Which of the following is not regular?
a) String whose length is perfect square and consists of 0s
b) Palindromes consisting of 0’s and 1’s
c) String whose length is perfect square and consists of 0s & Palindromes
consisting of 0’s and 1’s
d) None of the mentioned
104. Which of the following pairs of regular expression are equivalent?
a) 1(01)* and (10)*1
b) X(xx)* and (xx)*x
c) 1(01)* and (10)*1 & X(xx)* and (xx)*x
d) None of the mentioned