====== 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//