Pochodna Brzozowskiego (na czerwonym tle) łańcucha znaków ze słownika względem łańcucha „con”
W teorii języków formalnych w informatyce pochodna Brzozowskiegozbioru ciągów znaków względem ciągu znaków jest zdefiniowana jako zbiór ciągów znaków otrzymanych z elementów zbioru poprzez usunięcie prefiksu (jeśli istnieje), formalnie 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.
Pochodna wyrażenia regularnego
Mając skończony alfabet 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 Zbiór ten może mieć postać:
(pusty zbiór ciągów znaków)
(jednoelementowy zbiór zawierający tylko pusty ciąg znaków)
symbol ze zbioru (co oznacza jednoelementowy zbiór zawierający ciąg znaków składający się z jednego symbolu )
(unia zbiorów i gdzie i są uogólnionymi wyrażeniami regularnymi)
(część wspólna zbiorów i )
(dopełnienie zbioru względem wszystkich ciągów znaków złożonych z symboli alfabetu )
(zbiór wszystkich możliwych złączeń ciągów znaków ze zbiorów i )
(zbiór -krotnych powtórzeń ciągów znaków ze zbioru i dla dowolnego włącznie z pustym ciągiem znaków).
W zwykłym wyrażeniu regularnym ani nie jest dozwolone.
Zbiór ciągów znaków oznaczony przez uogólnione wyrażenie regularne nazywany jest jego językiem i oznacza się go jako
Jako funkcja pomocnicza zwraca pusty łańcuch jeśli język odpowiadający zawiera w przeciwnym razie zwraca Funkcja ta może być obliczona za pomocą następujących reguł[3]:
=
=
=
=
=
=
=
jeśli
=
jeśli
W oparciu o to, pochodna uogólnionego wyrażenia regularnego względem jednoelementowego ciągu znaków może być obliczona w następujący sposób[4]:
=
=
dla każdego symbolu
=
=
=
=
=
=
=
Dla symbolu dowolnego łańcucha i uogólnionego wyrażenia regularnego pochodna może być obliczona rekursywnie jako i jest równe [5]. w ten sposób dla danego uogólnionego wyrażenia regularnego i łańcucha pochodna może być obliczona jako kolejne uogólnione wyrażenie regularne[6].
Właściwości
Łańcuch należy do zbioru określonego przez uogólnione wyrażenie regularne wtedy i tylko wtedy gdy należy do zbioru ciągów znaków określonego przez pochodną [7].
Rozważając wszystkie pochodne uogólnionego wyrażenia regularnego stałej długości otrzymuje się skończenie wiele różnych języków. Jeśli ich liczba określona jest przez wszystkie te języki można otrzymać jako pochodne względem ciągu znaków długości mniejszej niż [8]. Ponadto istnieje kompletny deterministyczny automat skończony o liczbie stanów rozpoznający język regularny określony przez zgodnie z twierdzeniem Myhilla-Nerode’a.
Przypisy
↑Janusz A. Brzozowski. Derivatives of Regular Expressions. „JACM”. 11, s. 481–494, 1964. DOI: 10.1145/321239.321249.
↑Brzozowski (1964), s. 481, wymagał by kombinacji bitów, dla dowolnego