CODEWITHSUNDEEP
algorithmmathfinite-automataautomatadfa
Gana
Gana

Reputation: 75

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.

Upvotes: 3

Views: 5553

Answers (2)

Paul Hankin
Paul Hankin

Reputation: 58201

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

Upvotes: 3

RiaD
RiaD

Reputation: 47619

Well, instead of drawing the automaton you may describe it using words.

How would I do that for your problem: Let a vertex be a triple where

  • first element is 0, 1, 2, 3 and "at least 4" showing the number of 11s.
  • second element is 0, 1, 2 and "at least 3" depending on number of "00"s
  • third element is the last symbol (0, 1 or "string is empty")

It's pretty easy to define the transitions, start states and finish states.

So, there's 5 * 4 * 3 = 60 states

You may notice that there are some not achievable states and some states that may be united to "failed states" that can reduce the size of automaton significantly

Upvotes: 2

Related Questions