Някои хора обичат честичко да използват регулярни изрази. Аз също съм от тях. Понякога някои от тези хора се сблъскват със следния проблем: какъв би бил регулярен израз, който отговаря на думи несъдържащи в себе си низа баба.
След кратки справки с книги, интернет и perldoc и местни perl гуру-та стана ясно, че лесен начин наистина няма. Набързо обаче се сетих за един труден. Поне на пръв поглед труден.
Всеки регулярен израз описва един език – това е множеството от думи, които на практика този регулярен израз match-ва (български превод?). Всеки език описан с регулярен израз се нарича регулярен език (защо ли…). Езиците породени от крайни автомати се наричат автоматни.
Теорема на Клини: Регулярните езици и автоматните езици съвпадат.
Сега захождаме към съставяне на нашия регулярен израз – опитваме се да си построим краен автомат, който да описва езика, който ние искаме. Тъй като обаче някакво вътрешно чувство ни води, решаваме да си опишем езика, който включва всички думи несъдържащи в себе си ба вместо баба. От втория път успяваме да си построим едно крайно детерминирано автоматче:
Малка забележка: дискретната математика не вярвам да познава означението ^xyz, но в нашия случай (благодарим на perl) с това чудо означаваме множеството на всички букви от азбуката, без x, y и z.
Сега остава по този автомат да си съставим регулярния израз.
Както доста от доказателствата на теореми от дискретната математика и това на Клини е конструктивно и от него получаваме алгоритъм за намиране на регуларярен израз, съответен да даден краен автомат. Няма да се впускам в подробности. Доказателството, както и алгоритъма ги има във вероятно всеки учебник по дискретна математика. След една-две страници сметки накрая от горния автомат получаваме следния регулярен израз, записан в термините на езика perl:
(([^b]*)|([^b]*b(([^ab][^b]*b)|b)*)|([^b]*b(([^ab][^b]*b)|b)*[^ab][^b]*))
Ето и по-грозна негова версия:
( [^b]* ) |
( [^b]* b ( ( [^ab] [^b]* b ) | b )* ) |
( [^b]* b ( ( [^ab] [^b]* b ) | b )* [^ab] [^b]* )
Това е. Ето тук има примерно скриптче, което използва горния регулярен израз и проверява верността му за всички думи с дължина по-малка или равна на 5 върху азбуката {a,b,c,d}.
П.П. Подозирам, че горният израз може да се поопрости и дължината му да се намали поне наполовина. Спи ми се…
П.П.П. Нищо чудно това да може да се направи и с двадесетинасимволен израз. Не ми пука :)