Na potrzeby tego wyzwania mówimy, że wzór wyrażenia regularnego pasuje do łańcucha, jeśli cały łańcuch jest dopasowany przez wzorzec, a nie tylko podłańcuch.

Biorąc pod uwagę dwa wzorce wyrażeń regularnych  A  i  B , mówimy, że  A  jest bardziej wyspecjalizowany niż  B,   jeśli każdy ciąg pasujący do  A  jest również dopasowany przez  B,   ale nie na odwrót. Mówimy, że   jest równoważny do  B  , jeśli oba wzory pasują dokładnie ten sam zestaw strun. Jeśli żaden wzorzec nie jest bardziej wyspecjalizowany niż drugi i nie są one równoważne, mówimy, że  A  i  B  są nieporównywalne .

Na przykład wzorzec Hello, .*!jest bardziej wyspecjalizowany niż .*, .*!; wzory (Hello|Goodbye), World!i Hello, World!|Goodbye, World!są równoważne; i wzory Hello, .*!i .*, World!są nieporównywalne.

Relacja „bardziej wyspecjalizowana niż” określa ścisłe częściowe uporządkowanie zbioru wzorców wyrażeń regularnych. W szczególności, dla wszystkich wzorów  A  i  B , dokładnie jedna z następujących czynności:

• A  jest bardziej wyspecjalizowany niż  B  ( A < B ).
• B  jest bardziej wyspecjalizowany niż  A  ( A > B ).
• A  i  B  są równoważne ( A = B ).
• A  i  B  są nieporównywalne ( A ∥ B ).

Gdy  A  i  B  są nieporównywalne, możemy dalej rozróżnić dwa przypadki:

• A  i  B  są rozłączne ( A ∥ B ), co oznacza, że ​​żaden łańcuch nie pasuje do nich obu.
•  I  B  są przecinające się ( A ≬ B ), co oznacza, że niektóre ciągi są dopasowane zarówno.

Wyzwanie

Napisz program lub funkcję, która bierze parę wzorców wyrażeń regularnych i porównuje je w powyższej kolejności. Oznacza to, że jeśli dwa wzory są   i  B , program powinien ustalić, czy  A < B ,  A > B , A = B  lub  A ∥ B .

× 92% Premia  Dodatkowa premia jest przyznawana, jeśli gdy wzorce są nieporównywalne, program określa, czy się przecinają, czy rozłączają.

Wejście i wyjście

Program powinien zaakceptować dwa wzorce wyrażeń regularnych, jako ciągi znaków, w smaku zdefiniowanym poniżej. Możesz odczytać dane wejściowe poprzez STDIN , wiersz poleceń , jako argumenty funkcji lub równoważną metodę . Możesz założyć, że wzorce są prawidłowe.

Program powinien wygenerować jeden z dokładnie czterech różnych wyników (lub pięć różnych wyników, jeśli wybierasz powyższą premię), w zależności od wyniku porównania (dokładne wyniki zależą od Ciebie.) Możesz zapisać wynik w STDOUT , zwróć jako wynik funkcji lub użyj równoważnej metody .

Smak Regex

Możesz obsługiwać dowolne funkcje wyrażenia regularnego, które lubisz, ale musisz obsługiwać następujące:

• Alternacja z |.
• Kwantyfikacja za pomocą *.
• Grupowanie za pomocą (i ).
• Dopasowywanie dowolnego znaku (ewentualnie z wyłączeniem nowych linii) z ..
• (Opcjonalnie: × 80% Premia)  Dopasowywanie prostych i negowanych klas postaci odpowiednio z […]i [^…]. Nie musisz obsługiwać żadnych predefiniowanych klas znaków (np. [:digit:]), Ale powinieneś obsługiwać zakresy znaków.
• Postać ucieka z \. Powinno być możliwe przynajmniej zaszyfrowanie znaków specjalnych (tj. |*().[^-]\), A najlepiej także zwykłych znaków specjalnych w innych smakach (np. {}), Ale zachowanie podczas ucieczki znaków niespecyficznych nie jest określone. W szczególności nie musisz obsługiwać specjalnych sekwencji specjalnych, takich jak \nznak nowej linii i tym podobne. Możliwą implementacją jest po prostu wzięcie znaku \za literał.

Możesz założyć, że istnieje znak wejściowy, który nie może być dopasowany żadną literałem (tzn. Może być dopasowany tylko przez .negowane klasy znaków).

Dodatkowe zasady

• Możesz używać bibliotek wyrażeń regularnych lub wbudowanej funkcji wyrażeń regularnych tylko w celu dopasowywania i zastępowania ciągów.
• Możesz zignorować wszelkie problemy związane z ustawieniami regionalnymi, takie jak reguły sortowania.
• Aby stwierdzić oczywiste: twój program musi się zakończyć. Powinien wykonać się w rozsądnym czasie, biorąc pod uwagę typowe wzorce (zdecydowanie nie więcej niż godzinę, najlepiej znacznie krócej).

Punktacja

To jest golf golfowy. Twój wynik jest produkt o wielkości kodu w bajtach, a każda z premii . Na najniższym wynikiem wygrywa.

Przypadki testowe

Format przypadków testowych jest następujący:

<Test ID>
<Pattern A>
<Ordering>
<Pattern B>

<Test ID>
<Pattern A>
<Ordering>
<Pattern B>

...

Gdzie <Test ID>jest identyfikatorem przypadku testowego <Pattern A>i <Pattern B>jest wzorcami wyrażeń regularnych oraz <Ordering>jest kolejnością między nimi i jest jednym z:

• <: <Pattern A>jest bardziej wyspecjalizowany niż <Pattern B>.
• >: <Pattern B>jest bardziej wyspecjalizowany niż <Pattern A>.
• =: Wzory są równoważne.
• |: Wzory są nieporównywalne i rozłączne.
• X: Wzory są nieporównywalne i przecinają się.

Specjalna wartość <empty pattern>oznacza pusty wzór.

A. Podstawowe wzorce

A1
Hello
=
Hello

A2
Hello
|
World

A3
Hell(|o)
=
Hell|Hello

A4
x
<
.

A5
.
>
x

A6
\.
<
.

A7
x|y
=
y|x

A8
x|y
X
y|z

A9
x|y
|
a|b

A10
x|y|z
>
x|z

A11
x.
X
.x

A12
.*
>
<empty pattern>

A13
()*
=
<empty pattern>

A14
x*
>
xxxx

A15
x*
>
x|xx|xxxx*

A16
x*
=
|x|xx|xxxx*

A17
x*
<
.*

A19
(.|..)*
=
.*

A20
(...)*
X
(..)*

A21
...*
X
(..)*

A22
...*
<
..*

A23
(...)*
|
Four

A24
a*
X
a.*

A25
a*
|
b.*

A26
x*
=
(x|)*

A27
(((.*)*)*)*
=
.*

B. Złożone wzorce

B1
aaa*
=
aa*a

B2
aa*a
=
a*aa

B3
a*
X
aaax||a|aa|aaa

B4
aaaaaaaaaaaaaa*
X
(aa)*|(aaa)*

B5
a*b*
<
(a|b)*

B6
((a|b)(a|b))*
>
(ab|ba)*

B7
((a|b)(a|b))*
=
(aa|ab|ba|bb)*

B8
.*.*
=
.*

B9
(x*y*z*)*
=
(x|y|z)*

B10
(...|.....)*
>
.........*

B11
(...|.....)*
=
|...|.....|......|.........*

B12
(...|......)*
<
|...|.......*

B13
(...|....|.....)*
=
|....*

B14
(...|x...............|x..x)*
>
(...|x..............|x..x)*

B15
(...|x...............|x..x)*
<
(..|...|x..............|x..x)*

B16
(____)*_x__(____)*
|
(____)*x___(____)*

B17
(____)*_x__(____)*
X
(_____)*x_____(_____)*

B18
(____)*_x__(____)*
|
(______)*x______(______)*

B19
(____)*_x__(____)*
<
_*x__*

C. Podstawowe wzorce z klasami postaci

C1
[x]
=
x

C2
[xy]
|
xy

C3
[abc]
=
a|b|c

C4
[abc]
>
[ab]

C5
[abc]
<
[abcd]

C6
[ab]
X
[bc]

C7
[ab]
|
[cd]

C8
[abc]*
>
(a|b)*

C9
[^xyz]
>
a

C10
[^xyz]
|
x

C11
[^xyz]
|
[xyz]

C12
[^xyz]
X
[wxyz]

C13
[^xyz]
X
[^abc]

C14
[0-9]
=
[0123456789]

C15
[a-z]
>
[b-y]

C16
[a-z]
=
a|[b-y]|z

C17
[^0-9]*
>
Hello, World!

C18
[^0-9]*
|
123

C19
[^abc]
<
.

C20
[^abc]*
X
.

C21
[^a]|a
=
.

C22
[^abcd]|[a-c]|d
=
.

C23
[^a]*
X
b[^c]*

C24
[^a]*
|
a[^c]*

D. Złożone wzorce z klasami postaci

D1
http://[^/][^/]*/.*
>
http://(www\.|)google\.com/.*

D2
http://[A-Za-z][A-Za-z]*\.wikipedia\.org/
X
(http://|)en\.wikipedia\.org/(|wiki(|/.*))

D3
[A-Za-z0-9._%+\-][A-Za-z0-9._%+\-]*@[A-Za-z0-9.\-][A-Za-z0-9.\-]*\.[A-Za-z][A-Za-z](|[A-Za-z]|[A-Za-z][A-Za-z])
X
[email protected]

D4
[A-Za-z0-9._%+\-][A-Za-z0-9._%+\-]*@[A-Za-z0-9.\-][A-Za-z0-9.\-]*\.[A-Za-z][A-Za-z](|[A-Za-z]|[A-Za-z][A-Za-z])
>
email@address\.com

D5
[A-Za-z0-9._%+\-][A-Za-z0-9._%+\-]*@[A-Za-z0-9.\-][A-Za-z0-9.\-]*\.[A-Za-z][A-Za-z](|[A-Za-z]|[A-Za-z][A-Za-z])
>
[A-Za-z0-9._%+\-][A-Za-z0-9._%+\-]*@gmail\.com

D6
JohnDoe@[A-Za-z0-9.\-][A-Za-z0-9.\-]*\.[A-Za-z][A-Za-z](|[A-Za-z]|[A-Za-z][A-Za-z])
<
[A-Za-z0-9._%+\-][A-Za-z0-9._%+\-]*@[A-Za-z0-9.\-][A-Za-z0-9.\-]*\.[A-Za-z][A-Za-z](|[A-Za-z]|[A-Za-z][A-Za-z])

D7
[A-Za-z0-9._%+\-][A-Za-z0-9._%+\-]*@gmail\.com
X
JohnDoe@[A-Za-z0-9.\-][A-Za-z0-9.\-]*\.[A-Za-z][A-Za-z](|[A-Za-z]|[A-Za-z][A-Za-z])

D8
[^, a-z][^,]*(|(, [^, ][^,]*)* and [^, ][^,]*)\.
>
One, two and three\.

D9
[^, a-z][^,]*(|(, [^, ][^,]*)* and [^, ][^,]*)\.
|
one, two and three\.

D10
[^, a-z][^,]*(|(, [^, ][^,]*)* and [^, ][^,]*)\.
|
One, two\.

D11
[^, a-z][^,]*(|(, [^, ][^,]*)* and [^, ][^,]*)\.
<
(.*(,|))*

D12
[A-Z][^,]*(|(, [a-z][^,]*)* & [a-z][^,]*)\.
<
[^, a-z][^,]*(|(, [^, ][^,]*)* (and|et|[&+]) [^, ][^,]*)\.

Program testowy

Do porównania wzorców wyrażeń regularnych można użyć następującego fragmentu kodu:

<style>#main {display: none;}#main[loaded] {display: inline;}.pattern_container {position: relative;}.pattern_underlay, .pattern {font: 12pt courier, monospace;overflow: hidden;white-space: pre;padding: 7px;box-sizing: border-box;}.pattern_underlay {background-color: #dddddd;color: #707070;border-radius: 4px;box-shadow: 0.5px 0.5px 2.5px #aaaaaa;}.pattern_underlay[error] {background-color: #ffccbb;}.pattern {position: absolute;left: 0px;top: 0px;background: none;border: none;width: 100%;height: 100%;resize: none;white-space: normal;}#ordering {min-width: 28pt;text-align: center;font-size: 16pt;}#status {padding: 5px;background-color: #fffdce;box-shadow: 1.5px 1.5px 3.5px #aaaaaa;font-size: 10pt;white-space: pre;display: none;}#status[error] {display: inline;background-color: #ffe8df;}#status[loading] {display: inline;}.inline_code {background-color: #dddddd;font: 12pt courier, monospace;padding: 2px;}.placeholder {visibility: hidden;}.error_text {background-color: #fffcb7};</style><span id="main"><table><tr><td><div class="pattern_container"><div class="pattern_underlay" id="pattern1_underlay"></div><textarea class="pattern" id="pattern1" oninput="compare()">Hello, .*!</textarea></div></td><td id="ordering"></td><td><div class="pattern_container"><div class="pattern_underlay" id="pattern2_underlay"></div><textarea class="pattern" id="pattern2" oninput="compare()">.*, .*!</textarea></div></td></tr></table><br></span><span id="status" loading>Loading...</span><script type='text/javascript'>var Module = {setStatus: function (status) {document.getElementById("status").innerHTML = status;if (status == "") {compare();document.getElementById("status").removeAttribute("loading");document.getElementById("main").setAttribute("loaded", 1);}}};function underlay_chars(str) {if (/^\n*$/.exec(str))return str.split("\n").map(function () { return '<span class="placeholder"> \n</span>'; });if (str.indexOf("\n") >= 0)str = str.replace(/\s*$/gm, function (m) { return m.replace(/[^\n]/g, "\0"); });return (str + "\n").split("").map(function (c) {if (c == "\0") return "·";else return '<span class="placeholder">' + c + '</span>';});}function underlay_str(str) {return underlay_chars(str).join("");}function str_to_array32(str) {a = [];for (c of str) {n = c.charCodeAt(0);a.push(n & 0xff, (n >> 8) & 0xff, (n >> 16) & 0xff, n >> 24);}a.push(0, 0, 0, 0);return a;}function compare() {try {for (e of ["pattern1_underlay", "pattern2_underlay", "status"])document.getElementById(e).removeAttribute("error");for (e of ["pattern1", "pattern2"])document.getElementById(e + "_underlay").innerHTML = underlay_str(document.getElementById(e).value);c = Module.ccall("regex_compare", "number", ["array", "array"], [str_to_array32(document.getElementById("pattern1").value),str_to_array32(document.getElementById("pattern2").value)]);if (c >= 0)document.getElementById("ordering").innerHTML = "∥≬<>="[c];else {i = Module.ccall("regex_error_index", "number", [], []);l = Module.ccall("regex_error_length", "number", [], []);e = document.getElementById("pattern" + -c + "_underlay");t = underlay_chars(document.getElementById("pattern" + -c).value);e.setAttribute("error", 1);e.innerHTML =t.slice(0, i).join("") +'<span class="error_text">' + t.slice(i, i + l).join("") + "</span>" +t.slice(i + l).join("");e.setAttribute("error", 1);throw "Pattern error: " + Module.ccall("regex_error", "string", [], []).replace(/`(.*?)'/g, '<span class="inline_code">$1</span>');}} catch (e) {document.getElementById("ordering").innerHTML = "??";document.getElementById("status").innerHTML = e;document.getElementById("status").setAttribute("error", 1);}}</script><script async type="text/javascript" src="https://gist.githack.com/anonymous/91f27d6746566c7b4e4c/raw/c563bf84a01c3a1c6e5f021369a3e730a2e74a1a/rpo.js"></script>

Python 2, 522 bajty * .92 = 480,24 537,28

Edytuj 2 : -60 bajtów

Edycja : Dodano wyjaśnienie.

Zdefiniowana jest funkcja f, która przyjmuje dwa ciągi wzór jako argumentów i zwrotów '<', '=', '>', '|', lub 'X'. Przetwarzanie wszystkich przypadków testowych zajmuje mniej niż minutę.

Kod składa się z następujących, ale z \r, \n \ti \0znaków ucieczki szesnastkowych (ale nie ) zastąpionych ich rzeczywistymi wartościami bajtów.

#encoding=Latin
exec"""x\xda]RMo\xdb0\x0c\xbd\xe7Wx\'K\x96\x92\xc5mOR\xb8\xdf1@%|\x98%X\x80a\x19\x96\x02\x03n\xf2\xdfG:i;\xec$\x92z|\x8f_\x1b\x84%m~\xca\xbe\x1c\x0e\xbd\x0fU\x10Agi\x0e\x87\xea\n\x1f\xf9n{=\xea\0\x93\x08\xd2\xaez\xd0\x99\xcc,m\x07g\xbb\x80s\x9b\x08\xee\x8cRo"\xf3\x8bHy!-\x95\xd7\xa9\x8aS\xb50O5\xc3&\xb68\x0b\xe7\xb1\x19t\x92\x8a\x1d\xaf]\xc2f\x94\x92\x111T\xf3\xf1j\xba\x1b\x081r\xa2\x97\xea\xa5\x11\x03\x9bI\xca\xe6\xed\xe7\xab\xbd\xde`\xb6\x8b"\xd1\xc5\xf7\xd7?^l\xa7\xaeKK\xd7i\x91\x92\x8b\xaaE\x16\x8e\x9c\x12#3\x86\xe0"\xc6\xc9\x15\xfd\x86\xae\\\xde\xcc^\xa7\x94;,\xea\x94t\x08\x84\xa6J\x82\xee%\xb1\xe8\xacW\xb9\xb3\x14f\xd9\x84\xeb\x89\xe1\x8b\xd5\xa3r\xeb\xbf\x81D\rS\xf5\x8b/\xd7e\xaao\xf0\xeb\xf2\xbbv\xdd\xf1\x15\x1f\x93\xe4Aq\xff\x19\xc6\x98\x8b\xa8E\xad\xb2\xaae-m\x843\xc5\xd7!\x8e\xbe\xca.\x1a4\x01\xe8E;@-\xe4\xad9\xd5\xa7\x10\xa7\x9eg\xcea\x10\x83\x0e\xd2\r\x973\xb2o\xb8\xd7\x06\xc2\x0f\xa8\xdf\xdfk\x1b\x15\xb4v\x84H\xc9\xad]\xc1\x83C;\x03m\xc3\x16p\x1f\xe3\x1d\xbf\xa4\xe2\xbe\x8d\x1eX)\x1e\t\x9dv\xf3\xa9\xcd\xe8xGU\x9e\x0b\t\x97\xd6\x0c\x8c\xf2\nxa\xa9\x19u\xaf\xf2iN3\r\xd1\xae\x0f\xe3\x13\x0c@h\xb5W\xb0\xaad3\xef\t\x91s]R=~\xc3^Lv\xc7\x16\x15\xf4\xfb\xa7\x88ze_~B\x06\x80\x99\x03\x86\x7f\x0bY\x06U\xd2.\xeaV\x95\x87$\xd1\xce\xff\x8b\xbf\x9a\x99\xe0\x03u\xa1 =o0<n\xd0\xef]s`b\xb7\x98\x89\xael\xd2\x85\xceO:>\x80j\xfa\xdeb\x95\x95k\x91N\xbe\xfc'5\xac\xe7\xe8\x15""".decode('zip')

Powyższa instrukcja powoduje wykonanie następującego kodu:

z=frozenset
def f(f,s):
 u={s};d,l,f=n(f);w,h,s=n(s);_=0;r=[[z(f[0]),z(s[0])]]
 for e,o in r:
  p=z(zip([e]*h,o)+zip(e,[o]*l))
  if p-u:_|=((l in e)+2*(h in o))*4/3;u|=p;r+=[[reduce(z.__or__,(oo[i+1]for i in ii if ff[i]in[t,4][t<4:]),z())for ii,oo,ff in(e,f,d),(o,s,w)]for t in z([d[i]for i in e]+[w[i]for i in o])]
 return'|=><X'[_-3]
def n(s):
 s=list('('+s+')');i=0
 while s[i:]:f=s[i];h='()|*.'.find(f);s[i]=(h,f)[h<0];s[i:i+1]*=f!='\\';i+=1;l=i;h=1;w=e=[];p=[0];t=[{l}]
 while i:
  d=[i];i-=1;o=[i];f=s[i];t=[{i}]+t
  if f<1:h-=1;e+=zip(o*l,d+s.pop());w.pop()
  if f==1:h+=1;w=w+o;s+=[[]];e+=[o+d]
  if f==2:s[-1]+=d;e+=[(i,w[-1])]
  if h==p[-1]:e+=[t[-1:]+o,[i,1+t.pop()]];p.pop()
  if f==3:p+=[h];t+=o
 for f,o in e:
  for n in t:n|=(n,t[o])[f in n]
 return s+[1],l,t

Jeśli druga próbka kodu jest przechowywana w ciągu s, wyrażenie podobne może wytworzyć coś podobnego do pierwszego '#encoding=Latin\nexec"""%s"""'%__import__('zlib').compress(s). Konieczne może być naprawienie niektórych znaków, takich jak puste bajty lub odwrotne ukośniki. Rozpakowany kod ma prawie 1000 800 bajtów, więc być może jest bardziej zaciemniony niż w golfa ... ale przynajmniej udało mi się trochę zakodować kodowanie: od Latin1do Latin.

Wyjaśnienie

Program działa przy użyciu indeksów ciągu jako prostego sposobu śledzenia stanów parsowania ciągu. nFunkcja opiera tabele przejścia. Najpierw analizuje ciąg i znajduje wszystkie wystąpienia dwóch rodzajów przejść. Po pierwsze, są przejścia, które nie wymagają dodania kolejnej litery do łańcucha. Na przykład przeskakując od a *do początku wyrażenia ilościowego. Po drugie, istnieją przejścia dodawania znaku, które po prostu przesuwają się o jeden indeks do przodu. Następnie obliczane jest przechodnie przechodzenie przejść bez znaków, które zastępują miejsca docelowe przejścia 1-znakowego. Zwraca więc mapowanie indeksu i znaku na zestaw indeksów.

Główna funkcja wykonuje BFS względem możliwych ciągów wejściowych. Śledzi zestaw wszystkich możliwych indeksów dla dowolnego rozważanego fragmentu ciągu. Interesuje nas znalezienie stanów, które są albo akceptowane przez oba wyrażenia regularne, albo przez jedno, a nie drugie. Aby pokazać, że wyrażenie regularne jest akceptowane, konieczne jest tylko znalezienie jednej możliwej ścieżki przejścia do końca wzorca. Ale aby pokazać, że ktoś został odrzucony, konieczne jest przeanalizowanie wszystkich możliwych ścieżek. Dlatego, aby ustalić, czy zestawy możliwych stanów dla wzoru A i wzoru B są już objęte tymi, które zostały przeanalizowane wcześniej, pary jednego stanu w jednym wyrażeniu regularnym i zbiór wszystkich możliwych stanów w drugim są rejestrowane. Jeśli nie ma żadnych nowych, możesz wrócić. Oczywiście byłoby to również możliwe, a mniej znaków,

Haskell, 560 553 618

może uzyskać niektóre z bonusów w przyszłości.

nie jest jeszcze w pełni golfa.

import Data.List
c%j|'\\':h:s<-j=[s|c==h]|(a,b):_<-[(a,b)|x<-[0..length j],(a,'|':b)<-[splitAt x j],snd(k b)==[]]=c%a++c%b|'(':s<-j,(a,_:'*':b)<-k s=map(++j)(c%a)++c%b|'(':s<-j,(a,_:b)<-k s=map(++b)(c%a)|h:'*':s<-j=map(++j)(c%[h])++c%s
c%"."=[""|c>'\0']
c%s@[_]=c%('\\':s)
c%(a:b)=map(++b)(c%[a])
c%s=[""|c>'\0']
a&b=nub[(x,nub$b>>=(c%))|c<-[' '..'~'],x<-c%a]
g e(k@(a,l):r)|j<-a&l\\e=g(k:e)(j++r)
g e[]=e
a#b=or[all(null.('\0'%))m|(x,m)<-g[][(a,[b])],""<-'\0'%x]
a!b|a#b,b#a='x'|a#b='>'|b#a='<'|0<1='='
k"("=("","(")
k(c:s)|'('<-c,(x,y)<-k$tail b=('(':a++')':x,y)|')'<-c=("",')':s)|0<1=(c:a,b)where(a,b)=k s
k j=(j,j)

faliste wyjaśnienie algorytmu:

reg!reg' zwraca wymagany znak, jeden z „= <> x”.

a#bma wartość prawda, jeśli nie apasuje do każdego pasującego łańcucha b.

c%regjest listą wyrażeń regularnych, które regpasują do c:sjednego z wyrażeń regularnych w dopasowaniach wyjściowych s. i jest zasadniczo częściowo dopasowane do wyrażenia regularnego. z wyjątkiem jeśli cjest '\0'. następnie zmusza, regaby nie otrzymywać więcej danych wejściowych, zwracając, []jeśli regtrzeba uzyskać więcej danych wejściowych w celu dopasowania, i w [""]przeciwnym razie.

#działa, generując skończoną listę wszystkich możliwych „stanów wyrażeń regularnych”, w których dwa wyrażenia regularne będą znajdować się po dowolnym ciągu znaków. następnie, aby sprawdzić, czy a<bsprawdzamy pogodę, istnieje „stan wyrażenia regularnego”, w którym ajest w pełni dopasowany, ale bnie jest w pełni dopasowany.