Pochodna Brzozowskiego

W teorii języków formalnych w informatyce pochodna Brzozowskiego ${\displaystyle u^{-1}S}$ zbioru ciągów znaków ${\displaystyle S}$ względem ciągu znaków ${\displaystyle u}$ jest zdefiniowana jako zbiór ciągów znaków otrzymanych z elementów zbioru ${\displaystyle S}$ poprzez usunięcie prefiksu ${\displaystyle u}$ (jeśli istnieje), formalnie ${\displaystyle u^{-1}S=\{v\in \Sigma ^{*}:uv\in S\},}$ jak na rysunku^[1]. Nazwa pochodnych Brzozowskiego pochodzi od nazwiska informatyka Janusza Brzozowskiego, który badał ich właściwości i opracował algorytm liczący pochodne uogólnionych wyrażeń regularnych.

Mając skończony alfabet ${\displaystyle A}$ symboli^[2] uogólnione wyrażenie regularne oznacza potencjalnie nieskończony zbiór ciągów znaków skończonej długości złożonych z symboli z alfabetu ${\displaystyle A.}$ Zbiór ten może mieć postać:

• ${\displaystyle \varnothing }$ (pusty zbiór ciągów znaków)
• ${\displaystyle \varepsilon }$ (jednoelementowy zbiór zawierający tylko pusty ciąg znaków)
• symbol ${\displaystyle a}$ ze zbioru ${\displaystyle A}$ (co oznacza jednoelementowy zbiór zawierający ciąg znaków składający się z jednego symbolu ${\displaystyle a}$)
• ${\displaystyle R\lor S}$ (unia zbiorów ${\displaystyle R}$ i ${\displaystyle S,}$ gdzie ${\displaystyle R}$ i ${\displaystyle S}$ są uogólnionymi wyrażeniami regularnymi)
• ${\displaystyle R\land S}$ (część wspólna zbiorów ${\displaystyle R}$ i ${\displaystyle S}$)
• ${\displaystyle \neg R}$ (dopełnienie zbioru ${\displaystyle R}$ względem wszystkich ciągów znaków złożonych z symboli alfabetu ${\displaystyle A}$)
• ${\displaystyle RS}$ (zbiór wszystkich możliwych złączeń ciągów znaków ze zbiorów ${\displaystyle R}$ i ${\displaystyle S}$)
• ${\displaystyle R^{*}}$ (zbiór ${\displaystyle n}$-krotnych powtórzeń ciągów znaków ze zbioru ${\displaystyle R}$ i ${\displaystyle S,}$ dla dowolnego ${\displaystyle n\geqslant 0,}$ włącznie z pustym ciągiem znaków).

W zwykłym wyrażeniu regularnym ${\displaystyle \land }$ ani ${\displaystyle \neg }$ nie jest dozwolone.

Zbiór ciągów znaków oznaczony przez uogólnione wyrażenie regularne ${\displaystyle R}$ nazywany jest jego językiem i oznacza się go jako ${\displaystyle L(R).}$

Jako funkcja pomocnicza ${\displaystyle \delta (R)}$ zwraca pusty łańcuch ${\displaystyle \varepsilon }$ jeśli język odpowiadający ${\displaystyle R}$ zawiera ${\displaystyle \varepsilon ,}$ w przeciwnym razie ${\displaystyle \delta (R)}$ zwraca ${\displaystyle \varnothing .}$ Funkcja ta może być obliczona za pomocą następujących reguł^[3]:

${\displaystyle \delta (\varepsilon )}$	= ${\displaystyle \varepsilon }$
${\displaystyle \delta (\varnothing )}$	= ${\displaystyle \varnothing }$
${\displaystyle \delta (R^{*})}$	= ${\displaystyle \varepsilon }$
${\displaystyle \delta (RS)}$	= ${\displaystyle \delta (R)\land \delta (S)}$
${\displaystyle \delta (R\land S)}$	= ${\displaystyle \delta (R)\land \delta (S)}$
${\displaystyle \delta (R\lor S)}$	= ${\displaystyle \delta (R)\lor \delta (S)}$
${\displaystyle \delta (\neg R)}$	= ${\displaystyle \varepsilon }$	jeśli ${\displaystyle \delta (R)=\varnothing }$
${\displaystyle \delta (\neg R)}$	= ${\displaystyle \varnothing }$	jeśli ${\displaystyle \delta (R)=\varepsilon }$

W oparciu o to, pochodna uogólnionego wyrażenia regularnego względem jednoelementowego ciągu znaków ${\displaystyle a}$ może być obliczona w następujący sposób^[4]:

${\displaystyle a^{-1}a}$	= ${\displaystyle \varepsilon }$
${\displaystyle a^{-1}b}$	= ${\displaystyle \varnothing }$	dla każdego symbolu ${\displaystyle b\neq a}$
${\displaystyle a^{-1}\varepsilon }$	= ${\displaystyle \varnothing }$
${\displaystyle a^{-1}\varnothing }$	= ${\displaystyle \varnothing }$
${\displaystyle a^{-1}(R^{*})}$	= ${\displaystyle a^{-1}RR^{*}}$
${\displaystyle a^{-1}(RS)}$	= ${\displaystyle (a^{-1}R)S\lor \delta (R)a^{-1}S}$
${\displaystyle a^{-1}(R\land S)}$	= ${\displaystyle (a^{-1}R)\land (a^{-1}S)}$
${\displaystyle a^{-1}(R\lor S)}$	= ${\displaystyle (a^{-1}R)\lor (a^{-1}S)}$
${\displaystyle a^{-1}(\neg R)}$	= ${\displaystyle \neg (a^{-1}R)}$

Dla symbolu ${\displaystyle a,}$ dowolnego łańcucha ${\displaystyle u}$ i uogólnionego wyrażenia regularnego ${\displaystyle R}$ pochodna ${\displaystyle (ua)^{-1}R}$ może być obliczona rekursywnie jako ${\displaystyle a^{-1}(u^{-1}R);}$ i ${\displaystyle \varepsilon ^{-1}R}$ jest równe ${\displaystyle R}$^[5]. w ten sposób dla danego uogólnionego wyrażenia regularnego ${\displaystyle R}$ i łańcucha ${\displaystyle u,}$ pochodna ${\displaystyle u^{-1}R}$ może być obliczona jako kolejne uogólnione wyrażenie regularne^[6].

Łańcuch ${\displaystyle u}$ należy do zbioru określonego przez uogólnione wyrażenie regularne ${\displaystyle R}$ wtedy i tylko wtedy gdy ${\displaystyle \varepsilon }$ należy do zbioru ciągów znaków określonego przez pochodną ${\displaystyle u^{-1}R}$^[7].

Rozważając wszystkie pochodne uogólnionego wyrażenia regularnego ${\displaystyle R}$ stałej długości otrzymuje się skończenie wiele różnych języków. Jeśli ich liczba określona jest przez ${\displaystyle d_{R},}$ wszystkie te języki można otrzymać jako pochodne ${\displaystyle R}$ względem ciągu znaków długości mniejszej niż ${\displaystyle d_{R}}$^[8]. Ponadto istnieje kompletny deterministyczny automat skończony o liczbie stanów ${\displaystyle d_{R}}$ rozpoznający język regularny określony przez ${\displaystyle R,}$ zgodnie z twierdzeniem Myhilla-Nerode’a.