# Compilers Questions and Answers – Finite Automata and Regular Expressions – 2

This set of Compilers Interview Questions and Answers focuses on “Finite Automata and Regular Expressions – 2”.

- Which of the following strings is not generated by the following grammar?

S ? SaSbS|e

- a) aabb
- b) abab
- c) aababb
- d) aaabbb

### “Answer

Answer: d

Explanation:

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

S->aSaSaSbSbSbS putting S->SaSbS

S->aaabbb putting S->€.

- Regular expressions can be used only for values of type string and number.
- a) True
- b) False

### Answer

Answer: b

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

- What is the Regular Expression Matching Zero or More Specific Characters
- a) x
- b) #
- c) *
- d) &

### Answer

Answer: c

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

- All __________ are automatically treated as regular expressions.
- a) Programmatic description
- b) Window
- c) Win Object
- d) Collection

### “Answer

Answer: a

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

- Regular Expressions can be used with XML checkpoints.
- a) True
- b) False

### Answer

Answer: a

Explanation: XML checkpoints employ RE.

- 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

### Answer

Answer: b

Explanation: As per the definition of type-2 grammar.

- Regular expression (x/y)(x/y) denotes the set
- a) {xy,xy}
- b) {xx,xy,yx,yy}
- c) {x,y}
- d) {x,y,xy}

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

- Regular expression x/y denotes the set
- a) {x,y}
- b) {xy}
- c) {x}
- d) {y}

### Answer

Answer: a

Explanation: Because either x or y can be selected.

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

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

10.The regular expression denote a language comprising all possible strings of even length over the alphabet (0, 1)

- a) 1 + 0(1+0)*
- b) (0+1) (1+0)*
- c) (1+0)
- d) (00+0111+10)*

### Answer

Answer: d

Explanation: Option A does not consider even length criteria for the question.

Option B it can so happen here that from the former bracket it takes 0 or 1 and takes null from the latter then it forms a string of odd length

Option C it gives either 1 or 0.

Hence Option D is the answer.

11. The RE gives none or many instances of an x or y is

- a) (x+y)
- b) (x+y)*
- c) (x* + y)
- d) (xy)*

### Answer

Answer: b

Explanation: Whether x or y is denoted by x+y and for zero or more instances it is denoted but (x+y)*.

12. The RE in which any number of 0’s is followed by any number of 1’s followed by any number of 2’s is

- a) (0+1+2)*
- b) 0*1*2*
- c) 0* + 1 + 2
- d) (0+1)*2*

### Answer

Answer: b

Explanation: The order for the desired string is 012 and foe any number of 0s we write 0* for any number of 1s we denote it by 1* and similarly for 2*.Thus 0*1*2*.

13. The regular expression have all strings of 0’s and 1’s with no two consecutive 0’s is :

- a) (0+1)
- b) (0+1)*
- c) (0+?) (1+10)*
- d) (0+1)* 011

### Answer

Answer: c

Explanation: From the former bracket we choose 0 or epsilon. Then from the latter part 1 or 10 which can be followed by 1 or 10.

14. The regular expression with all strings of 0’s and 1’s with at least two consecutive 0’s is:

- a) 1 + (10)*
- b) (0+1)*00(0+1)*
- c) (0+1)*011
- d) 0*1*2*

### Answer

Answer: b

Explanation: The expression (0+1)*00(0+1)* is where either it initially takes 0 or 1 or 00 followed by string of combination of 0 and 1.

15. Which of the following is NOT the set of regular expression R = (ab + abb)* bbab

- a) ababbbbab
- b) abbbab
- c) ababbabbbab
- d) abababab

### Answer

Answer: a

Explanation: ab followed by abb which is followed by bbab.

16. String generated by

S->aS/bA,

A->d/ccA

- a) aabccd
- b) adabcca
- c) abcca
- d) abababd

### Answer

Answer: a

Explanation: S->aS (substitute S->aS)

S->aaS (substitute S->bA)

S->aabA (substitute A->ccA)

S->aabccA (substitute A->d)

S->aabccd.

17. Consider the production of the grammar S->AA A->aa A->bb Describe the language specified by the production grammar.

- a) L = {aaaa,aabb,bbaa,bbbb}
- b) L = {abab,abaa,aaab,baaa}
- c) L = {aaab,baba,bbaa,bbbb}
- d) L = {aaaa,abab,bbaa,aaab}

### Answer

Answer: a

Explanation: S->AA (substitute A->aa)

S->aaaa

S->AA (substitute A->aa )

S->aaA (substitute A->bb)

S->aabb

S->AA (substitute A->bb the A->aa)

S->bbaa

S->AA (substitute A->bb)

S->bbbb.

18. If R is regular language and Q is any language (regular/ non regular), then Pref (Q in R) is _____________

- a) Non-regular
- b) Equal
- c) Infinite
- d) Regular

### Answer

Answer: d

Explanation: So says the definition of Regular Grammar.

19. The production of the form no terminal ? ? is said to be null production.

- a) False
- b) True

### Answer

Answer: b

Explanation: Here the non terminal that gives null will said to have a null production.