Regulární množiny, regulární výrazy a rovnice nad regulárními výrazy

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í předchozího

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} 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í předchozího

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 ε zkonstruujeme ε-přechod
• Pro výraz x zkonstruujeme přechod se symbolem x
• Pro výraz ∅ nezkonstruujeme žá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 ε-přechody do počátačních stavů r a q a ε-přechody z koncových stavů r a q do koncového stavu
• Pro výraz r^* zkonstruujeme ε-přechod mezi počátečním a koncovým stavem, ε-přechod z počátečního stavu do počátečního stavu r, ε-přechod z koncového stavu r do koncového stavu a ε-přechod z koncového stavu r do počátečního stavu r