Pochodna Brzozowskiego

W teorii języków formalnych w informatyce pochodna Brzozowskiego $u^{-1}S$ zbioru ciągów znaków $S$ względem ciągu znaków $u$ jest zdefiniowana jako zbiór ciągów znaków otrzymanych z elementów zbioru $S$ poprzez usunięcie prefiksu $u$ (jeśli istnieje), formalnie $u^{-1}S=\{v\in \Sigma ^{*}:uv\in S\},$ jak na rysunku. 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.

Pochodna Brzozowskiego (na czerwonym tle) łańcucha znaków ze słownika względem łańcucha „con”

Pochodna wyrażenia regularnego

Mając skończony alfabet $A$ symboli 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 $A.$ Zbiór ten może mieć postać:

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

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

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

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

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

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

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

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

Właściwości

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

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