Automata Theory Questions and Answers – Operators of Regular Expression

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

1. A finite automaton accepts which type of language:
a) Type 0
b) Type 1
c) Type 2
d) Type 3
View Answer

Answer: d
Explanation: Type 3 refers to Regular Languages which is accepted by a finite automaton.

2. Which among the following are incorrect regular identities?
a) εR=R
b) ε*=ε
c) Ф*=ε
d) RФ=R
View Answer

Answer: d
Explanation: There are few identities over Regular Expressions which include: RФ=ФR=Ф≠R

3. Simplify the following regular expression:
ε+1*(011) *(1*(011) *) *
a) (1+011) *
b) (1*(011) *)
c) (1+(011) *) *
d) (1011) *
View Answer

Answer: a
Explanation: ε+1*(011) *(1*(011) *) *
ε + RR*= ε + R*R= ε + R+= R*
advertisement
advertisement

4. P, O, R be regular expression over ∑, P is not ε, then
R=Q + RP has a unique solution:
a) Q*P
b) QP*
c) Q*P*
d) (P*O*) *
View Answer

Answer: b
Explanation: The given statement is the Arden’s Theorem and it tends to have a unique solution as QP*.
Let P and Q be regular expressions,
R=Q+RP
R=Q+(Q+RP) P
R=Q+((Q+RP) +RP) +P=Q+QP+RPP+RPP=Q+QP+(Q+RP) PP+(Q+RP) PP=Q+QP+QPP+RPPP+QPP+RPPP,
If we do this recursively, we get:
R= QP*

5. Arden’s theorem is true for:
a) More than one initial states
b) Null transitions
c) Non-null transitions
d) None of the mentioned
View Answer

Answer: c
Explanation: Arden’s theorem strictly assumes the following;
a) No null transitions in the transition diagrams
b) True for only single initial state

6. The difference between number of states with regular expression (a + b) and (a + b) * is:
a) 1
b) 2
c) 3
d) 0
View Answer

Answer: a
Explanation:

7. In order to represent a regular expression, the first step to create the transition diagram is:
a) Create the NFA using Null moves
b) Null moves are not acceptable, thus should not be used
c) Predict the number of states to be used in order to construct the Regular expression
d) None of the mentioned
View Answer

Answer: a
Explanation: Two steps are to be followed while converting a regular expression into a transition diagram:
a) Construct the NFA using null moves.
b) Remove the null transitions and convert it into its equivalent DFA.
advertisement

8. (0+ε) (1+ε) represents
a) {0, 1, 01, ε}
b) {0, 1, ε}
c) {0, 1, 01 ,11, 00, 10, ε}
d) {0, 1}
View Answer

Answer: a
Explanation: The regular expression is fragmented and the set of the strings eligible is formed. ‘+’ represents union while ‘.’ Represents concatenation.

9. The minimum number of states required to automate the following Regular Expression:
(1) *(01+10) (1) *
a) 4
b) 3
c) 2
d) 5
View Answer

Answer: a
Explanation: None.
advertisement

10. Regular Expression denote precisely the ________ of Regular Language.
a) Class
b) Power Set
c) Super Set
d) None of the mentioned
View Answer

Answer: a
Explanation: Regular Expression denote precisely the class of regular language. Given any regular expression, L(R) is a regular language. Given any regular language L, there is a regular expression R, such that L(R)=L.

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