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$

L S (L) = {| u | ∣ u \in L}

$\mathrm{LS}(L) = \{|u| \mid u \in L \}$

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

formal-languages computability regular-languages finite-automata Gilles „SO- przestań być zły”
źródło

Odpowiedzi:

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$

automaty w kształcie listy

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

L. S. (L.) = fa \cup {k r + x ∣ x \in sol, k \in N.}

$\mathrm{LS}(L) = F \cup \{ k \, r + x \mid x \in G, k\in\mathbb{N} \}$

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 . $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.}

Gilles „SO- przestań być zły”
źródło

Twoja obserwacja na temat nieistotności alfabetu sugeruje, że można zastosować twierdzenie Parikha. W szczególności pokazujesz, że LS (L) = LS (L ') gdzie w L' wszystkie litery są zwinięte do pojedynczego alfabetu. Ale LS (L ') jest odwzorowaniem Parikha języka L, który jest znany jako półliniowy dla każdego zwykłego języka.

Suresh

Niezłe podejście! 1) Myślę, że pierwszy akapit można zastąpić stwierdzeniem, że zwykłe języki są zamknięte przed homomorfizmami łańcuchowymi. 2) Dla jasności powinieneś rozważyć podanie drugiej części

jako

, modulo off-by-one-error. 3) Co to jest „okresowy” zestaw liczb całkowitych?

L S (L)

$\mathrm{LS(L)}$

{h + k r + (x - h) ∣ \dots}

$\{h + kr + (x - h) \mid \dots \}$

Raphael

@Suresh, Raphael (1): Wolę przedstawić dowód w elementarny sposób, ani homomorfizmy, ani odwzorowania Parikha nie zostały wymienione w mojej klasie CS 102.

Gilles „SO- przestań być zły”

@Raphael (2) Gdy zaczynasz w indeksowaniu

nie ma znaczenia, mógłbym usunąć warunek

, ponieważ

może pochłonąć tyle małych elementów, ile chcemy. (3) Zestaw, który jest okresowy powyżej określonej wartości, jest zestawem, który można umieścić w wyświetlonej powyżej formie.

G

$G$

h \leq G

$h \le G$

F

$F$

Gilles „SO- przestań być zły”

Dowolny podzbiór skończony może być zestawem długości zwykłego języka , ponieważ możesz wziąć jednoargumentowy alfabet i zdefiniować jako (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 i . Ł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 $\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)$
$L S (L (r_{1}^{*})) = {0} \cup ⋃_{n \geq 1} {\sum_{i = 1}^{n} ℓ_{i} : (ℓ_{1}, \dots, ℓ_{n}) \in (L S (L_{1}))^{n}} .$ $\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 z 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}$

Janoma
źródło

Nie widzę żadnej ostatecznej odpowiedzi. (Czy miałeś zamiar dokończyć swoją odpowiedź później?) Miałem nadzieję na prosty opis możliwych zestawów i połączenie z automatami.

Gilles „SO- przestań być zły”

Ostateczna odpowiedź brzmi: „Zatem możliwe zestawy liczb całkowitych ...”. To jest rzeczywiście prosty opis, choć związany z wyrażeniami regularnymi, a nie automatami.

Janoma,

Jest prostszy opis, który nie wymaga przyjęcia punktu stałego. Może to pytanie nie jest tak podstawowe, jak myślałem!

Gilles „SO- przestań być zły”

Nie sądzę, że można uniknąć ostatniej reguły, ponieważ jest to operator gwiazd, który może wytwarzać nieskończone zestawy długości, tak jak produkuje nieskończone języki.

Janoma,

@Gilles Chcesz więc zamkniętej formy najmniejszego punktu stałego rozwiązania indukcyjnego, które zapewnia Janoma?

Raphael

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

x = u v w

$x = uvw$

| u v | < n

$|uv| < n$

| v | > 0

$|v| > 0$

u v^{k} w \in L.

$uv^{k}w \in L$

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 (długość z ) 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 i wszystkich skończonych zbiorów , 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 ).

{za + b n | n \in N.} \cup S.

$\{a + bn | n \in \mathbb{N}\} \cup S$

a, b \in N

$a, b \in \mathbb{N}$

S

$S$

N

$\mathbb{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.

Patrick87
źródło

{a + b n ∣ a, b, n \in N} \cup S

$\{a+bn \mid a,b,n\in\mathbb{N}\} \cup S$

N

$\mathbb{N}$

L = L (a^{*})

$L=L(a^*)$

Σ = {a, b}

$\Sigma=\{a,b\}$

L

$L$

N

$\mathbb{N}$

\bar{L}

$\overline{L}$

N^{+}

$\mathbb{N}^+$

@Gilles Ale zestaw wszystkich liczb naturalnych jest prawidłowym zestawem długości, prawda? Nie generuję wszystkich podzbiorów liczb naturalnych, prawda? Zgadzam się, że byłoby to problematyczne. Edycja: och, czekaj, widzę, co mówisz. Tak, masz rację. Naprawi się po powrocie do komputera.

Patrick87,

@Janoma Doskonały punkt, będę musiał rozważyć, jak to może zmienić zestaw rzeczy, które definiuję ...

Patrick87