Co znamená ∅ v regulárním výrazu?
Jaký je rozdíl mezi ∅ a ε? Co vznikne operacemi součet a zřetězení, např ∅a, a∅, (a+∅)?
Jaký je rozdíl mezi ∅ a ε? Co vznikne operacemi součet a zřetězení, např ∅a, a∅, (a+∅)?
Jak tyto speciální RV interagují s jinými najdete na 4. slídě 4. přednášky z AAG.
Pokud však tyto operace chápete, jde to jednoduše odvodit: Zřetězení spojuje všechny možné hodnoty jednoho RV s možnými hodnotami druhého RV, a protože ∅ má 0 možností, celkem vyjde také 0 možností, takže ∅a = ∅. "Součet" možné hodnoty sjednocuje, a ∅ žádné nemůže přidat. (a + ∅), neboli "a nebo žádná další možnost" je vlastně totéž jako a.
Asi tak stejný rozdíl jako mezi prázdnou peněženkou a žádnou peněženkou. Když nemám peněženku a strčím do ní peníze, tak pořád nemám peněženku (a už ani ty peníze, vypadly na ulici). Když mám peníze nebo nemám peneženku, no tak mám vlastně jen ty peníze.
A teď vážně. ε je prázdný řetězec, takže vlastně něco jako "". ∅ je prázdná množina, takže neobsahuje vůbec nic (ani to epsilon). Když udělám εa (""."a"), dostanu a, ∅a mi dá ∅. ε+a, je stále ε nebo a. ∅+a můžu zkrátit na a.
A ještě matematický pohled na věc. Ono jsou to vlastně jen nějaké monoidy, takže to celé (doufám, že se nepletu) tvoří nějaký polookruh. Když to převedu třeba na sčítání a násobení, kdy zřetězení je právě to násobení, tak ∅ se chová jako 0 (a je to neutrální prvek pro sčítání), ε je pak neutrální prvek pro násobení. No a násobení nulou (zřetězení s ∅) se chová tak, jak čekáme.
Zřetězení s prázdnou množinou je pouze prázdná množina, sjednocení se dá zjednodušit pouze na původní řetězec (naopak zřetězení s prázdným řetězcem je původní řetězec a ve sjednocení zůstávají oba dva).
řetězení vyjde zase prázdná množina, součet bude 'a' a pokud prázdnou množinu iteruješ, vyjde eps, tyhle vztahy jsou shrnutý na slidech z přednášky ;-)
Asked: Nov 21 '14
Seen: 296 times
Last updated: Nov 21 '14