thumb|100px|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 Brzozowskiego zbioru 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. 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 symboliBrzozowski (1964), s. 481, wymagał by kombinacji bitów, dla dowolnego 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łBrzozowski (1964), s. 482, definicja 3.2.:
= = = = = = = 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óbBrzozowski (1964), s. 483, twierdzenie 3.1.:
= = 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 Brzozowski (1964), s. 483, twierdzenie 3.2.. 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 regularneBrzozowski (1964), s. 483, twierdzenie 4.1..
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ą Brzozowski (1964), s. 483, twierdzenie 4.2..
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ż Brzozowski (1964), s. 484, twierdzenie 4.3.. 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
Kategoria:Języki formalne