19 - Regulární množiny, regulární výrazy a rovnice nad regulárními výrazy Flashcards
Způsoby prezentace regulárních jazyků
- Všechny tyto způsoby zápisu jsou ekvivalentní
- Všechny umožňují zapsat jazyky typu 3 Chomského hierarchie
Alternativa Konkatenace Iterace Pozitvní iterace Neutr. prvek alternativa Neutr. prvek konkatenace Regulární množiny P∪Q P⋅Q P^∗ P^+ ∅ {ε} Regulární výrazy p+q pq p^∗ p^+ ∅ ε Kleeneho algebra p+q pq p^∗ p^+ 0 1
- Všechny umožňují zapsat jazyky typu 3 Chomského hierarchie
Regulární množiny
Regulární množinu nad abecedou Σ definujeme takto:
1. Prázdná množina ∅ je regulární množina 2. Množina obsahující pouze prázdný řetezec {ε} je regulární množina 3. Množina {a} po všechna a∈Σ je regulární množina 4. 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 5. 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, konkatenace a iterace.
Regulární výrazy (RV)
• Představují obvyklou notaci regulárních množin.
Regulární výraz nad abecedou Σ definujeme takto:
1. ∅ je regulární výraz označující regulární množinu ∅.
2. ε je regulární výraz označující regulární množinu {ε}
3. a je regulární výraz označující regulární množinu {a} po všechna a∈Σ
4. 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, ∗) - Je to okruh s jednotkovým prvkem.
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
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.
Druhy: levá a pravá
Použití: převod KA a gramatiky na regulární výrazy
Ř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=a^+ b+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_n} má-li tvar:
• ⋀8_(1≤i≤n)▒〖X_i=α_i0+α_i1 X_1+α_i2 X_2+…+α_in X_n 〗
• kde αij jsou regulární výrazy nad nejakou abecedou ∑, ∑ \ Δ = ∅.
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
Algoritmus převodu RV na rozšířený KA
* pro výraz ε zkonstrujeme ε-přechod * pro výraz x zkonstruujeme přechod se symbolem x * pro výraz ∅ nekonstruujeme žá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