14 - Regulární množiny, regulární výrazy a rovnice nad regulárními výrazy
pátek 13. května 2016
10:19
Regulární množiny, regulární výrazy a rovnice nad regulárními výrazy.
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
𝑃∪Q
𝑃⋅𝑄
𝑃∗
𝑃+
{𝜀}
𝑝+𝑞
𝑝𝑞
𝑝∗
𝑝+
𝜀
Kleeneho algebra
𝑝+𝑞
𝑝𝑞
𝑝∗
𝑝+
0
1
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 {𝑎} po všechna 𝑎∈Σ je regulární množina
Jsou-li 𝑃 a 𝑄 regulární množiny pak také jejich sjednocení (𝑷∪𝑸), konkatenace (𝑷⋅𝑸) a iterace (𝑷∗) 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 ∅, 𝜀, {𝑎} pro všechny symboly a a je uzavřena vzhledem k operacím sjednoceni, konkatenace a iterace.
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 {𝜺}
𝑎 je regulární výraz označující regulární množinu {𝒂} po všechna 𝑎∈𝛴
Jsou-li 𝑝 a 𝑞 regulární výrazy označující regulární množiny 𝑃 a 𝑄 pak:
(𝒑+𝒒) je regulární výraz označující regulární množinu 𝑃∪𝑄
(𝒑𝒒) je regulární výraz označující regulární množinu 𝑃⋅𝑄
(𝒑∗) je regulární výraz označující regulární množinu 𝑃∗
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 𝑨, +, 𝟎, ., 𝟏, ∗
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 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: 𝑋=𝑎𝑋+𝑏 je regulární výraz 𝑋=𝑎*𝑏. Důkaz:
𝑎∗𝑏=𝑎+𝑏+𝑏
𝑎∗𝑏=𝑎∗𝑏
Nechť X = pX +q je rovnice nad regulárními výrazy, kde p, q jsou regulární výrazy a p označuje regulární množinu P takovou, že 𝜺 𝝐 P. Pak 
X = p*(q + r)
je řešením této rovnice pro libovolné r (kterému nemusí ani odpovídat regulární množina, ale případně i obecnější jazyk).
Obvykle ale hledáme ”nejmenší řešení“, tzv. nejmenší pevný bod, dané rovnice.
Nejmenším pevným bodem rovnice X = pX + q je: X = p*q
Soustava rovnic nad RV je ve standardním tvaru vzhledem k neznámým 𝛥={𝑋₁, 𝑋₂, …, 𝑋𝑛} má-li tvar:
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
Notes
1. Otazka (předmět) (okruh): Regulární množiny, regulární výrazy
Kdo me primarne zkousel: Janoušek Jan, doc. Ing., Ph.D. (z Prahy)
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Řek jsem všechno co co jsem se učili, ptal se na druhy Rovnic nad regulárními výrazy - levá a pravá (netušil jsem), a k čemu se používá (převod KA a gramatiky na regulární výrazy) + nějaký příklady 
From <[link]> 
1. Otazka (okruh): Regulární množiny, regulární výrazy a rovnice nad regulárními výrazy
Kdo me primarne zkousel: Janoušek
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: chtěl pravidlo regulární gramatiky převést na rovnici, pevný bod
From <[link]> 
2. Otazka (okruh): Regulární množiny
Kdo me primarne zkousel: Hruška / později Vojnar
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Tuhle otázku jsem při učení přeskakoval s tím, že je příliš lehká než aby ji dali. Hruška i Vojnar se mě snažili dokopat k odpovědi, ale já jsem se nenechal a vyplodil jsem nějaké náznaky...
 Dokonce vstávali a psali definice za mě... Chtěli základy a když jsem nevěděl základy, chtěli ještě větší základy, ale ty jsem taky nevěděl, protože jsem se už nacházel ve stavu zmaru, z toho, že jsem nevěděl předchozí základy 
Z mé strany naprostá tragédie. Naštestí asi pomohla diplomka nebo vyšší síla, ale dali.
From <[link]> 
2. Otazka (okruh): 33. Regulární množiny
Kdo me primarne zkousel: Ryšavý
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Na papírku to byl docela škrabopis, takže jsem se podle čísla ujišťoval, jestli fakt mám dva TINy. Tady se mi z hlavy vykouřilo všechno co jsem věděl, nevěděl jsem jak začít, co všechno říct, hodně jsem znejistel co všechno tvoří reg. množinu. Řekl jsme jak se tvoří, co vyjadřuje, a pak se otázkama snažil ze mě něco dostat, což se jakš takš dařilo. Nemluvil jsem blbosti, ale mluvil jsem málo. Když zazvonil budík tak ještě chtěl rovnici a raději to ukončil. E
From <[link]> 
Regulární množiny, regulární výrazy a rovnice nad regulárními výrazy.
Kdo me primarne zkousel: Hruška
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Podotázka byla: vztah DTD a regulárních výrazů. Proč DTD popisuje bezkontextový jazyk (XML)? Něco jsem vyplodil, už sám nevím co...
From <[link]> 