19 - Regulární množiny, regulární výrazy a rovnice nad regulárními výrazy

Question 1

Způsoby prezentace regulárních jazyků

Answer 1

• 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

Question 2

Regulární množiny

Answer 2

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.

Question 3

Regulární výrazy (RV)

Answer 3

• 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

Question 4

Kleeneho algebra

Answer 4

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

Question 5

Rovnice nad regulárními výrazy

Answer 5

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í.

Question 6

Algoritmus převodu RV na rozšířený KA

Answer 6

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