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?

a) (0+1)*001(0+1)*

b) 1*001(0+1)*

c) (01)*(0+0+1)(01)*

d) None of the mentioned

View Answer

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

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

4. Which of the given regular expressions correspond to the automata shown?

a) (110+1)*0

b) (11+110)*1

c) (110+11)*0

d) (1+110)*1

View Answer

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

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

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

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

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

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.

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

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