wartości null (regularne Ekspresja)

Question

W „pochodne regularnych wyrażenia” Brzozowskiego oraz w innym miejscu, δ funkcji (R) powrocie X jeśli R pustych i ∅ inaczej, obejmuje klauzule takie jak:

δ(R1 + R2) = δ(R1) + δ(R2) 
δ(R1 · R2) = δ(R1) ∧ δ(R2) 

Oczywiście, jeżeli zarówno R1 i R2 są pustych wówczas (· R1 R2) jest pustych, a jeśli R1 albo lub R2 jest pustych, a następnie (R1 + R2) jest pustych. Nie jest dla mnie jasne, co mają znaczyć powyższe klauzule. Moja pierwsza myśl, mapowanie (+), (·) lub operacji logicznych do regularnych zestawów jest bezsensowne, ponieważ w przypadku bazowego

δ(a) = ∅ (for all a ∈ Σ) 
δ(λ) = λ 
δ(∅) = ∅ 

i λ nie jest zbiorem (ani to zestaw typ zwracany δ, który jest wyrażeniem regularnym). Co więcej, to mapowanie nie jest wskazane i istnieje osobny zapis dla niego. Rozumiem, że mam do czynienia z zerowaniem, ale zagubiłem się w definicji sumy, produktu i operacji Boole'a w definicji δ: w jaki sposób λ lub ∅ wróciły z δ (R1) ∧ δ (R2), na przykład , w definicji off δ (R1 · R2)?

Answer 1

Wydaje mi się, że przyłapią Cię notacyjne wolności, które autor robi. Typ powrotu δ (R) jest z pewnością zbiorem, a raczej językiem. Jeśli spojrzeć na definicję:

widać, że istnieje sprzeczność w rodzaju powrotu, formalnie λ jest pierwiastkiem, ale ∅ jest pusty język ... Co powinien powiedzieć to:

fakt, że autor używa X zarówno dla pusty ciąg, jak również języka zawierającego tylko pusty łańcuch jest dodatkowo świadczy jego definicji operatora Kleene zodiaku:

Najwyraźniej ostatnia część powinna być , jeśli chcemy być pedantyczni.

Biorąc pod uwagę, że typ zwrotu δ (R) jest zbiorem, a raczej językiem, równania, które podajesz, mają doskonały sens i wyrażają dokładnie to, co opisałeś.

Answer 2

Myślę, że miałeś rację, odpowiednio odwzorowując + i ^ na boolowskie or i and. Wygląda na to, dwiema liniami ty cytowanych kontrakt z naprzemiennie (suma) i konkatenacji (produktu):

δ(R1 + R2) = δ(R1) + δ(R2) 

naprzemiennej z R1 i R2 jest pustych jeśli R1 jest pustych, R2 jest pustych, lub oba R1 i R2 są zerowalne.

δ(R1 · R2) = δ(R1) ∧ δ(R2) 

konkatenacji z R1 i R2 pustych tylko wtedy, gdy oba R1 i R2 są pustych.

Zapoznaj się z here, aby zapoznać się z implementacją tych reguł przez firmę Haskell.

Answer 3

(Nie mogę zajrzeć do artykułu Brzozowskiego, aby lepiej zrozumieć, co tam jest napisane), ale mogę zasugerować 2 sposoby na interpretację tego zapisu (poza dostawaniem się do notacji, widzę, że nie ma pytanie: zamierzony sens tej definicji jest dobrze zrozumiany):

1) Po lewej stronie definicji mamy tylko "syntaktyczne" wzorce dla wyrażeń regularnych. Po prawej produkujemy zestawy; pamiętaj, że wyrażenie regularne jest sposobem na oznaczenie języka (zestawu), a więc ten sposób zapisania definicji staje się zrozumiały: po prawej, po prostu używamy niektórych (prostych) wyrażeń regularnych jako krótkiego sposobu odnoszenia się do zestawy. Tj. ∅ oznacza pusty język (pusty zbiór) i λ (jeśli wyrażenie interpretowane jako jako wyrażenie regularne) oznacza język zawierający tylko puste słowo (zestaw z tym elementem).

Operacje są po prostu operacjami na zestawach: prawdopodobnie połączeniach i przecięciach.

Jeśli notacja jest interpretowana w ten sposób, nie ma sprzeczności z używaną notacją, aby oprzeć się podstawowym przypadkom: ponownie "a" jest wyrażeniem regularnym, które oznacza tam język z napisem "a".

2) Najpierw budujemy regularne wyrażenia, ale autor rozszerzył operacje, które budują wyrażenia regularne za pomocą klina, który ma semantykę przecięcia się języków.