# Automata Theory Questions and Answers – Regular Expression-Introduction

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Regular Expression-Introduction”.

1. L is a regular Language if and only If the set of __________ classes of IL is finite.
a) Equivalence
b) Reflexive
c) Myhill
d) Nerode
View Answer

Answer: a
Explanation: According to Myhill Nerode theorem, the corollary proves the given statement correct for equivalence classes.

2. A language can be generated from simple primitive language in a simple way if and only if
a) It is recognized by a device of infinite states
b) It takes no auxiliary memory
c) All of the mentioned
d) None of the mentioned
View Answer

Answer: b
Explanation: A language is regular if and only if it can be accepted by a finite automaton. Secondly, It supports no concept of auxiliary memory as it loses the data as soon as the device is shut down.

3. Which of the following does not represents the given language?
Language: {0,01}
a) 0+01
b) {0} U {01}
c) {0} U {0}{1}
d) {0} ^ {01}
View Answer

Answer: d
Explanation: The given option represents {0, 01} in different forms using set operations and Regular Expressions. The operator like ^, v, etc. are logical operation and they form invalid regular expressions when used.
advertisement
advertisement

4. According to the given language, which among the following expressions does it corresponds to?
Language L={xϵ{0,1}|x is of length 4 or less}
a) (0+1+0+1+0+1+0+1)4
b) (0+1)4
c) (01)4
d) (0+1+ε)4
View Answer

Answer: d
Explanation: The extended notation would be (0+1)4 but however, we may allow some or all the factors to be ε. Thus ε needs to be included in the given regular expression.

5. Which among the following looks similar to the given expression?
((0+1). (0+1)) *
a) {xϵ {0,1} *|x is all binary number with even length}
b) {xϵ {0,1} |x is all binary number with even length}
c) {xϵ {0,1} *|x is all binary number with odd length}
d) {xϵ {0,1} |x is all binary number with odd length}
View Answer

Answer: a
Explanation: The given regular expression corresponds to a language of binary strings which is of even length including a length of 0.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. If R represents a regular language, which of the following represents the Venn-diagram most correctly?

a) An Irregular Set
b) R*
c) R complement
d) R reverse
View Answer

Answer: b
Explanation: The given diagram represents the Kleene operation over the Regular Language R in which the final states become the initial and the initial state becomes final.

7. The given NFA corresponds to which of the following Regular expressions?

a) (0+1) *(00+11) (0+1) *
b) (0+1) *(00+11) *(0+1) *
c) (0+1) *(00+11) (0+1)
d) (0+1) (00+11) (0+1) *
View Answer

Answer: a
Explanation: The transition states shown are the result of breaking down the given regular expression in fragments. For dot operation, we change a state, for union (plus) operation, we diverge into two transitions and for Kleene Operation, we apply a loop.
advertisement

8. Concatenation Operation refers to which of the following set operations:
a) Union
b) Dot
c) Kleene
d) Two of the options are correct
View Answer

Answer: b
Explanation: Two operands are said to be performing Concatenation operation AB = A•B = {xy: x ∈ A & y ∈ B}.

9. Concatenation of R with Ф outputs:
a) R
b) Ф
c) R.Ф
d) None of the mentioned
View Answer

Answer: b
Explanation: By distributive property (Regular expression identities), we can prove the given identity to be Ф.
advertisement

10. RR* can be expressed in which of the forms:
a) R+
b) R-
c) R+ U R-
d) R
View Answer

Answer: a
Explanation: RR*=R+ as R+ means the occurrence to be at least once.

Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, 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, 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.