Ask Your Question
2

Co znamená ∅ v regulárním výrazu?

asked Nov 21 '14

Vadim Petrov gravatar image

updated Nov 21 '14

Miro Hrončok gravatar image

Jaký je rozdíl mezi ∅ a ε? Co vznikne operacemi součet a zřetězení, např ∅a, a∅, (a+∅)?

add a comment

5 Answers

Sort by » oldest newest most voted
2

answered Nov 21 '14

Viktor Chlumský gravatar image
  • ∅ 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.

link
add a comment
4

answered Nov 21 '14

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.

link
add a comment
0

answered Nov 21 '14

Zdeněk Kasner gravatar image

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

link
add a comment
0

answered Nov 21 '14

ř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 ;-)

link
add a comment
0

answered Nov 21 '14

beranpa8 gravatar image

Nevim všechno, ale a∅=nic. Zato ale a∅* = a myslim.

link
add a comment

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!

Add answer

[hide preview]

Question tools

Follow
1 follower

Stats

Asked: Nov 21 '14

Seen: 296 times

Last updated: Nov 21 '14