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

24

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 LLΣ

L1/2={xΣ:xyL,yΣ|x|}.
L1/2xyxyL

Ć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. lL1/2L

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 + 1{Ln}(Ln)1/2L+1

Aryeh
źródło
1
nie wspominasz o częściowo oczywistym problemie minimalizacji DFA. nie widziałem dowodów, ale może nie biorą ich pod uwagę. a minimalizacja DFA po uruchomieniu na sprawdzonej konstrukcji może znacznie uprościć DFA ...?
vzn
5
Konstrukcje w dowodach są abstrakcyjne i wcale nie jest jasne, jak je zminimalizować za pomocą standardowych technik.
Aryeh
Czy możesz opublikować najlepszą rodzinę języków, którą znalazłeś?
Diego de Estrada
nie jest to wymagane, aby odpowiedzieć na twoje Q, ale może być pomocne naszkicowanie konstrukcji. inną opcją jest empiryczne zaatakowanie problemu losowymi modułami FSM
od

Odpowiedzi: