Ask Your Question
2

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

asked 2014-11-21 13:59:41 +0100

Vadim Petrov gravatar image

updated 2014-11-21 14:27:51 +0100

Miro Hrončok gravatar image

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

edit retag flag offensive close delete

5 Answers

Sort by » oldest newest most voted
2

answered 2014-11-21 14:23:43 +0100

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.

edit flag offensive delete publish link more
4

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.

edit flag offensive delete publish link more
0

answered 2014-11-21 14:26:14 +0100

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

edit flag offensive delete publish link more
0

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

edit flag offensive delete publish link more
0

answered 2014-11-21 14:23:00 +0100

beranpa8 gravatar image

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

edit flag offensive delete publish link more

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: 2014-11-21 13:59:41 +0100

Seen: 296 times

Last updated: Nov 21 '14