3
$\begingroup$

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.

First regex's DFA First regex's DFA, minimized

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

Second regex's DFA Second regex's DFA, minimized

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.

Pseudocode

$\endgroup$
2
  • 4
    $\begingroup$ In the first round, State 0 is distinguishable from the other states, which are accepting. In the second round, States 1 and 2 are distinguishable by "b", States 1 and 3 are also distinguishable by "b", States 2 and 3 are distinguishable by "c". Therefore the given DFA is already minimal. I can't see the pseudocode, so I'm not sure what happened. My top hypothesis is that this pseudocode assumes an explicit "reject" state instead of missing arcs. $\endgroup$ Aug 15, 2022 at 12:51
  • $\begingroup$ @DavidEisenstat you have (and should post) the correct answer: textbook versions of Hopcroft's algorithm assume complete DFAs. $\endgroup$
    – agemO
    Feb 20 at 23:43

1 Answer 1

1
$\begingroup$

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})
$\endgroup$
1
  • 1
    $\begingroup$ What I realized, thanks to your answer, was that I only contemplated a single case out of the many when splitting the set of states. Now I understand that there are more conditions that lead to the splitting in two different sets and I believe I can implement a proper solution. $\endgroup$
    – Ψray
    Aug 15, 2022 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.