automatafinite-automatadfa

DFA over language {0,1}

I'm trying to satisfy the following requirements (homework)

Construct both regular expression and deterministic automatons that accept the following languages over {0,1}.

I've done the following so far but it feels wrong, anyone have any suggestions on what I can do better? I'm very new to this and don't even know if what I've done fills the requirements.

DFA example solution

Solution

  • I find making regular expressions is harder than DFAs, so I recommend making the DFAs first and then getting regular expressions after.

    (a) We can make a DFA that detects the substring 00 and transitions to a dead state.

     q    s   q'
--   --   --
q0    0   q1        q0 is the initial state
q0    1   q0        q0 and q1 are accepting
q1    0   q2        q2 is a dead state
q1    1   q0
q2    0   q2
q2    1   q2

    To get the regular expression, we iteratively find for each state a regular expression for strings leading to that state. Then, we take the union of all regular expressions for accepting states.

    iteration 1
q0: e + (q0)1 + (q1)1
q1: (q0)0
q2: (q1)0 + (q2)0 + (q2)1

iteration 2
q0: e + (q0)1 + (q0)01
q1: (q0)0
q2: (q0)00 + (q2)0 + (q2)1

iteration 3
q0: e+(1+01)*
q1: (e+(1+01)*)0
q2: (e+(1+01)*)00(0+1)*

    Because q0 and q1 are accepting states, the regular expression is

      e+(1+01)*+(e+(1+01)*)0
= (1+01)*+(1+01)*0          // e + r* = r*
= (1+01)*e+(1+01)*0         // r = re
= (1+01)(e+0)               // distributive law of concatenation

    (b) A DFA here is:

     q     s    s'
--    --    --
q0     0    q1
q0     1    q1           q0 is the initial state
q1     0    q2           q3 is the accepting state
q1     1    q2
q2     0    q3
q2     1    q3
q3     0    q3
q3     1    q3

    Same exercise:

     iteration 1
 q0: e
 q1: (q0)0 + (q0)1
 q2: (q1)0 + (q1)1
 q3: (q2)0 + (q2)1

 iterations 2-3 (combined)
 q0: e
 q1: e0 + e1
 q2: (0+1)0 + (0+1)1
 q3: (q2)0 + (q2)1 + (q3)0 + (q3)1

 iteration 4
 q0: e
 q1: e0 + e1
 q2: (0+1)0 + (0+1)1
 q3: ((0+1)0 + (0+1)1)(0+1)(0+1)*

    Since q4 is the only accepting state, the answer is just

      ((0+1)0 + (0+1)1)(0+1)(0+1)*
= (00+10+01+11)(0+1)(0+1)*

    (c) This is very similar to (a) except that we throw out strings ending in 0. That is, q1 is not accepting. So, the DFA is the same as in (a), with q1 not accepting, and the regular expression is therefore just e+(1+01)* = (1+01)*.

    (d) A DFA:

     q     s    q'
--    --    --
q0     0    q1
q0     1    q2        q0 is the initial state
q1     0    q1        q3 is the accepting state
q1     1    q1        q1 is the dead state
q2     0    q1        q0,q1,q2 ensure the string starts with 11
q2     1    q3        q3,q4,q5 ensure the string stops with 11
q3     0    q4
q3     1    q3
q4     0    q4
q4     1    q5
q5     0    q4
q5     1    q3

    We can certainly go through the same exercise as above but a regular expression is actually easy to make here: 11+111+11(0+1)*11.

    (e) A DFA:

     q     s    q'
--    --    --
q0     0    q1
q0     1    q2    q0 is the initial state
q1     0    q0    q3 is the accepting state
q1     1    q3    q0: #0 and #1 are even
q2     0    q3    q1: #0 is odd, #1 is even
q2     1    q0    q2: #0 is even, #1 is odd
q3     0    q2    q3: #0 is odd, #1 is odd
q3     1    q1

    The regular expression here is difficult and left as an exercise. You can go through the iterations as in the earlier examples; just remember the rule is:

    qx: r + (qx)s    --->    qx: (r)(s*)

    Then just eliminate one symbol at a time until you have a regular expression for (q3) with no state placeholders. Good luck.