Automata Theory Questions and Answers – Building Regular Expressions

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

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.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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

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

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

Answer: c
Explanation: Using the rules of precedence on the give expression, c is the appropriate choice with the order of: Bracket>Kleene>Dot>Union

Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory for Quizzes, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.