Exploring fun and horrible ways in which non-deterministic automata (NFA) determinization can go wrong. We consider ways to make automata, search for a worst case, and then make inductive leaps. All without the sanity-checking of a textbook or good research. What could possibly go wrong?

Automata Construction Possibilities

Consider the possible ways to construct 2-state NFA for an alphabet = {0,1}.

• State 0 can accept or not. (2 options)
• State 1 can accept or not. (2 options)
• State 0 can transition, on ‘0’, to S0, S1, S0 & S1, or nowhere. (4 options)
• State 0 can transition, on ‘1’, to S0, S1, S0 & S1, or nowhere. (4 options)
• State 1 can transition, on ‘0’, to S0, S1, S0 & S1, or nowhere. (4 options)
• State 1 can transition, on ‘1’, to S0, S1, S0 & S1, or nowhere. (4 options)

Next, consider the same using 3-states.

• State 0 can accept or not. (2 options)
• State 1 can accept or not. (2 options)
• State 2 can accept or not. (2 options)
• State 0 can transition, on ‘0’, to S0, S1, S2, S0 & S1, S0 & S2, S1 & S2, S0 & S1 & S2, or nowhere. (8 options)
• State 0 can transition, on ‘1’, to S0, S1, S2, S0 & S1, S0 & S2, S1 & S2, S0 & S1 & S2, or nowhere. (8 options)
• State 1 can transition, on ‘0’, to S0, S1, S2, S0 & S1, S0 & S2, S1 & S2, S0 & S1 & S2, or nowhere. (8 options)
• State 1 can transition, on ‘1’, to S0, S1, S2, S0 & S1, S0 & S2, S1 & S2, S0 & S1 & S2, or nowhere. (8 options)
• State 2 can transition, on ‘0’, to S0, S1, S2, S0 & S1, S0 & S2, S1 & S2, S0 & S1 & S2, or nowhere. (8 options)
• State 2 can transition, on ‘1’, to S0, S1, S2, S0 & S1, S0 & S2, S1 & S2, S0 & S1 & S2, or nowhere. (8 options)

Though repetetive, exhausting the possibilities for both 2- and 3-state non-deterministic finite automata exposes a trend. The amount of NFAs we can form using those states, #PossibleNFAs = AcceptPossibilities * TransitionPossibilities, where AcceptPossibilities = 2^^#states and TransitionPossibilities = (2^^#states)^^{(alphabetSize*#states)}.

Some time later, I’ll brute force the space for a 2-letter alphabet on 3 states, but for now, here my approximation of the worst-case:

1
2
3
4
5
6
7
8
9

{
    "0" : {"0" : 1,
           "1" : [0,1]},
    "1" : {"0" : 2,
           "1" : [1,2]},
    "2" : {"0" : 0,
           "1" : 1,
           "ACCEPT" : "done"}
}

Before determinization, it looks like this:

A little transition-heavy, but seemingly unassuming. If you turned it 90° clockwise, it would make a convincing muppet. Anyway, after determinizing it using the subset construction (and not using any minimization techniques) it looks like this:

Pretty big.

This post was primarily a formatting test. Expect more soon.