# Finite Automata and Regular Expressions-1

This set of Compilers Multiple Choice Questions & Answers (MCQs) focuses on “Finite Automata and Regular Expressions”.
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 2^n
b) 2^mn
c) 2^(m+n)
d) All of the mentioned
Explanation: For every Data here length is n and memory’s state is defined in terms of power of 2, Here the total memory capability for all the words = mn Hence the number of states is2^mn.
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
Explanation: The Definition of FSM states that M can be transformed to N by relabeling its states or its edges.
3. Which of the following is right?
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
Explanation: Context-free languages are closed under the following operations. The Kleene star, the concatenation, the union and the intersection.
4. 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 is true?
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
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. SO we can write regular grammars for both
G1 -> G100/00 (For S1)
G2 -> G200/000000 (For S2).
5. 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
Explanation:
Rule (pq)*p=p (qp)*
Therefore–(xx^*) (x*x**)
(xx*)(x*x*) [Using x**=x] (xx*)(x*) [Using x*x*=x*] (xx*) [Using x*xx*=x*)
x+
6. Given a NFA with N states, the maximum number of states in an equivalent minimized DFA is at least.
(a) N^2
(b) 2^N
(c) 2N
(d) N!
Explanation: The initial state of the DFA constructed from this NFA is the set of all NFA states that are reachable from state 1 by ε-moves; that is, it is the set {1, 2, and 3}. A transition from states1, 2, and 3 by input symbol 0 must follow either the arrow from state 1 to 2, or from state 3 to 4. Also, neither state 2 nor 4 have outgoing ε-moves.
7. 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
Explanation: The grammar itself is not regular but language L is regular as L can be represented using a regular grammar, for example S -> S00/00.
8. 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
Explanation: Strings of odd number of zeroes can be generated by the regular expression (00) *0.Pumping lemma can be used to prove the non-regularity of the other options.
9. 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
Explanation: Here string length is 4 so we create string of length 4 by 6 values firstly we arrange any value by 6 methods. Then Remaining numbers are 5 so we can arrange them by 5 methods then remaining numbers are 4 so we arrange them by 4 methods and then 3.Thus 6*5*4*3=360.
10. 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
Explanation: CFL is closed under Kleene closure, concatenation, and Union

# Finite Automata and Regular Expressions-2

This set of Compilers Interview Questions and Answers focuses on “Finite Automata and Regular Expressions – 2”.
1. Which of the following strings is not generated by the following grammar?
S → SaSbS|ε
a) aabb
b) abab
c) aababb
d) aaabbb
Explanation:
S->aSbS putting S-> € and then S->SaSbS
S->aSaSaSbSbSbS putting S->SaSbS
S->aaabbb putting S->€.
2. Regular expressions can be used only for values of type string and number.
a) True
b) False
Explanation: RE is used for all types of string and numbers.
3. What is the Regular Expression Matching Zero or More Specific Characters
a) x
b) #
c) *
d) &
Explanation: Zero or Specific Expression matching can be done only by a single character that is*.
4. All…….. are automatically treated as regular expressions.
a) Programmatic description
b) Window
c) Win Object
d) Collection
Explanation: It is seen that programmatic description are treated as regular expression.
5. Regular Expressions can be used with XML checkpoints.
a) True
b) False
Explanation: XML checkpoints employ RE.
6. The production Grammar is {S->aSbb,S->abb} is
a) Type-3 grammar
b) Type-2 grammar
c) Type-1 grammar
d) Type-0 grammar
Explanation: As per the definition of type-2 grammar.
7. Regular expression (x/y)(x/y) denotes the set
a) {xy,xy}
b) {xx,xy,yx,yy}
c) {x,y}
d) {x,y,xy}
Explanation: From first part if we take x then from the latter part x then it forms xx
From first part if we take x then from the latter part y then it forms xy
From first part if we take y then from the latter part x then it forms yx
From first part if we take y then from the latter part y then it forms yy.
8. Regular expression x/y denotes the set
a) {x,y}
b) {xy}
c) {x}
d) {y}