Operatori regolari

Union: A ∪ B = {x|x∈A or x∈B}

Concatenation: A ○ B = {xy | x∈A and y∈B}

Star: A* = {x₁, x₂, x₃,...x_k | k ≥ 0 and each x_i∈A }

 

Inoltre si definisce per prassi ε stringa vuota (in maniera simile a quello che in SQL è NULL)

 

La prova dell'unione di A con B è data dalle seguenti cinque considerazioni:

1. Gli stati possibili sono dati dal prodotto cartesiano degli stati A × B: Q = {(r₁, r₂) | r₁∈A and r₂∈B}
2. Σ per ora lo consideriamo un unico dizionario per entrambe le macchine
3. δ è una funzione definita su una coppia di stati alla volta: δ((r₁, r₂), a) = (δ(r₁, a), δ(r₂, a)). Ovviamente lo stato restituito è un elemento di Q, che a sua volta è costituito da "coppie".
4. q₀ = (q₁, q₂)
5. Il risultato è un F = (F₁ × Q₂) ∪ (F₂ × Q₁)

Nota: il risultato NON è F₁ × F₂, perché questo rappresenterebbe l'intersezione dei due automi, e non l'unione, perché entrambi gli stati di uscita dovrebbero essere validi.