====== 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//<sup>*</sup>) 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//<sup>*</sup>) je regulární výraz označující regulární množinu //P//<sup>*</sup>
  * 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//<sup>*</sup>//b//. Důkaz:
  - //a//<sup>*</sup>//b// = //a//(//a//<sup>*</sup>//b//) + //b//
  - //a//<sup>*</sup>//b// = //a//⁺//b// + //b//
  - //a//<sup>*</sup>//b// = (//a//⁺ + //ε//)//b//
  - //a//<sup>*</sup>//b// = //a//<sup>*</sup>//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//<sup>*</sup> 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//