# Compilers Questions and Answers – 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’
2. a) m x 2n
3. b) 2mn
4. c) 2(m+n)
5. 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 is2mn.

1. An FSM with
2. a) M can be transformed to Numeral relabeling its states
3. b) M can be transformed to N, merely relabeling its edges
4. c) Both of the mentioned
5. 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.

1. Which of the following is right?
2. a) A Context free language can be accepted by a deterministic PDA
3. b) union of 2 CFLs is context free
4. c) The intersection of two CFLs is context free
5. 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.

1. Consider the following two statements:

S1: { 02n |n >= l} is a regu1ar language

S2: { 0m 0n 0(m+n) l m >= 1 and n >= 2} is a regu1ar language

Which of the following is true?

1. a) Only S1 is correct
2. b) Only S2 is correct
3. c) Both S1 and S2 are correct
4. 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).

1. Which of the following pairs of regular expressions are equivalent?
2. a) 1(01)* and (10)*1
3. b) x (xx)* and (xx)*x
4. c) x+ and x+ x(*+)
5. 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+

1. 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!

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 e-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 e-moves.

1. 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.

1. Which of the following are not regular?
2. a) String of )’s which has length that is a perfect square
3. b) Palindromes Consisting of 0’s 1’s
4. c) String of 0’s whose length is a prime number
5. 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.

1. 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
2. a) 35
3. b) 360
4. c) 49
5. 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

.

1. Which one of the following statement is FALSE?
2. a) Context-free languages are closed under union
3. b) Context-free languages are closed under concatenation
4. c) Context-free languages are closed under intersection
5. d) Context-free languages are closed under Kleene closure

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

11.A regular expression enables a quick test to determine objects and text strings with undependable values.

1. a) True
2. b) False

Explanation: Because it checks for all the values and determines whether the output string matches with the given string.

12.RE can be used only for values of type string and number.

1. a) True
2. b) False

Explanation: No not for all values the string and numbers can we use the RE.

13.You can use RE, if you expect the value of a property to change in an unpredictable way each time its run.

1. a) True
2. b) False

Explanation: For every cycle the values does not change unpredictably because the type of grammar that it accepts is defined.

14. All ___________ Are automatically treated as regular expressions.

1. a) Programmatic description
2. b) Window
3. c) Win Object
4. d) Collection

Explanation: The programmatic description is genuinely treated as regular expression.

15. If a ‘/’ is used before a character that has no special meaning, ‘/’ is ignored.

1. a) True
2. b) False