Regular Expression to DFA

Question

Can someone tell me if the attached DFA is correct ?

I am suppose to give DFA for the language that has alphabet Σ ={a, b}

I need DFA for this ----> A={ε, b, ab}

Answer 1

No, for multiple reasons:

1. Your automaton bab
2. Your automaton does not accept ab
3. Your automaton is not a DFA, at least by some strict definitions

Regarding the first point: starting at q1, we see b, go to q2, see a, go to q3, see b, and go to q4, which is accepting. We saw bab and accepted it.

Regarding the second point: starting at q1, we see a but have no defined transition. The automaton "crashes" and fails to accept. So no string starting with a is accepted, including ab.

Regarding the third point: DFAs are often required to show all states and transitions, including dead states and transitions that will never lead back to any accepting state. You don't show all transitions and don't show all states in your automaton.

You can use the Myhill-Nerode theorem to determine how many states a minimal DFA for your language has. We note that the empty state can have appended either the empty string, b or ab to get a string in the language; a can have b appended; and b can have the empty string appended. Nothing can be appended to aa, bb, or ba to get a string in the language (so these are indistinguishable); but ab can have the empty string appended (and so is indistinguishable from b).

Equivalence classes so determined correspond to states in a minimal DFA. Our equivalence classes are:

1. Strings like the empty string
2. Strings like b
3. Strings like a
4. Strings like aa

We note that b is in the language, so the second class will correspond to an accepting state. We notice nothing can be appended to aa to get a string in the language, so this class corresponds to a dead state in the DFA. We write the transitions between these states by seeing which new equivalence class the appending of a new symbol puts us in:

1. Appending a puts us in (3) since appending a to the empty string gives a which is in (3). Appending b puts us in (2) since appending b to the empty string gives b which is in (2)

2. Appending a puts us in (4) since appending a to to b gives ba which is like aa in that it isn't a prefix of any string in the language. Appending b, we arrive in (4) by a similar argument.

3. Appending a we get aa and are in (4). Appending b we get ab which is like b so we are in (2).

4. All transitions from a dead state return to a dead state; both a and b lead back to (4).

You end up with something like:

q1 --a--> q3
 |        /|
 b  --b--< a
 | /       |
 vv        v
q2 -a,b-> q4 \
           ^ a,b
           \_/

Or in tabular form:

q    s    q'
==   =    ==
q1   a    q3
q1   b    q2
q2   a    q4
q2   b    q4
q3   a    q4
q3   b    q2
q4   a    q4
q4   b    q4