Search code examples
regexexpressioncomputation-theorydfanfa

Convert a regulation expression to DFA

I have been trying different ways to solve this problem for over an hour and am getting very frustrated.

The problem is: Give regular expressions and DFAs for each of the following languages over Sigma = {0,1}.

a). {w ∈ Σ* | w contains an even number of 0s or an odd number of 1s}

If anyone could provide hints or get me started on figuring this one out, it would be very appreciated!

I know it is something along the lines of this DFA but this one is for

{w ∈ Σ* | w contains an even number of 0s or exactly two 1's}

so it's a bit different but I can't figure it out.

enter image description here

Solution

  • You can see it as follows: you always have to remember two things:

    1. whether the number of 0s is even or odd; and
    2. whether the number of 1s is even or odd.

    Now if we denote even with e and odd with o, we consider four states: ee (both even), eo (even number of 0s and odd number of 1s), oe and oo.

    Now when we read a zero (0), we simply swap the first state token, so it means we introduce transitions from:

    1. ee - 0 -> oe;
    2. eo - 0 -> oo;
    3. oe - 0 -> ee; and
    4. oo - 0 -> eo.

    The same for ones (1):

    1. ee - 1 -> eo;
    2. eo - 1 -> ee;
    3. oe - 1 -> oo; and
    4. oo - 1 -> oe.

    Now we only need to determine the initial state and the accepting state(s). The intial state is ee, since at that moment we have considered no zeros and no ones.

    Furthermore the accepting state can by determined by the condition:

    w contains an even number of 0s or an odd number of 1s

    So that means the accepting states are ee, eo and oo. A drawing of this DFA is shown below:

    dfa described above

    There exists an algorithmic way to convert a DFA into an equivalent regular expression as is stated here.

    You can construct a regular expression by splitting the problem into two easier problems:

    • a regex that checks if the number of 0s is even; and
    • a regex that checks if the number of 1s is odd.

    For the first, you can use the regex:

    (1*01*0)*1*

    Indeed: you first have a group (1*01*0). This group ensures that there are two zeros, and 1s can appear everywhere in between. We allow an arbitrary number of repetitions, since the number always remains even. The regex ends with 1* since it is still possible that there are additional ones in the string.

    The second problem can be solved with the regex:

    0*1(0*10*1)*0*

    The solution is more or less the same. The expression between the brackets: (0*10*1) ensures that the ones occur evenly. By adding a 1 in front, we ensure the number of 1s is odd.

    A regular expression that then solves the problem is:

    (1*01*0)*1*|0*1(0*10*1)*0*

    Since the "pipe" (|) means "or".