Automata Theory Questions and Answers – DFA to Regular Expressions

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “DFA to Regular Expressions”.

1. Which of the following is same as the given DFA?
(0+1)*001(0+1)* is same as the given DFA in the string as an essential substring
a) (0+1)*001(0+1)*
b) 1*001(0+1)*
c) (01)*(0+0+1)(01)*
d) None of the mentioned
View Answer

Answer: a
Explanation: There needs to be 001 together in the string as an essential substring. Thus, the other components can be anything, 0 or 1 or e.

2. Which of the following statements is not true?
a) Every language defined by any of the automata is also defined by a regular expression
b) Every language defined by a regular expression can be represented using a DFA
c) Every language defined by a regular expression can be represented using NFA with e moves
d) Regular expression is just another representation for any automata definition
View Answer

Answer: b
Explanation: Using NFA with e moves, we can represent all the regular expressions as an automata. As regular expressions include e, we need to use e moves.

3. The total number of states required to automate the given regular expression
(00)*(11)*
a) 3
b) 4
c) 5
d) 6
View Answer

Answer: c
Explanation: The total number of states required to automate is 5
advertisement
advertisement

4. Which of the given regular expressions correspond to the automata shown?
The regular expressions correspond to the automata is (110+11)*0
a) (110+1)*0
b) (11+110)*1
c) (110+11)*0
d) (1+110)*1
View Answer

Answer: c
Explanation: There is no state change for union operation, but has two different paths while for concatenation or dot operation, we have a state change for every element of the string.

5. Generate a regular expression for the following problem statement:
Password Validation: String should be 8-15 characters long. String must contain a number, an Uppercase letter and a Lower case letter.
a) ^(?=.*[a-z])(?=.*[A-Z])(?=.*\d).{8,15}$
b) ^(?=.*[a-z])(?=.*[A-Z])(?=.*\d).{9,16}$
c) ^(?=.[a-z])(?=.[A-Z])(?=.\d).{8,15}$
d) None of the mentioned
View Answer

Answer: a
Explanation: Passwords like abc123, 123XYZ, should not be accepted . If one also wants to include special characters as one of the constraint, one can use the following regular expression:
^(?=.*[a-z])(?=.*[A-Z])(?=.*\d)(?=.*[^\da-za-Z]).{8,15}$
Note: Join free Sanfoundry classes at Telegram or Youtube

6. Generate a regular expression for the following problem statement:
P(x): String of length 6 or less for å={0,1}*
a) (1+0+e)6
b) (10)6
c) (1+0)(1+0)(1+0)(1+0)(1+0)(1+0)
d) More than one of the mentioned is correct
View Answer

Answer: a
Explanation: As the input variables are under Kleene Operation, we need to include e,thus option c is not correct,thereby option (a) is the right answer.

7. The minimum number of states required in a DFA (along with a dumping state) to check whether the 3rd bit is 1 or not for |n|>=3
a) 3
b) 4
c) 5
d) 1
View Answer

Answer: c
Explanation:The minimum number of states required in a DFA is 5
advertisement

8. Which of the regular expressions corresponds to the given problem statement:
P(x): Express the identifiers in C Programming language
l=letters
d=digits
a) (l+_)(d+_)*
b) (l+d+_)*
c) (l+_)(l+d+_)*
d) (_+d)(l+d+_)*
View Answer

Answer: c
Explanation: Identifiers in C Programming Language follows the following identifiers rule:
a) The name of the identifier should not begin with a digit.
b) It can only begin with a letter or a underscore.
c) It can be of length 1 or more.

9. Generate a regular expression for the given language:l
L(x): {xÎ{0,1}*| x ends with 1 nd does not contain a substring 01}
a) (0+01)*
b) (0+01)*1
c) (0+01)*(1+01)
d) All of the mentioned
View Answer

Answer: c
Explanation: (a) and (b) are the general cases where we restrict the acceptance of a string witrh substring 00 but we ignore the case where the string needs to end with 1 which therby, does not allows the acceptance of e.
advertisement

10. The minimum number of transitions to pass to reach the final state as per the following regular expression is:
{a,b}*{baaa}
a) 4
b) 5
c) 6
d) 3
View Answer

Answer: a
Explanation: The minimum number of transitions to pass to reach the final state is 4

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.