złożoność półjęzyka

Dla dowolnego języka ponad zdefiniuj Słowami, składa się ze wszystkich dla których istnieje o równej długości, tak że .Σ * l 1 / 2 = { x ∈ Σ * : x y ∈ L , Y ∈ Σ | x | } . L 1 / 2 x Y x Y ∈ $L$$\Sigma^*$

Ćwiczenie w książce Sipsera ma na celu wykazanie, że jest regularne, gdy jest. Widziałem dwa odrębne rozwiązania, i oba pociągają za sobą gwałtowny wzrost stanów.$L_{1/2}$$L$

Pytanie: czy ktokolwiek może skonstruować rodzinę języków taki sposób, że automat kanoniczny dla jest znacznie (powiedzmy, wykładniczo) większy niż dla ? Moje dotychczasowe starania zwiększają tylko rozmiar państwa o !( l n ) 1 / 2 L + $\{L_n\}$$(L_n)_{1/2}$$L$$+1$

Zobacz artykuł Mike'a Domaratzkiego, Złożoność państwowa proporcjonalnych przeprowadzek

http://dl.acm.org/citation.cfm?id=782471

http://www.cs.umanitoba.ca/~mdomarat/pubs/sc_jalc.ps