Automaten (Operationen: Durchschnitt)

Eingabe: A₁ = (Σ, Q₁, I₁, δ₁, F₁), A₂ = (Σ, Q₂, I₂, δ₂, F₂),

Ausgabe: A mit Lang(A) = Lang(A₁)∩Lang(A₂)

Lösung durch Kreuzprodukt-Konstruktion: A = (Σ, Q, I, δ, F) mit

• Q = Q₁×Q₂ (daher der Name)
• I = I₁×I₂, F = F₁×F₂
• δ(c)((p₁, p₂),(q₁, q₂)) = ...

Korrektheit: ∀w∈Σ^* : w∈Lang(A)$\iff$w∈Lang(A₁)∧w∈Lang(A₂)

Komplexität: | Q| = | Q₁|⋅| Q₂| (hier: Zeit = Platz)