regexp - vse krome retezce

Pavel Kankovsky peak na argo.troja.mff.cuni.cz
Čtvrtek Září 23 14:26:56 CEST 2004


On Thu, 23 Sep 2004, Pavel Toser wrote:

> Vyraz by mel vyhovovat jekemukoliv znaku (retezci) krome
> retezce obsahujiciho podretezec "abc" nebo "xyz" kdekoliv v
> retezci. Doufam, ze jsem to popsal srozumitelne :).

Takze pokud abecedu oznacime A a mnozinu vsechn slov v teto abecede
A^* a mnozinu slov v A obsahujicich retezec X oznacime A^*[X]
(mozna na to existuje nejaka oficialni notace, ale ted si na
ni nevzpomenu) pak chcete regularni vyraz popisujici mnozinu slov
(jazyk) popsany vyrazem A^* - (A^*["abc"] \cup A^*["xyz"]), ano?

Nejprve vyresme jednodussi ulohu, totiz L = A^* - A^*["abc"].

Zavedme notaci L1*L2 pro jazyk vznikly konkatenaci vsech kombinaci
slov z L1 a L2 (v tomto poradi), A^1 pro jednoznakova slova z A.

Reseni teto jednodussi ulohy, je "^(|c|bc)([^c]|[^b]c|[^a]bc)*$".
Najdeme ho nasledujici uvahou:
1. {"", "c", "bc"} \subset L
2. L * (A^1 - {"c"}) \subset L
3. L * (A^1 - {"b"}) * {"c"} \subset L
4. L * (A^1 - {"a"}) * {"bc"} \subset L

Ad 1. prazdny retezec, "c" a "bc" neobsahuji "abc"
Ad 2.-4. pokud na konec slova z L pridame neco, co bud neobsahuje
  "c" nebo ma pred "c" neco, co neumoznuje vytvorit "abc", pak mame
  opet slovo z L
Dukaz, ze v L nejsou zadna slova, ktera nelze vytvorit pravidly 1.-4.,
je ponechan jako cviceni pro ctenare.

Pro dva retezce to lze take resit, ale uz se potykame s mensi
kombinatorickou explozi (a bylo by to jeste horsi, kdyby zadane retezce
mely nejake spolecne podretezce), takze si to uz vyreste sam. :)

Je to v podstate mechanicka uloha, kdy se regularni vyrazy prevedou
na konecne automaty, vytvori se kombinace techto konecnych automatu
(de facto jakysi kartezsky soucin) a vysledny k.a. se znovu prevede
na regularni vyraz.

\cup    je znacna pro sjednoceni
\subset je znacka pro inkluzi

PS: Snad se nebudu blamovat nejakym omylem, prece jen je uz ctvrtek a
hlava se uz tesi na vikend. ;)

--Pavel Kankovsky aka Peak  [ Boycott Microsoft--http://www.vcnet.com/bms ]
"Resistance is futile. Open your source code and prepare for assimilation."



Další informace o konferenci Linux