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
Note: Join free Sanfoundry classes at Telegram or Youtube
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}$

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.

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 & technical discussions at Telegram SanfoundryClasses.