Hopcroft's minimization algorithm produces an incorrect result for a particular regular expression

Question

I'm writing a DFA minimizer using Hopcroft's algorithm. While testing some regular expressions, I came out with an issue in the algorithm's output relative to two particular regular expressions:

• a(b|c)*
• a(b|c*)

P.S.: the assumption is that both regular expressions are valid, but if that's not the case please let me know, I wouldn't be able to see what's wrong.

---

The difference between the two is that the first one allows for the letters b and c to be consumed an indefinite number of times, while the second one only allows for the letter c to be repeated indefinitely. This makes the scanner reach an accepting state if, after reading the letter a, it reads b. That is, it should stop when reading ab and consider an input like abbbb wrong, but acccc correct.

Let's generate the DFA for the first regex. Accepting states are in green. The picture below shows the DFA and its minimization.

All is good, let's generate the DFA for the second regex now.

After applying Hopcroft's algorithm, it occurs to me that the result is the same. However, the minimization of the second DFA is incorrect because it also allows to repeat the letter b indefinitely. Did I apply the algorithm in an incorrect way, is this a side effect of that particular regular expression? I can't seem to figure out.

I followed the pseudocode found on Engineering a Compiler, 2nd edition as explained in pages 54 to 57. The graphs are generated first using Thompson's construction, then the subset construction to get a DFA and minimized using Hopcroft's algorithm.

Answer 1

I suspect what happened is that you took Split to subdivide a cluster of states based on whether the successor state is accepting or rejecting, which, since the pseudocode only contemplates a binary division (wrong), is understandable.

Below is some Python code that I believe correctly implements minimization while being only somewhat more low-level than that pseudocode.

import collections

DFA = collections.namedtuple("DFA", ("Q", "Sigma", "delta", "q_0", "F"))


# Minimizes the given DFA. To avoid making this function more complicated, I've
# assumed that the input contains no dead states.
def minimize(dfa):
    # Input state labeling. Two states are distinguishable iff they have
    # different labels.
    labels = {q: (1 if q in dfa.F else 0) for q in dfa.Q}

    # Refine the labels until we reach a fixed point.
    while True:
        label_count = len(set(labels.values()))
        for sigma in dfa.Sigma:
            # Extend each label by the label of the successor state after sigma.
            labels = {
                q: (label, labels.get(dfa.delta.get((q, sigma))))
                for (q, label) in labels.items()
            }
            # Renumber for a compact representation. In another language, we'd
            # do these steps at the same time.
            labels = renumber_labels(labels)
        if len(set(labels.values())) <= label_count:
            # Arrived at a fixed point.
            break

    # Compute the new transition function.
    delta = {}
    for q in dfa.Q:
        for sigma in dfa.Sigma:
            q_prime = dfa.delta.get((q, sigma))
            if q_prime is not None:
                delta[(labels[q], sigma)] = labels[q_prime]

    return DFA(
        Q=set(labels.values()),
        Sigma=dfa.Sigma,
        delta=delta,
        q_0=labels[dfa.q_0],
        F={labels[q] for q in dfa.F},
    )


def renumber_labels(labels):
    label_numbers = {}
    for label in labels.values():
        label_numbers.setdefault(label, len(label_numbers))
    return {q: label_numbers[label] for (q, label) in labels.items()}


a = "a"
b = "b"
c = "c"
print(
    minimize(
        DFA(
            Q={0, 1, 2, 3},
            Sigma={a, b, c},
            delta={
                (0, a): 1,
                (1, b): 2,
                (1, c): 3,
                (2, b): 2,
                (2, c): 3,
                (3, b): 2,
                (3, c): 3,
            },
            q_0=0,
            F={1, 2, 3},
        )
    )
)
print(
    minimize(
        DFA(
            Q={0, 1, 2, 3},
            Sigma={a, b, c},
            delta={(0, a): 1, (1, b): 2, (1, c): 3, (3, c): 3},
            q_0=0,
            F={1, 2, 3},
        )
    )
)

Output:

DFA(Q={0, 1}, Sigma={'a', 'c', 'b'}, delta={(0, 'a'): 1, (1, 'c'): 1, (1, 'b'): 1}, q_0=0, F={1})
DFA(Q={0, 1, 2, 3}, Sigma={'a', 'c', 'b'}, delta={(0, 'a'): 1, (1, 'c'): 3, (1, 'b'): 2, (3, 'c'): 3}, q_0=0, F={1, 2, 3})