Kalábovi

Kalábovic wikina

Uživatelské nástroje

Nástroje pro tento web


pitel:msz:regularni_vyrazy

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í (PQ), 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 PQ
    • (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:

  1. a*b = a(a*b) + b
  2. a*b = ab + 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 ≤ in. 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
/var/www/wiki/data/pages/pitel/msz/regularni_vyrazy.txt · Poslední úprava: 03. 07. 2012, 13.53:31 (upraveno mimo DokuWiki)