Search code examples
algorithmmathfinite-automataautomatadfa

DFA - design a DFA that accepts all strings over {0,1} that contains at most two 00's and three 11's as substring

I am practicing my DFA and I came across this question that seems to be very complex. I tried splitting it up into two smaller questions and I have an answer but it doesn't look right to me.

Can someone help me or at least give me some tips.

They are all accepting states btw. enter image description here

Another possibility that I can think of is that you only have the accepting states every two O's or 1's since they need to be a pair. So for example 11 accepting 11 accepting 11 accepting.

Solution

  • You're describing your state machine as a huge picture, but you can make your problem much easier by naming your states with structured names rather than trying to draw a huge diagram.

    Let your states be (n, m, s) where n is the number of 00s you've seen, m is the number of 11s you've seen and s is the previous character read (s='', '1', '0') (where '' means you haven't seen a previous character, or you've just found a '00' or '11').

    Then your transitions are:

    (n, m, '')  -0-> (n, m, '0')
(n, m, '')  -1-> (n, m, '1')
(n, m, '0') -0-> (n+1, m, '')
(n, m, '0') -1-> (n, m, '1')
(n, m, '1') -0-> (n, m, '0')
(n, m, '1') -1-> (n, m+1, '')

    All states with n<=2 and m<=3 are accepting. The start state is (0, 0, '').

    This isn't finite, but you can make it so by merging all non-accepting states into a single state. It'll have (3 * 4 * 3 + 1) = 37 states, which is minimal.

    Counting overlapping 00 and 11.

    The answer above assumes that '000' contains one '00' rather than 2 '00's (that is the number of '00' is the maximal number of non-overlapping '00' in the string, and the same for '11'). If you want to count '000' as 2, you need this machine:

    States are S (start) or (n, m, s) where n, m are as before, and s is '0' or '1'. Then:

    S -0-> (0, 0, '0')
S -1-> (0, 0, '1')
(n, m, '0') -0-> (n+1, m, '0')
(n, m, '0') -1-> (n, m, '1')
(n, m, '1') -0-> (n, m, '0')
(n, m, '1') -1-> (n, m+1, '1')

    All states are accepting except those with n>2 or m>3. Again, we merge all non-accepting states into a single state.

    This has (3 * 4 * 2 + 2) = 26 states, which again, is minimal.

    Generating a FSM diagram.

    Given the formal description, one can write a program to generate a DOT file that describes the machine. Here's the program to generate the diagram for the machine in the first part of the answer. (Note, it doesn't show which states are accepting, but they all are except FAIL).

    def state(n, m, s):
    if n > 2 or m > 3: return 'FAIL'
    return "n%s_%s_%s" % (n, m, s)

def T(st, c):
    n, m, s = st
    if s == '':
        return (n, m, c)
    if s == '0':
        return (n+1, m, '') if c=='0' else (n, m, c)
    if s == '1':
        return (n, m+1, '') if c=='1' else (n, m, c)

print 'digraph {'
for n in xrange(3):
    for m in xrange(4):
        for s in ['', '0', '1']:
            for c in '01':
                print '    %s -> %s [label="%s"]' % (state(n, m, s), state(*T((n, m, s), c)), c)

print '}'

    Here's the result from piping the output through dot -Tpng: FSM