##### MCQ Computer Science

# 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”.

- 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

### 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 is2mn.

- 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

### Answer

Answer: c

Explanation: The Definition of FSM states that M can be transformed to N by relabeling its states or its edges.

- 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

### Answer

Answer: b

Explanation: Context-free languages are closed under the following operations. The Kleene star, the concatenation, the union and the intersection.

- 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?

- 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

### 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).

- 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

### 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+

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

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

- 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

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

- 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

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

- 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

### 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

- 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

### Answer

Answer: c

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.

- a) True
- b) False

### Answer

Answer: a

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.

- a) True
- b) False

### Answer

Answer: b

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.

- a) True
- b) False

### Answer

Answer: b

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.

- a) Programmatic description
- b) Window
- c) Win Object
- d) Collection

### Answer

Answer: a

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.

- a) True
- b) False

### Answer

Answer: a

Explanation: The backslash carries no significance and it is ignored.