All Exams Test series for 1 year @ ₹349 only
Question

Consider the DFA given below

Which of the regular expressions given below represents the above DFA ?

The correct answer is

$(0+1)*00$

To find the regular expression that represents the given DFA, we need to analyze its structure and transitions.

  1. The DFA starts and ends in different states, indicating specific strings that will result in acceptance. We need to find the path that leads to the accepting state.
  2. The starting state is represented by the leftmost state. From the start state, the DFA can follow these paths:
    • On input '0', move to the second state.
    • On input '1', stay in the start state.
  3. The second state transits:
    • On '0', it moves to the accepting state.
    • On '1', it loops back to the start state or the second state depending on the DFA structure.
  4. The accepting state requires two '0's in succession, represented by the string "00". Since any combination of '0's and '1's can be in the prefix, we use the Kleene star operator for "0+1": \((0+1)^*00\).

Therefore, the correct regular expression corresponding to the given DFA is:

(0+1)*00

Explanation of Options:

  • (0+1)*00 correctly represents the DFA as it requires a string to end with "00".
  • (0+1)*0 is incorrect because it allows any string ending in a single '0', which is not accepted by the DFA.
  • (0+1)* is incorrect because it allows any string, not ensuring the "00" pattern required by the DFA.
  • (0+1)*00(0+1)* is incorrect because it suggests "00" can appear anywhere, but in the DFA, "00" should appear at the end.

Hence, the correct answer is (0+1)*00.

Was this answer helpful?

Important Questions from Finite Automata

  1. If NFA of 5 states excluding the initial state is converted into DFA, maximum possible number of states for the DFA is?

  2. A Language for which DFA exist is a________

  3. For a DFA accepting binary numbers whose decimal equivalent is divisible by 3, what are all the possible remainders?

  4. Minimum Number of states require to accept string ends with 101.

  5. Consider the following DFA that generates set of strings over $\Sigma=\{a, b, c\}$

    Now identify that which of the followings is the best description of the language for the above DFA

Need Expert Advice?

Start Your Preparation with Prepp Mobile App

Download the app from Google Play & App Store
Download the app from Google Play & App Store
Prepp Mobile App