Regulární množinu nad abecedou Σ definujeme takto:

• Prázdná množina ∅ je regulární množina.
• Množina obsahující pouze prázdný řetezec {ε} je regulární množina.
• Množina {a} po všechna a ∈ Σ je regulární množina.
• Jsou-li P a Q regulární množiny pak také jejich sjednocení (P ∪ Q), konkatenace (P . Q) a iterace (P^*) jsou regulární množiny.
• Regulárními množinami jsou pouze množiny, které lze získat aplikací 1 až 4

Třída regulárních množin je tedy nejmenší třída jazyků, která obsahuje ∅, ε, {a} pro všechny symboly a a je uzavřena vzhledem k operacím sjednoceni, součinu a iterace.

Představují obvyklou notaci regulárních množin.

Regulární výraz nad abecedou Σ definujeme takto:

• ∅ je regulární výraz označující regulární množinu ∅.
• ε je regulární výraz označující regulární množinu {ε}
• a je regulární výraz označující regulární množinu {a}</math> po všechna a ∈ Σ
• Jsou-li p a q regulární výrazy označující regulární množiny P a Q pak:
  • (p + q) je regulární výraz označující regulární množinu P ∪ Q
  • (pq) je regulární výraz označující regulární množinu P . Q
  • (p^*) je regulární výraz označující regulární množinu P^*
• Regulárními výrazy jsou právě ty výrazy, které lze získat aplikací 1 až 4

Algebra se sadou axiomů pro řešení rovnic nad regulárními výrazy.

Algebra (A, +, 0, ., 1, *)

Vazba na regulární výrazy: pokud Σ je abeceda, tak A může být definována jako např. množina všech regulárních výrazů nad touto abecedou.

• + – Operace alternativy (asociativní, komutativní, idempotentní)
• 0 – Neutrální prvek operace alternativy, anihilátor operace konkatenace
• . – Operace konkatenace (asociativní, distributivní nad alternativou)
• 1 – Neutrální prvek operace konkatenace
• ***** – Operace iterace

Regulární přechodový graf je zobecněný KA, který obsahuje množinu počátečních stavů a regulární výrazy na hranách. Každý reg. přechodový graf je možné převést na reg. přechodový graf s jediným přechodem na kterém je hledaný RV.

Rovnice jejichž složky jsou koeficienty a neznámé reprezentující dané a hledané regulární výrazy.

Při řešení se využívají axiomy Kleeneho algebry a klasické postupy řešení soustav rovnic.

Řešením rovnice: X = aX + b je regulární výraz X = a^*b. Důkaz:

1. a^*b = a(a^*b) + b
2. a^*b = a⁺b + b
3. a^*b = (a⁺ + ε)b
4. a^*b = a^*b

Soustava rovnic nad RV je ve standardním tvaru vzhledem k neznámým Δ = {X₁, X₂, …, Xₙ} má-li tvar ∧ Xᵢ = αᵢ₀ + αᵢ₁X₁ + αᵢ₂X₂ + … + αᵢₙXₙ pro 1 ≤ i ≤ n. Je-li soustava rovnic ve standardním tvaru pak existuje její minimální pevný bod (řešení) a algoritmus jeho nalazení.

* pro výraz <math>\epsilon</math> zkonstrujeme <math>\epsilon</math>-přechod * pro výraz x zkonstruujeme přechod se symbolem x * pro výraz <math>\emptyset</math> nekonstruujeme žádný přechod * pro výraz rq sjednotíme koncový stav r a počátečním stavem q * pro výraz r + q zkonstruujeme z počátečního stavu <math>\epsilon</math>-přechody do počátačních stavů r a q a <math>\epsilon</math>-přechody z koncových stavů r a q do koncového stavu * pro výraz r* zkonstruujeme <math>\epsilon</math>-přechod mezi počátečním a koncovým stavem, <math>\epsilon</math>-přechod z počátečního stavu do počátečního stavu r, <math>\epsilon</math>-přechod z koncového stavu r do koncového stavu a <math>\epsilon</math>-přechod z koncového stavu r do počátečního stavu r