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.