| Meno: | Tatiana
|
|---|
| Priezvisko: | Tóthová
|
|---|
| Názov: | Sila a zložitosť moderných regulárnych výrazov
|
|---|
| Vedúci: | RNDr. Michal Forišek PhD.
|
|---|
| Rok: | 2015
|
|---|
| Blok: | INF
|
|---|
| Kľúčové slová: | regex, spätné referencie, pozitívny a negatívny lookaround, lookahead, lookbehind, priestorová zložitosť
|
|---|
| Abstrakt: | Skúmali sme moderné regulárne výrazy špecifikované v jazyku Python z hľadiska teórie formálnych jazykov. Nové konštrukcie rozširujúce klasické regulárne výrazy sú spätné referencie, pozitívny a negatívny lookaround. Práca naväzuje na výsledky o spätných referenciách a pozitívnom lookarounde a doplňuje výsledky do hierarchie tried regexov nad rôznymi množinami operácií, ako napríklad neporovnateľnosť s bezkontextovými jazykmi. Ďalej ukazujeme, že uzavretosť triedy s pozitívnym lookaroundom na zreťazenie nie je triviálne a dokázali sme vlastnosti negatívneho lookaroundu podobné ako pri pozitívnej verzii. V oblasti priestorovej zložitosti sme zistili, že regexy s~pozitívnym lookaroundom potrebujú priestor NSPACE(log n) a s pridaným negatívnym lookaroundom dosiahneme DSPACE((log n)^2). Pokiaľ na vstup dostávame zároveň regex aj slovo, zložitosť pre triedu s pozitívnym lookaroundom je NSPACE(n*log n) a výsledok DSPACE(n*(log n)^2) platí iba ak je zaručená konštantná hĺbka vnorenia lookaroundov. K dôkazom sme zaviedli nový formálny model s konfiguráciami a krokom výpočtu inšpirovaný Turingovým strojom.
|
|---|