Oto przypuszczenie dotyczące wyrażeń regularnych:
Dla wyrażenia regularnego , niech długość | R | być liczbą w nim symboli, ignorując nawiasy i operatory. np | 0 ∪ 1 | = | ( 0 ∪ 1 ) ∗ | = 2
Domysł: Jeśli i L ( R ) zawiera każdy ciąg długości | R | lub mniej, to L ( R ) = Σ ∗ .
Oznacza to, że jeśli jest „gęsty” do R długość jest, wówczas R faktycznie wytwarza wszystko.
Niektóre rzeczy, które mogą być istotne:
- Do wygenerowania wszystkich łańcuchów potrzebna jest tylko niewielka część Na przykład w systemie binarnym, R = ( 0 ∪ 1 ) * ∪ S działa dla wszelkich S .
- W pewnym momencie musi być gwiazda Kleene w Jeśli tak nie jest, będzie brakować ciągu o rozmiarze mniejszym niż | R | .
Byłoby miło zobaczyć dowód lub kontrprzykład. Czy jest jakiś przypadek, w którym to oczywiste jest, że przegapiłem? Czy ktoś widział to wcześniej (lub coś podobnego)?
symbols
operations
Odpowiedzi:
Twoje przypuszczenia są obalone przez Keitha Ellula, Bryana Krawetza, Jeffreya Shallita i Ming-wei Wanga w ich artykule „Wyrażenia regularne: nowe wyniki i otwarte problemy”. Chociaż artykuł nie jest dostępny on-line, rozmowa trwa.
W artykule określają miarę , czyli liczba symboli w R , nie licząc ϵ ani ∅ . Jednak ∅ można wyeliminować z każdego wyrażenia, które nie generuje pustego języka, a wyrażenie można „wyczyścić”, tak aby liczba ϵ w nim zawarta wynosiła co najwyżej | a l p h ( R ) | (Lemat na stronie 10 wykładu).|alph(R)| R ϵ ∅ ∅ ϵ |alph(R)|
Na stronie 51 dla każdego konstruują wyrażenie regularne o wielkości O ( n ) powyżej { 0 , 1 }, które generuje wszystkie łańcuchy wielkości co najwyżej Ω ( 2 n n ) , ale nie generuje wszystkich łańcuchów. Zauważ, że „rozmiar” jest tutaj zarówno w twoim znaczeniu, jak i ich, ponieważ używamy notacji big-O. Stawiają też otwarte pytanie, aby znaleźć najlepszą zależność między tymi dwoma parametrami.n≥3 O(n) {0,1} Ω(2nn)
źródło