Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- msz:regularni_vyrazy [07. 06. 2012, 09.34:12] – [Algoritmus převodu RV na rozšířený KA] pitel
+++ msz:regularni_vyrazy [11. 08. 2026, 10.08:15] (aktuální) – odstraněno - upraveno mimo DokuWiki (Neznámé datum) 127.0.0.1
@@ Řádek 1: / Řádek 1: @@
-====== 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í 1 až 4
-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//}</math> 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í 1 až 4
-===== 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//

Kalábovi

Uživatelské nástroje

Nástroje pro tento web

Rozdíly

Nástroje pro stránku