# 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

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.

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

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.

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

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.

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

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

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

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+

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

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

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

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

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

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.

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

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.

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

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

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

View Answer

S → SaSbS|Îµ

a) aabb

b) abab

c) aababb

d) aaabbb

View Answer

Answer: d

Explanation:

S->aSbS putting S-> € and then S->SaSbS

S->aSaSaSbSbSbS putting S->SaSbS

S->aaabbb putting S->€.

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

View Answer

a) True

b) False

View Answer

Answer: b

Explanation: RE is used for all types of string and numbers.

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) &

View Answer

a) x

b) #

c) *

d) &

View Answer

Answer: c

Explanation: Zero or Specific Expression matching can be done only by a single character that is*.

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

View Answer

a) Programmatic description

b) Window

c) Win Object

d) Collection

View Answer

Answer: a

Explanation: It is seen that programmatic description are treated as regular expression.

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

View Answer

a) True

b) False

View Answer

Answer: a

Explanation: XML checkpoints employ RE.

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

View Answer

a) Type-3 grammar

b) Type-2 grammar

c) Type-1 grammar

d) Type-0 grammar

View Answer

Answer: b

Explanation: As per the definition of type-2 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}

View Answer

a) {xy,xy}

b) {xx,xy,yx,yy}

c) {x,y}

d) {x,y,xy}

View Answer

Answer: b

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.

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}

View Answer

a) {x,y}

b) {xy}

c) {x}

d) {y}

View Answer

Answer: a

Explanation: Because either x or y can be selected.

Explanation: Because either x or y can be selected.

9. The regular expressions denote zero or more instances of an x or y is

a) (x+y)

b) (x+y)*

c) (x* + y)

d) (xy)*

View Answer

a) (x+y)

b) (x+y)*

c) (x* + y)

d) (xy)*

View Answer

Answer: b

Explanation: For instances of x or y the exp is x+y and both can zero or more times than (x+y)*.

Explanation: For instances of x or y the exp is x+y and both can zero or more times than (x+y)*.