Pochodna Brzozowskiego

Pochodna Brzozowskiego (na czerwonym tle) ciągu słownikowego ustawionego względem ciągu „con”

W informatyce teoretycznej $Displaystyle$ w szczególności w teorii języka formalnego , pochodna Brzozowskiego zbioru ciągów i łańcucha u $^ {-1} S$ \ $}$ gdzie jest zbiorem wszystkich ciągów, które można uzyskać z ciągu w $ciągu$ $odcięcie$ przedrostka , jak pokazano na rysunku Formalnie: ${\ Displaystyle u ^ {- 1} S = \ {v \ w \ Sigma ^ {*} \ mid uv \ w S \}}$ .

Został wprowadzony pod różnymi nazwami od późnych lat pięćdziesiątych. Dziś nosi imię informatyka Janusza Brzozowskiego , który zbadał jego właściwości i podał algorytm obliczania pochodnej uogólnionego wyrażenia regularnego .

Definicja

Chociaż pierwotnie badano ją pod kątem wyrażeń regularnych, definicja dotyczy dowolnych języków formalnych. $}$ $\ in \ Sigma ^ {*}$ dowolny język formalny $nad$ alfabetem i dowolnym ciągiem , pochodną u ∈ $u$ w odniesieniu do jest zdefiniowany jako: ${\ displaystyle u}$

{\ Displaystyle u ^ {- 1} S = \ {v \ w \ Sigma ^ {*} \ średni uv \ w S \}}

Pochodna Brzozowskiego jest szczególnym przypadkiem lewego ilorazu przez zbiór singletonowy zawierający tylko ${\ displaystyle u}$ : ${\ Displaystyle \ u ^ {- 1} S = \ {u \} \;\backslash \;S}$ .

Równoważnie dla wszystkich ${\ Displaystyle u, v \ in \ Sigma ^ {*}}$ :

{\ Displaystyle v \ w u ^ {- 1} S \; \ Strzałka w prawo \; uv \ w S.}

Z definicji dla wszystkich ${\ Displaystyle u, v \ in \ Sigma ^ {*}}$ :

{\ Displaystyle (uv) ^ {- 1} S = v ^ {- 1} (u ^ {- 1} S)}

${\ Displaystyle w \ w (uv) ^ {- 1} S \ Strzałka w prawo uvw \ w S \ Strzałka w lewo vw \ w u ^ {- 1} S \ Strzałka w lewo w \ w v ^ {- 1}(u^{-1}S)}$ . dla $mamy$ S

Pochodna w odniesieniu do dowolnego ciągu sprowadza się do kolejnych $wszystkich$ ,

{\ Displaystyle {\ rozpocząć {wyrównane} (ua) ^ {- 1} S & = a ^ {- 1} (u ^{-1}S)\\\varepsilon ^{-1}S&=S\koniec{wyrównane}}}

Język jest nazywany nullable wtedy i tylko $gdy$ zawiera pusty ciąg $varepsilon}$ . Każdy język jest jednoznacznie określony przez możliwość zerowania jego pochodnych: ${\ displaystyle S}$

{\ Displaystyle w \ w S \ \ strzałka w lewo \ \ varepsilon \ w w ^ {- 1} S}

Język można postrzegać jako (potencjalnie nieskończone) drzewo z etykietą logiczną (patrz także drzewo (teoria mnogości) i automat drzewa nieskończonego ). Każdy $true,$ łańcuch oznacza węzeł w drzewie, z etykietą w ∈ $displaystyle w \ in S}$ false w przeciwnym razie $W$ tej interpretacji pochodna względem symbolu $od$ poddrzewi otrzymanemu przez podążanie za krawędzią . Rozkład drzewa na korzeń i poddrzewa $następującej$ równości, która obowiązuje dla każdego języka $}}$ $subseteq \ Sigma ^ {$ :

{\ Displaystyle S = (\ {\ varepsilon \} \ cap S) \ kubek \ bigcup _ {a \ in \ Sigma} a (a ^ {-1} S).}

Pochodne uogólnionych wyrażeń regularnych

Kiedy język jest określony przez wyrażenie regularne, koncepcja pochodnych prowadzi do algorytmu decydującego, czy dane słowo należy do wyrażenia regularnego.

uwagę skończony alfabet A symboli, uogólnione wyrażenie regularne R oznacza możliwie nieskończony zbiór ciągów o skończonej długości nad alfabetem A , zwanym językiem R , oznaczonym jako L ( R ).

Uogólnione wyrażenie regularne może być jednym z następujących (gdzie a jest symbolem alfabetu A , a R i S są uogólnionymi wyrażeniami regularnymi):

„∅” oznacza zbiór pusty: L (∅) = {},
„ε” oznacza zestaw singleton zawierający pusty ciąg: L (ε) = {ε},
„ a ” oznacza zestaw singleton zawierający ciąg pojedynczych symboli a : L ( a ) = { a },
" R ∨ S " oznacza sumę R i S : L ( R ∨ S ) = L ( R ) ∪ L ( S ),
„ R ∧ S ” oznacza przecięcie R i S : L ( R ∧ S ) = L ( R ) ∩ L ( S ),
„¬ R ” oznacza dopełnienie R (w odniesieniu do A *, zbioru wszystkich ciągów nad A ): L (¬ R ) = A * \ L ( R ),
„ RS ” oznacza konkatenację R i S : L ( RS ) = L ( R ) · L ( S ),
„ R *” oznacza zamknięcie Kleene’a R : L ( R *) = L ( R )*.

W zwykłym wyrażeniu regularnym ani ∧, ani ¬ nie są dozwolone.

Obliczenie

Dla dowolnego uogólnionego wyrażenia regularnego R i dowolnego łańcucha u , pochodna u ⁻¹ R jest ponownie uogólnionym wyrażeniem regularnym (oznaczającym język u ⁻¹ L ( R )). Można to obliczyć rekurencyjnie w następujący sposób.

( ua ) ⁻¹ R	= za ⁻¹ ( u ⁻¹ R )	dla symbolu a i łańcucha u
ε ^-1 R	= R

Stosując poprzednie dwie reguły, pochodna względem dowolnego ciągu znaków jest wyjaśniona przez pochodną względem ciągu jednosymbolowego a . To ostatnie można obliczyć w następujący sposób:

za- ¹ za	= ε
a - ^1b	= ∅	dla każdego symbolu b ≠ a
za ⁻¹ ε	= ∅
za ⁻¹ ∅	= ∅
a ⁻¹ ( R *)	= ( za ⁻¹ R ) R *
a ^-1 ( RS )	= ( za ^-1 R ) S ∨ ν ( R ) za ^-1 S
za ⁻¹ ( R ∧ S )	= ( za ⁻¹ R ) ∧ ( za ⁻¹ S )
za ⁻¹ ( R ∨ S )	= ( za ⁻¹ R ) ∨ ( za ⁻¹ S )
a ⁻¹ (¬ R )	= ¬( za ⁻¹ R )

Tutaj $ν(R)$ jest funkcją pomocniczą dającą uogólnione wyrażenie regularne, którego wynikiem jest pusty łańcuch ε, jeśli język R zawiera ε , a w przeciwnym razie daje ∅. Funkcję tę można obliczyć według następujących reguł:

ν( a )	= ∅	dla dowolnego symbolu a
ν( ε )	= ε
ν(∅)	= ∅
ν( R *)	= ε
ν( RS )	= ν( R ) ∧ ν ( S )
ν( R ∧ S )	= ν( R ) ∧ ν ( S )
ν( R ∨ S )	= ν( R ) ∨ ν ( S )
ν(¬ R )	= ε	jeśli ν( R ) = ∅
ν(¬ R )	= ∅	jeśli ν( R ) = ε

Nieruchomości

Łańcuch u jest członkiem zbioru ciągów oznaczonego uogólnionym wyrażeniem regularnym R wtedy i tylko wtedy, gdy ε należy do zbioru ciągów określonego przez pochodną u ⁻¹ R .

Biorąc pod uwagę wszystkie pochodne ustalonego uogólnionego wyrażenia regularnego R daje tylko skończenie wiele różnych języków. Jeśli ich liczbę oznaczymy przez d _R , wszystkie te języki można otrzymać jako pochodne R względem łańcuchów o długości mniejszej niż d _R . Co więcej, istnieje kompletny deterministyczny automat skończony ze stanami d _R , który rozpoznaje język regularny podany przez R , zgodnie z twierdzeniem Myhilla-Nerode'a .

Pochodne języków bezkontekstowych

Pochodne są również efektywnie obliczalne dla rekurencyjnie zdefiniowanych równań z operatorami wyrażeń regularnych, które są równoważne gramatyce bezkontekstowej . Ta wiedza została wykorzystana do wyprowadzenia analizowania dla języków bezkontekstowych . Implementacja takich algorytmów wykazała złożoność w czasie sześciennym , odpowiadającą złożoności parsera Earleya w ogólnych gramatykach bezkontekstowych.

Zobacz też

Iloraz języka formalnego