Building Regular Expressions Automata Theory Multiple Choice Questions with Answers

This set of Automata Theory Quiz focuses on “Building Regular Expressions”.

1. Which of the following is correct?
Statement 1: ε represents a single string in the set.
Statement 2: Ф represents the language that consist of no string.
a) Statement 1 and 2 both are correct
b) Statement 1 is false but 2 is correct
c) Statement 1 and 2 both are false
d) There is no difference between both the statements, ε and Ф are different notation for same reason
View Answer

Answer: a
Explanation: ε represents a single string in the set namely, the empty string while Statement 2 is also correct.

2. The appropriate precedence order of operations over a Regular Language is
a) Kleene, Union, Concatenate
b) Kleene, Star, Union
c) Kleene, Dot, Union
d) Star, Union, Dot
View Answer

Answer: c
Explanation: If a regular language expression is given, the appropriate order of precedence if the parenthesis is ignored is: Star or Kleene, Dot or Concatenation, Union or Plus.

3. Regular Expression R and the language it describes can be represented as:
a) R, R(L)
b) L(R), R(L)
c) R, L(R)
d) All of the mentioned
View Answer

Answer: c
Explanation: When we wish to distinguish between a regular expression R and the language it represents; we write L(R) to be the language of R.

4. Let for ∑= {0,1} R= (∑∑∑) *, the language of R would be
a) {w | w is a string of odd length}
b) {w | w is a string of length multiple of 3}
c) {w | w is a string of length 3}
d) All of the mentioned
View Answer

Answer: b
Explanation: This regular expression can be used to eliminate the answers and get the result. The length can be even and as well more than 3 when R= (∑∑∑) (∑∑∑) (particular case).

5. If ∑= {0,1}, then Ф* will result to:
a) ε
b) Ф
c) ∑
d) None of the mentioned
View Answer

Answer: a
Explanation: The star operation brings together any number of strings from the language to get a string in the result. If the language is empty, the star operation can put together 0 strings, resulting only the empty string.

6. The given NFA represents which of the following NFA
a) (ab U a) *
b) (a*b* U a*)
c) (ab U a*)
d) (ab)* U a*
View Answer

Answer: a
Explanation: The Regular expression (ab U a) * is converted to NFA in a sequence of stages as it can be clearly seen in the diagram. This NFA consist of 8 stated while its minimized form only contains 2 states.

7. Which of the following represents a language which has no pair of consecutive 1’s if ∑= {0,1}?
a) (0+10)*(1+ε)
b) (0+10)*(1+ε)*
c) (0+101)*(0+ε)
d) (1+010)*(1+ε)
View Answer

Answer: a
Explanation: All the options except ‘a’ accept those strings which comprises minimum one pair of 1’s together.

8. The finite automata accept the following languages:
a) Context Free Languages
b) Context Sensitive Languages
c) Regular Languages
d) All the mentioned
View Answer

Answer: c
Explanation: A finite automaton accepts the languages which are regular and for which a DFA can be constructed.

9. (a + b*c) most correctly represents:
a) (a +b) *c
b) (a)+((b)*.c)
c) (a + (b*)).c
d) a+ ((b*).c)
View Answer

Answer: d
Explanation: Following the rules of precedence, Kleene or star operation would be done first, then concatenation and finally union or plus operation.

10. Which of the following regular expressions represents the set of strings which do not contain a substring ‘rt’ if ∑= {r, t}
a) (rt)*
b) (tr)*
c) (r*t*)
d) (t*r*)
View Answer

Answer: d
Explanation: As Kleene operation is not on the whole of the substring, it will not repeat and maintain the order of t, r.

11. According to the precedence rules, x-y-z is equivalent to which of the following?
a) (x-y)-z
b) x-(y-z)
c) Both (x-y)-z and x-(y-z)
d) None of the mentioned
View Answer

Answer: a
Explanation: In arithmetic, we group two of the same operators from the left, hence x-y-z is equivalent to (x-y)-z and not x-(y—z).

12. Dot operator in regular expression resembles which of the following?
a) Expressions are juxtaposed
b) Expressions are multiplied
c) Cross operation
d) None of the mentioned
View Answer

Answer: a
Explanation: Dot operation or concatenation operation means that the two expressions are juxtaposed i.e. there are no intervening operators in between. In fact, UNIX regular expressions use the dot for an entirely different purpose: representing any ASCII character.

13. Which among the following is not an associative operation?
a) Union
b) Concatenation
c) Dot
d) None of the mentioned
View Answer

Answer: d
Explanation: It does not matter in which order we group the expression with the operators as they are associative. If one gets a chance to group the expression, one should group them from left for convenience. For instance, 012 is grouped as (01)2.

14.Which among the following is equivalent to the given regular expression?
01*+1
a) (01)*+1
b) 0((1)*+1)
c) (0(1)*)+1
d) ((0*1)1*)*
View Answer