2012.07.17 11:29
małpa niemałpa małpa
Od dawna myślę, jakim by wyrażeniem regularnym szukać dwu słów "małpa", między którymi będzie tekst niezawierający słowa "banan". I nad problemem, który wydaje mi się bardzo podobny: napisać wyrażenie regularne, które będzie szukać dwu słów "małpa", między którymi będzie tekst niezawierający słowa "małpa", ale bez użycia kwantyfikatorów niezachłannych. Już wczoraj przed snem myślałem, że mam: m/malpa([^b]|b[^a]|ba[^n]|ban[^a]|bana[^n])*(b|ba|ban|bana)?malpa/. Ale nie - to wyrażenie wykłada się na napisie "xmalpabbananmalpay". Znaczy, z tego napisu wyciąga fragment "malpabbananmalpa", choć ewidentnie ten fragment zawiera banana między małpami.
komentarze:
2012.07.17 12:03 Daniel
Czy przez wyrażenie regularne rozumiesz wyrażenie posixowe podstawowe, posixowe rozszerzone, PCRE czy jeszcze coś innego? Bo jeśli PCRE, to takie rzeczy załatwia się przez negative zero-width lookahead assertions, czyli: malpa(.(?!banan))*malpa (nietestowane, ale powinno działać).
2012.07.17 14:18 Marcin Gryszkalis
negative lookahead jest fajne, ale ze względu na to że jest zero-width to nie zjada nic, i stąd po pierwsze musiałbyś dodać co zje tego nie-banana pomiędzy małpami, a po drugie ciężko (czy może niemożliwe) będzie napisanie tego tak, żeby nie wywalało się na ciągu \"małpa małpa banan\" czy \"małpa małpa banan małpa\"...
2012.07.17 21:23 Piotrek
Dopuszczam tylko takie porządne wyrażenia regularne, czyli takie, które opisują jakąś gramatykę regularną. Więc negative lookahead odpada, chyba (tak, też o nim myślałem).
2012.07.18 01:27 Piotrek
Zresztą nawet przy użyciu lookaheada to nie jest takie proste, jak piszesz, Danielu. Moim zdaniem przy użyciu lookaheada nie da się zrobić prościej niż tak:
/(malpa([^b]|b(?!a)|ba(?!n)|ban(?!a)|bana(?!n))*malpa)/
2012.07.18 01:29 Piotrek
...przy okazji sprawdziłem: powyższe wyrażenie poprawnie radzi sobie z napisami \"małpa małpa banan\" i \"małpa małpa banan małpa\".
Ale problem nadal nie jest rozwiązany - bo chodzi o to, jak to zrobić normalnym, porządnym, wyrażeniem regularnym. I czy się w ogóle da.
2020.05.16 09:54 Marcin
Moim zdaniem się da. Z tym, że mój dowód pokazuje tylko to, jak zrobić takie wyrażenie regularne, a nie to, jak ono będzie wyglądało.
1. Kiedy się buduje deterministyczne automaty skończone z wyrażeń regularnych za pomocą pochodnych Brzozowskiego, można korzystać z szerszego zestawu operatorów niż w tradycyjnych w.r., m.in. dopełnienia w.r. (¬R) i części wspólnej w.r. (R∧S). Rodzina w.r. jest zamknięta ze względu na taki rozszerzony zestaw operatorów, czyli co byśmy korzystając z nich nie napisali, zawsze to, co nam wyjdzie, będzie w.r.
2. Teraz już z górki: budujemy DFA do rozpoznawania napisów pasujących do w.r. /małpa((.*)∧¬(.*małpa.*))małpa/, a potem zamieniamy ten DFA na zwykłe w.r. bez dodatkowych operatorów. Musi nam się udać, bo język rozpoznawany przez każdy DFA można opisać przez w.r. ze zwykłym zestawem operatorów. Inna rzecz, że długość tego w.r. nie będzie liniowa względem długości małpy, tylko jakaś inna (kwadratowa?).
2020.05.16 19:03 Marcin
Ha, teraz zrozumiałem, gdzie tkwi haczyk w wersji z unikaniem trzeciej małpy pośrodku. Mimo to uważam, że mój dowód da się uratować takim w.r.:
/(małpa.*małpa)∧¬(małpa.*małpa.*małpa)/
Kiedyś napisałem budowanie DFA z w.r. pochodnymi Brzozowskiego. Jeśli uda mi się je odkopać, nakarmić powyższym w.r. i wyciągnąć z niego DFA w czytelnym formacie, to dam tu znać.
powrot na strone glowna
RSS