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

Regulární množiny

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.

Regulární výrazy (RV)

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

Kleeneho algebra

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

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 nad regulárními výrazy

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:

a*b = a(a*b) + b

a*b = a⁺b + b

a*b = (a⁺ + ε)b

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í.

Algoritmus převodu RV na rozšířený KA

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