Jakie są możliwe zestawy długości słów w zwykłym języku?

Biorąc pod uwagę język , zdefiniuj zestaw długości jako zestaw długości słów w : $L$$L$$L$

Które zestawy liczb całkowitych mogą być zestawem długości zwykłego języka?

Po pierwsze, obserwacja, która nie jest kluczowa, ale wygodna: zbiór zestawów liczb całkowitych, które są dla jakiegoś regularnego języka na niepustym alfabecie , nie zależy od wyboru alfabetu. Aby to zobaczyć, rozważ automat skończony rozpoznający ; długości słów w to długości ścieżek na automacie widziane jako nieoznaczony wykres od stanu początkowego do dowolnego stanu akceptacji. W szczególności możesz ponownie przypisać każdą strzałkę do i uzyskać zwykły język o tej samej długości ustawionej na alfabecie . I odwrotnie, jeśli$\mathscr{S}$$LS(L)$$L$$\mathscr{A}$$L$$L$$a$$\{a\}$$L$ jest zwykłym językiem nad jednoczęściowym alfabetem, można go trywialnie wstrzyknąć do większego alfabetu, a wynik jest nadal zwykłym językiem.

Dlatego szukamy możliwych zestawów długości słów nad alfabetem singleton. W alfabecie singletonowym językiem jest ustawiona długość zapisana w unary: . Takie języki nazywane są językami jednoargumentowymi.$\mathrm{LS}(L) = \{n\in\mathbb{N} \mid a^n \in L\}$

Niech będzie język regularny, i rozważyć deterministyczny automat skończony (DFA), który rozpoznaje . Zbiór długości słów jest zbiorem długości ścieżek w DFA widzianym jako ukierunkowany wykres, który rozpoczyna się w stanie początkowym i kończy w jednym ze stanów akceptacji. DFA na jednoelementowym alfabecie jest dość oswojone (NFA byłyby bardziej szalone): jest to lista skończona lub lista okrężna. Jeśli lista jest skończona, ponumeruj stany od do zgodnie z kolejnością na liście; jeśli jest okrągły, numeruj stany od do po nagłówku listy, a od do wzdłuż pętli.$L$$L$$L$$0$$h$$0$$h$$h$$h+r$

Niech $F$ będzie zbiorem wskaźników stanów akceptacji do $h$ , a $G$ będzie zbiorem wskaźników stanów akceptacji od $h$ do $h+r$ . Następnie

I odwrotnie, niech $h$ i $r$ będą dwiema liczbami całkowitymi, a $F$ i $G$ będą dwoma skończonymi zestawami liczb całkowitych, tak że $\forall x \in F, x \le h$ i $\forall x \in G, h \le x \le h+r$ . Następnie zbiór $L_{F,G,r} = \{ a^{k\,r+x} \mid x\in G, k\in\mathbb{N} \}$jest językiem zwykłym: jest to język rozpoznawany przez DFA opisany powyżej. Wyrażenie regularne, które opisuje ten język jest F | G ( r ) * .$a^F \mid a^{G} (a^r)^*$

Podsumowując w języku angielskim, zestawy długości zwykłych języków są zestawami liczb całkowitych, które są okresowe¹ powyżej pewnej wartości .

¹ _{Aby utrzymać się na ustalonym pojęciu , okresowe oznacza funkcję charakterystyczną zestawu (która jest funkcją $\mathbb{N}\to\{\mathtt{false},\mathtt{true}\}$ którą podnosimy do funkcji $\mathbb{Z}\to\{\mathtt{false},\mathtt{true}\}$ ) ma charakter okresowy. Okresowe powyżej określonej wartości oznacza, że ​​funkcja ograniczona do $[h,+\infty[$ może zostać przedłużony do funkcji okresowej.}

Dowolny podzbiór skończony może być zestawem długości zwykłego języka L , ponieważ możesz wziąć jednoargumentowy alfabet { 0 } i zdefiniować L jako { 0 ℓ 1 , … , 0 ℓ n } (obejmuje to pusty język i { ε } ).$\{\ell_1,\ldots,\ell_n\}\subset\mathbb{N}$$L$$\{0\}$$L$$\{0^{\ell_1},\ldots,0^{\ell_n}\}$$\{\varepsilon\}$

Teraz dla zestawów nieskończonych. Dam krótką analizę, choć ostateczna odpowiedź może nie być wystarczająco jednoznaczna. Nie będę się rozwijał, chyba że mnie o to poprosisz, ponieważ uważam, że jest to intuicyjne i ponieważ nie mam teraz dużo czasu.

Niech będą wyrażeniami regularnymi generującymi odpowiednio języki L 1 i L 2 . Łatwo to zauważyć$r_1,r_2$$L_1$$L_2$

• .$\mathsf{LS}(L(r_1+r_2))=\mathsf{LS}(L_1\cup L_2)=\mathsf{LS}(L_1)\cup\mathsf{LS}(L_2)$
• . Jest to oznaczone L S ( L 1 ) + L S ( $\mathsf{LS}(L(r_1r_2))=\mathsf{LS}(L_1L_2)=\{\ell_1+\ell_2:\ell_1\in\mathsf{LS}(L_1),\ell_2\in\mathsf{LS}(L_2)\}$ .$\mathsf{LS}(L_1)+\mathsf{LS}(L_2)$
• $$\mathsf{LS}(L(r_1^*))=\{0\}\cup\bigcup_{n\geq 1}\Big\{\sum_{i=1}^n\ell_i:(\ell_1,\ldots,\ell_n)\in\big(\mathsf{LS}(L_1)\big)^n\Big\}.$$

W ten sposób, możliwe zestawy liczb, które mogą mieć długość-zestaw regularnych języku są te, które są skończone podzbiory lub które mogą być budowane poprzez skończonych podzbiorów S 1 , S 2 z N i przy użyciu poprzedniej formuły skończonej kilka razy.$\mathbb{N}$$S_1,S_2$$\mathbb{N}$

W tym przypadku korzystamy z tego, że języki regularne są budowane z definicji, stosując reguły konstruowania wyrażeń regularnych skończoną liczbę razy. Zauważ, że możemy zacząć od dowolnego skończonego podzbioru , chociaż w wyrażeniach regularnych zaczynamy od słów o długości 0 i 1 tylko jako podstawowy przypadek. Jest to łatwo uzasadnione faktem, że wszystkie (skończone) słowa są (skończonymi) konkatenacjami symboli alfabetu.$\mathbb{N}$

Zgodnie z lematem pompowania dla języków zwykłych istnieje takie, że ciąg x o długości co najmniej równej n można zapisać w następującej formie: x = u v w Jeżeli spełnione są następujące trzy warunki: | u v | < n | v | > 0 u v k w ∈ $n$$x$$n$

To daje nam jeden test na zestawy: zestaw nie może być zestawem długości języka regularnego, chyba że wszystkie jego elementy mogą być wyrażone jako dowolny dowolny zestaw liczb całkowitych nie większych niż stała , plus pewna wielokrotność nieokreślonej wartości m (długość z v ) plus pewna dowolna skończona wartość.$n$$m$$v$

Innymi słowy, wygląda na to, że możliwymi zestawami długości języków dla zwykłych języków jest zamknięcie w odniesieniu do unii zestawów (jak omówione w EDIT i EDIT2, dzięki komentatorom) zestawów opisanych w następujący sposób: Dla ustalonych a , b ∈ N i wszystkich skończonych zbiorów S , przez pompujący lemat dla zwykłych języków (dzięki Gillesowi za wskazanie głupiego błędu w mojej oryginalnej wersji, w którym definiowałem zestaw N ).

EDYCJA: Trochę więcej dyskusji. Z pewnością wszystkie skończone zestawy liczb całkowitych są zestawami długości. Również połączenie dwóch zestawów długości musi być również zestawem długości, podobnie jak dopełnienie dowolnego zestawu długości (stąd przecięcie, stąd różnica). Powodem tego jest to, że zwykłe języki są zamknięte w ramach tych operacji. Dlatego powyższa odpowiedź jest (prawdopodobnie) niepełna; w rzeczywistości jakakolwiek kombinacja takich zbiorów jest również zbiorem długości jakiegoś regularnego języka (zauważ, że zrezygnowałem z wymogu przecięcia, uzupełnienia, różnicy itp., ponieważ są one objęte tym, że zwykłe języki są zamknięte pod tymi właściwościami, ponieważ omówione w EDIT3; myślę, że w rzeczywistości konieczny jest tylko związek, nawet jeśli inni mają rację, co może nie mieć miejsca).

$bn$$a$

EDYCJA 3: W świetle komentarza Janomy zapomnijmy o właściwościach zamykających zestawów długości języka, które omawiam podczas pierwszego EDYCJI. Ponieważ zwykłe języki mają te właściwości zamykania, a ponieważ każdy zwykły język ma DFA, wynika z tego, że pompujący lemat dla zwykłych języków dotyczy wszystkich związków, skrzyżowań, uzupełnień i różnic zwykłych języków, i zostawimy to na tym ; nie muszę nawet brać pod uwagę żadnego z nich, z wyjątkiem związku, który nadal uważam za konieczny do poprawienia mojego oryginału (zmodyfikowanego dzięki wkładowi Gillesa). Tak więc moja ostateczna odpowiedź brzmi: to, co mówię w oryginalnej wersji, a także zamknięcie zestawów długości języka w odniesieniu do zbioru unii.