The intersection operation via complement

Union, concatenation, and Kleene star build languages by adding possibilities. But phonological descriptions also need to rule possibilities out. How can an automaton reject exactly the strings that another automaton accepts? And how can it require two constraints at once? These questions lead to complement and intersection.

Complement

Let a complete deterministic finite automaton (DFA)

\[G=\langle Q,\Sigma,\delta,q_0,F\rangle\]

recognize $A$. Its complement is

\[ \operatorname{complement}(G) =\langle Q,\Sigma,\delta,q_0,Q\setminus F\rangle. \]

Nothing about a run changes. We change only which ending states count as accepting.

Why must the DFA be complete? Fix an arbitrary $w\in\Sigma^*$. A complete DFA has exactly one run on $w$, and that run ends in some state $q$. If $q\in F$, the original machine accepts and the complemented machine rejects. If $q\notin F$, the original rejects and the complemented machine accepts. Thus,

\[ w\in\mathbb{L}(\operatorname{complement}(G)) \quad\Longleftrightarrow\quad w\notin\mathbb{L}(G). \]

If the transition function were partial, a run could instead get stuck. Swapping final and nonfinal states would not help: a stuck run would be rejected by both machines. So we complete the machine with a rejecting sink before swapping the final states. An NFA must also be determinized first.

The following small DFA class makes the construction executable. It allows a partial transition table at initialization, but complete fills every missing transition before complement swaps the final states.

from __future__ import annotations

from dataclasses import dataclass


@dataclass(frozen=True, slots=True)
class DFA:
    """A deterministic finite-state automaton with string-valued states."""

    alphabet: frozenset[str]
    states: frozenset[str]
    initial_state: str
    final_states: frozenset[str]
    transitions: dict[tuple[str, str], str]

    def __post_init__(self) -> None:
        if self.initial_state not in self.states:
            raise ValueError("the initial state must belong to the state set")
        if not self.final_states <= self.states:
            raise ValueError("the final states must be a subset of the state set")
        for (state, symbol), target in self.transitions.items():
            if state not in self.states or target not in self.states:
                raise ValueError("every transition endpoint must be a state")
            if symbol not in self.alphabet:
                raise ValueError("every transition symbol must be in the alphabet")

    def accepts(self, word: str) -> bool:
        """Return whether the machine accepts ``word``."""
        state = self.initial_state
        for symbol in word:
            if symbol not in self.alphabet:
                return False
            try:
                state = self.transitions[(state, symbol)]
            except KeyError:
                return False
        return state in self.final_states

    def complete(self, alphabet: frozenset[str] | None = None) -> DFA:
        """Complete the machine over ``alphabet`` with a rejecting sink."""
        ambient = self.alphabet if alphabet is None else alphabet
        if not self.alphabet <= ambient:
            raise ValueError("the ambient alphabet cannot remove old symbols")

        states = set(self.states)
        sink = "sink"
        while sink in states:
            sink += ":sink"

        transitions = dict(self.transitions)
        missing = [
            (state, symbol)
            for state in states
            for symbol in ambient
            if (state, symbol) not in transitions
        ]
        if missing:
            states.add(sink)
            for key in missing:
                transitions[key] = sink
            for symbol in ambient:
                transitions[(sink, symbol)] = sink

        return DFA(
            ambient,
            frozenset(states),
            self.initial_state,
            self.final_states,
            transitions,
        )

    def complement(self) -> DFA:
        """Return the complement relative to this machine's alphabet."""
        complete = self.complete()
        return DFA(
            complete.alphabet,
            complete.states,
            complete.initial_state,
            complete.states - complete.final_states,
            dict(complete.transitions),
        )


ends_in_a = DFA(
    frozenset({'a', 'b'}),
    frozenset({'no-a', 'a'}),
    'no-a',
    frozenset({'a'}),
    {
        ('no-a', 'a'): 'a',
        ('no-a', 'b'): 'no-a',
        ('a', 'a'): 'a',
        ('a', 'b'): 'no-a',
    },
)
does_not_end_in_a = ends_in_a.complement()

assert ends_in_a.accepts('bba')
assert not does_not_end_in_a.accepts('bba')
assert does_not_end_in_a.accepts('abb')

Intersection

Suppose $G_1$ recognizes $A$ and $G_2$ recognizes $B$. De Morgan’s law gives

\[ A\cap B=\overline{\overline{A}\cup\overline{B}}. \]

This identity gives one construction: complement both machines, take their union, and complement the result. But every complement must use the same universe. If $G_1$ uses $\Sigma_1$ and $G_2$ uses $\Sigma_2$, we first set $\Sigma=\Sigma_1\cup\Sigma_2$ and complete both machines over $\Sigma$.

Fix an arbitrary $w\in\Sigma^*$. Then

\[ \begin{aligned} w\in\overline{\overline{A}\cup\overline{B}} &\iff w\notin\overline{A}\cup\overline{B}\\ &\iff w\notin\overline{A}\text{ and }w\notin\overline{B}\\ &\iff w\in A\text{ and }w\in B\\ &\iff w\in A\cap B. \end{aligned} \]

Why do we insist on a common alphabet? Let $A=a^*$ be presented over $\{a\}$ and $B=b^*$ over $\{b\}$. Their intersection relative to $\{a,b\}^*$ is $\{\epsilon\}$. Complements taken separately over $\{a\}^*$ and $\{b\}^*$ do not describe languages in one shared universe. So the common alphabet is part of the operation, not mere bookkeeping.

Direct product construction

We can compute the intersection more directly. Complete both DFAs over the common alphabet and let the new machine track a pair of states. Its components move on the same input symbol, and a pair is final only when both components are final.

For complete DFAs

\[ G_1=\langle Q_1,\Sigma,\delta_1,q_1,F_1\rangle \quad\text{and}\quad G_2=\langle Q_2,\Sigma,\delta_2,q_2,F_2\rangle, \]

define the product by

\[ \begin{aligned} Q&=Q_1\times Q_2,\\ q_0&=(q_1,q_2),\\ F&=F_1\times F_2,\\ \delta((r_1,r_2),\sigma) &=(\delta_1(r_1,\sigma),\delta_2(r_2,\sigma)). \end{aligned} \]

What does a product state mean? The paired-state invariant says that after reading a prefix $x$, the product is in $(r_1,r_2)$ exactly when $G_1$ is in $r_1$ after $x$ and $G_2$ is in $r_2$ after $x$.

Before any input is read, the product is $(q_1,q_2)$, so the invariant holds. Now suppose it holds after $x$ and read a symbol $\sigma$. The product transition applies the two component transitions to that same symbol. Its new state is thus exactly the pair reached by the two component machines after $x\sigma$. This proves the inductive step.

After the full string $w$, the product is final exactly when both component states are final. By the invariant, that happens exactly when $w\in A$ and $w\in B$. Thus, the product recognizes $A\cap B$.

The method below explores only product states reachable from the initial pair. Length-prefixed labels keep distinct state pairs distinct when we store the pairs as strings.

def pair_label(left: str, right: str) -> str:
    """Serialize a pair of strings without delimiter collisions."""
    return f'{len(left)}:{left}{len(right)}:{right}'


def intersection(left: DFA, right: DFA) -> DFA:
    """Construct the direct-product intersection of two DFAs."""
    alphabet = left.alphabet | right.alphabet
    left = left.complete(alphabet)
    right = right.complete(alphabet)

    initial_pair = (left.initial_state, right.initial_state)
    pending = [initial_pair]
    visited: set[tuple[str, str]] = set()
    transitions: dict[tuple[str, str], str] = {}

    while pending:
        pair = pending.pop()
        if pair in visited:
            continue
        visited.add(pair)

        for symbol in sorted(alphabet):
            target = (
                left.transitions[(pair[0], symbol)],
                right.transitions[(pair[1], symbol)],
            )
            transitions[(pair_label(*pair), symbol)] = pair_label(*target)
            if target not in visited:
                pending.append(target)

    final_states = frozenset(
        pair_label(*pair)
        for pair in visited
        if pair[0] in left.final_states and pair[1] in right.final_states
    )
    return DFA(
        frozenset(alphabet),
        frozenset(pair_label(*pair) for pair in visited),
        pair_label(*initial_pair),
        final_states,
        transitions,
    )


a_star = DFA(
    frozenset({'a'}),
    frozenset({'q'}),
    'q',
    frozenset({'q'}),
    {('q', 'a'): 'q'},
)
b_star = DFA(
    frozenset({'b'}),
    frozenset({'q'}),
    'q',
    frozenset({'q'}),
    {('q', 'b'): 'q'},
)
only_empty = intersection(a_star, b_star)

assert only_empty.accepts('')
assert not only_empty.accepts('a')
assert not only_empty.accepts('b')
assert not only_empty.accepts('ab')

The direct product usually avoids the repeated determinization required by the De Morgan construction. Both constructions establish the same closure result: the intersection of two regular languages is regular.

--- title: The intersection operation via complement bibliography: ../../references.bib jupyter: python3 --- Union, concatenation, and Kleene star build languages by adding possibilities. But phonological descriptions also need to rule possibilities out. How can an automaton reject exactly the strings that another automaton accepts? And how can it require two constraints at once? These questions lead to **complement** and **intersection**. ## Complement Let a complete deterministic finite automaton (DFA) $$G=\langle Q,\Sigma,\delta,q_0,F\rangle$$ recognize $A$. Its complement is $$ \operatorname{complement}(G) =\langle Q,\Sigma,\delta,q_0,Q\setminus F\rangle. $$ Nothing about a run changes. We change only which ending states count as accepting. Why must the DFA be complete? Fix an arbitrary $w\in\Sigma^*$. A complete DFA has exactly one run on $w$, and that run ends in some state $q$. If $q\in F$, the original machine accepts and the complemented machine rejects. If $q\notin F$, the original rejects and the complemented machine accepts. Thus, $$ w\in\mathbb{L}(\operatorname{complement}(G)) \quad\Longleftrightarrow\quad w\notin\mathbb{L}(G). $$ If the transition function were partial, a run could instead get stuck. Swapping final and nonfinal states would not help: a stuck run would be rejected by both machines. So we complete the machine with a rejecting sink before swapping the final states. An NFA must also be determinized first. The following small `DFA` class makes the construction executable. It allows a partial transition table at initialization, but `complete` fills every missing transition before `complement` swaps the final states. ```{python} from __future__ import annotations from dataclasses import dataclass @dataclass(frozen=True, slots=True) class DFA: """A deterministic finite-state automaton with string-valued states.""" alphabet: frozenset[str] states: frozenset[str] initial_state: str final_states: frozenset[str] transitions: dict[tuple[str, str], str] def __post_init__(self) -> None: if self.initial_state not in self.states: raise ValueError("the initial state must belong to the state set") if not self.final_states <= self.states: raise ValueError("the final states must be a subset of the state set") for (state, symbol), target in self.transitions.items(): if state not in self.states or target not in self.states: raise ValueError("every transition endpoint must be a state") if symbol not in self.alphabet: raise ValueError("every transition symbol must be in the alphabet") def accepts(self, word: str) -> bool: """Return whether the machine accepts ``word``.""" state = self.initial_state for symbol in word: if symbol not in self.alphabet: return False try: state = self.transitions[(state, symbol)] except KeyError: return False return state in self.final_states def complete(self, alphabet: frozenset[str] | None = None) -> DFA: """Complete the machine over ``alphabet`` with a rejecting sink.""" ambient = self.alphabet if alphabet is None else alphabet if not self.alphabet <= ambient: raise ValueError("the ambient alphabet cannot remove old symbols") states = set(self.states) sink = "sink" while sink in states: sink += ":sink" transitions = dict(self.transitions) missing = [ (state, symbol) for state in states for symbol in ambient if (state, symbol) not in transitions ] if missing: states.add(sink) for key in missing: transitions[key] = sink for symbol in ambient: transitions[(sink, symbol)] = sink return DFA( ambient, frozenset(states), self.initial_state, self.final_states, transitions, ) def complement(self) -> DFA: """Return the complement relative to this machine's alphabet.""" complete = self.complete() return DFA( complete.alphabet, complete.states, complete.initial_state, complete.states - complete.final_states, dict(complete.transitions), ) ends_in_a = DFA( frozenset({'a', 'b'}), frozenset({'no-a', 'a'}), 'no-a', frozenset({'a'}), { ('no-a', 'a'): 'a', ('no-a', 'b'): 'no-a', ('a', 'a'): 'a', ('a', 'b'): 'no-a', }, ) does_not_end_in_a = ends_in_a.complement() assert ends_in_a.accepts('bba') assert not does_not_end_in_a.accepts('bba') assert does_not_end_in_a.accepts('abb') ``` ## Intersection Suppose $G_1$ recognizes $A$ and $G_2$ recognizes $B$. De Morgan's law gives $$ A\cap B=\overline{\overline{A}\cup\overline{B}}. $$ This identity gives one construction: complement both machines, take their union, and complement the result. But every complement must use the same universe. If $G_1$ uses $\Sigma_1$ and $G_2$ uses $\Sigma_2$, we first set $\Sigma=\Sigma_1\cup\Sigma_2$ and complete both machines over $\Sigma$. Fix an arbitrary $w\in\Sigma^*$. Then $$ \begin{aligned} w\in\overline{\overline{A}\cup\overline{B}} &\iff w\notin\overline{A}\cup\overline{B}\\ &\iff w\notin\overline{A}\text{ and }w\notin\overline{B}\\ &\iff w\in A\text{ and }w\in B\\ &\iff w\in A\cap B. \end{aligned} $$ Why do we insist on a common alphabet? Let $A=a^*$ be presented over $\{a\}$ and $B=b^*$ over $\{b\}$. Their intersection relative to $\{a,b\}^*$ is $\{\epsilon\}$. Complements taken separately over $\{a\}^*$ and $\{b\}^*$ do not describe languages in one shared universe. So the common alphabet is part of the operation, not mere bookkeeping. ### Direct product construction We can compute the intersection more directly. Complete both DFAs over the common alphabet and let the new machine track a pair of states. Its components move on the same input symbol, and a pair is final only when both components are final. For complete DFAs $$ G_1=\langle Q_1,\Sigma,\delta_1,q_1,F_1\rangle \quad\text{and}\quad G_2=\langle Q_2,\Sigma,\delta_2,q_2,F_2\rangle, $$ define the product by $$ \begin{aligned} Q&=Q_1\times Q_2,\\ q_0&=(q_1,q_2),\\ F&=F_1\times F_2,\\ \delta((r_1,r_2),\sigma) &=(\delta_1(r_1,\sigma),\delta_2(r_2,\sigma)). \end{aligned} $$ What does a product state mean? The **paired-state invariant** says that after reading a prefix $x$, the product is in $(r_1,r_2)$ exactly when $G_1$ is in $r_1$ after $x$ and $G_2$ is in $r_2$ after $x$. Before any input is read, the product is $(q_1,q_2)$, so the invariant holds. Now suppose it holds after $x$ and read a symbol $\sigma$. The product transition applies the two component transitions to that same symbol. Its new state is thus exactly the pair reached by the two component machines after $x\sigma$. This proves the inductive step. After the full string $w$, the product is final exactly when both component states are final. By the invariant, that happens exactly when $w\in A$ and $w\in B$. Thus, the product recognizes $A\cap B$. The method below explores only product states reachable from the initial pair. Length-prefixed labels keep distinct state pairs distinct when we store the pairs as strings. ```{python} def pair_label(left: str, right: str) -> str: """Serialize a pair of strings without delimiter collisions.""" return f'{len(left)}:{left}{len(right)}:{right}' def intersection(left: DFA, right: DFA) -> DFA: """Construct the direct-product intersection of two DFAs.""" alphabet = left.alphabet | right.alphabet left = left.complete(alphabet) right = right.complete(alphabet) initial_pair = (left.initial_state, right.initial_state) pending = [initial_pair] visited: set[tuple[str, str]] = set() transitions: dict[tuple[str, str], str] = {} while pending: pair = pending.pop() if pair in visited: continue visited.add(pair) for symbol in sorted(alphabet): target = ( left.transitions[(pair[0], symbol)], right.transitions[(pair[1], symbol)], ) transitions[(pair_label(*pair), symbol)] = pair_label(*target) if target not in visited: pending.append(target) final_states = frozenset( pair_label(*pair) for pair in visited if pair[0] in left.final_states and pair[1] in right.final_states ) return DFA( frozenset(alphabet), frozenset(pair_label(*pair) for pair in visited), pair_label(*initial_pair), final_states, transitions, ) a_star = DFA( frozenset({'a'}), frozenset({'q'}), 'q', frozenset({'q'}), {('q', 'a'): 'q'}, ) b_star = DFA( frozenset({'b'}), frozenset({'q'}), 'q', frozenset({'q'}), {('q', 'b'): 'q'}, ) only_empty = intersection(a_star, b_star) assert only_empty.accepts('') assert not only_empty.accepts('a') assert not only_empty.accepts('b') assert not only_empty.accepts('ab') ``` The direct product usually avoids the repeated determinization required by the De Morgan construction. Both constructions establish the same closure result: the intersection of two regular languages is regular.