Automaten (Operationen: Durchschnitt)

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

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

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

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

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

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