„Gęste” wyrażenia regularne generują

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 ) ∗ | = $R$$|R|$$|0 \cup 1| = |(0 \cup 1)^*| = 2$

Domysł: Jeśli i L ( R ) zawiera każdy ciąg długości | R | lub mniej, to L ( R ) = Σ ∗ .$|R| > 1$$L(R)$$|R|$$L(R) = \Sigma^*$

Oznacza to, że jeśli jest „gęsty” do R długość jest, wówczas R faktycznie wytwarza wszystko.$L(R)$$R$$R$

Niektóre rzeczy, które mogą być istotne:

1. 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 .$R$$R = (0 \cup 1)^* \cup S$$S$
2. W pewnym momencie musi być gwiazda Kleene w Jeśli tak nie jest, będzie brakować ciągu o rozmiarze mniejszym niż | R | .$R$$|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)?

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).$|\mathrm{alph}(R)|$$R$$\epsilon$$\emptyset$$\emptyset$$\epsilon$$|\mathrm{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 \geq 3$$O(n)$$\{0,1\}$$\Omega(2^n n)$