"Dichte" reguläre Ausdrücke erzeugen ?

Hier ist eine Vermutung für reguläre Ausdrücke:

Für den regulären Ausdruck sei die LängeGeben Sie die Anzahl der darin enthaltenen Symbole an und ignorieren Sie dabei Klammern und Operatoren. ZB| R | | 0 ∪ 1 | = | ( 0 ∪ 1 ) * | = $R$$|R|$$|0 \cup 1| = |(0 \cup 1)^*| = 2$

Vermutung: Wenn und enthält jede Zeichenkette der Längeoder weniger, dann ist .l ( R ) | R | L ( R ) = Σ $|R| > 1$$L(R)$$|R|$$L(R) = \Sigma^*$

Das heißt, wenn ist ‚dicht‘ bis ‚s Länge, dann eigentlich alles erzeugt.R $L(R)$$R$$R$

Einige Dinge, die relevant sein können:

1. Es wird nur ein kleiner Teil von benötigt, um alle Zeichenfolgen zu generieren. Zum Beispiel in Binär-, wird für jede Arbeit .R = ( 0 ∪ 1 ) * ∪ S $R$$R = (0 \cup 1)^* \cup S$$S$
2. Irgendwann muss es in einen Kleene-Stern geben . Ist dies nicht der Fall, wird eine Zeichenfolge mit einer Größe von weniger als übersehen .| R $R$$|R|$

Es wäre schön, einen Beweis oder ein Gegenbeispiel zu sehen. Gibt es einen Fall, in dem es offensichtlich falsch ist, dass ich etwas verpasst habe? Hat jemand dies (oder ähnliches) schon einmal gesehen?

Ihre Vermutung wird von Keith Ellul, Bryan Krawetz, Jeffrey Shallit und Ming-wei Wang in ihrem Artikel "Reguläre Ausdrücke: Neue Ergebnisse und offene Probleme" widerlegt. Während das Papier nicht online verfügbar ist, ist ein Vortrag .

In der Arbeit definieren sie das MaßDies ist die Anzahl der Symbole in , wobei oder nicht . Allerdings kann von jedem Ausdruck eliminiert werden nicht die leere Sprache zu erzeugen, und der Ausdruck kann „gereinigt“ werden , so dass die Anzahl der es enthält höchstens(Lemma auf Seite 10 des Vortrags).R ϵ ∅ ∅ ϵ | a l p h ( R ) $|\mathrm{alph}(R)|$$R$$\epsilon$$\emptyset$$\emptyset$$\epsilon$$|\mathrm{alph}(R)|$

Auf Seite 51 konstruieren sie für jedes einen regulären Ausdruck der Größe über der alle Zeichenfolgen der Größe höchstens generiert, jedoch nicht generiert alle Saiten. Beachten Sie, dass "Größe" hier sowohl in Ihrem als auch in ihrem Sinne ist, da wir die Big-O-Notation verwenden. Sie werfen auch eine offene Frage auf, um die beste Abhängigkeit zwischen den beiden Parametern zu finden.O ( n ) { 0 , 1 } Ω ( 2 n n $n \geq 3$$O(n)$$\{0,1\}$$\Omega(2^n n)$