Co znamená ∅ v regulárním výrazu?
asked 2014-11-21 13:59:41 +0100
Jaký je rozdíl mezi ∅ a ε? Co vznikne operacemi součet a zřetězení, např ∅a, a∅, (a+∅)?
5 Answers
answered 2014-11-21 14:23:43 +0100
- ∅ je prázdný regulární výraz, tzn. takový, jemuž neodpovídá žádný řetězec.
- ε je regulární výraz, kterému odpovídá právě jeden řetězec, a to prázdný řetězec ε, neboli řetězec nulové délky.
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.
answered 2014-11-21 14:28:39 +0100
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.
answered 2014-11-21 14:26:14 +0100
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).
answered 2014-11-21 14:25:09 +0100
ř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 ;-)
answered 2014-11-21 14:23:00 +0100
Nevim všechno, ale a∅=nic. Zato ale a∅* = a myslim.
Stats
Asked: 2014-11-21 13:59:41 +0100
Seen: 296 times
Last updated: Nov 21 '14
