Solved MCQs on Finite Automata

Finite Automata and Regular Expressions-1 This set of Compilers Multiple Choice Questions & Answers (MCQs) focuses on “Finite Aut...

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
View Answer

Answer: b
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
View Answer

Answer: c
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
View Answer

Answer: b
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
View Answer

Answer: c
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
View Answer

Answer: d
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!
View Answer

Answer: b
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
View Answer

Answer: b
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
View Answer

Answer: d
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
View Answer

Answer: b
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
View Answer

Answer: c
Explanation: CFL is closed under Kleene closure, concatenation, and Union