250+ TOP MCQs on DFA to Regular Expressions and Answers

Automata Theory Multiple Choice Questions on “DFA to Regular Expressions”.

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

Answer: b
Clarification: 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.

2. 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
Answer: a

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

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

Answer: c
Clarification: (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.

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

Answer: a
Clarification: 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

Answer: a
Clarification: 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
Answer: c

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+_)*

Answer: c
Clarification: 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.