„Gęste” wyrażenia regularne generują

25

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 ) | = 2R|R||01|=|(01)|=2

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

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

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 .RR=(01)SS
  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)?

Lucas Cook
źródło
czy i ∅ są liczone jako czy jako ? εsymbolsoperations
Ran G.
@Ran Liczyłem je jako symbole.
Lucas Cook

Odpowiedzi:

34

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.n3O(n){0,1}Ω(2nn)

Yuval Filmus
źródło
Bardzo fajny wynik, a także dość zaskakujący :)
Alex ten Brink
Jak wygląda to wyrażenie regularne?
sick
@svick: sprytnie łączy sztuczkę, która z gwiazdami Kleene, aby uchwycić wspólne podciągi, sądząc po szybkim przejrzeniu dowodu. Wyrażenie jest dość potworne :)(a+b)(c+d)=ac+bc+ad+bd
Alex ten Brink
@Yuval Bardzo fajne. Dzięki za referencje!
Lucas Cook
2
@YuvalFilmus Wygląda na to, że gazeta jest już dostępna online.
Anton Trunov