Czy język jednoargumentowy jest regularny, jeśli wykładnikiem jest funkcja liniowa?

13

Wykonując bieżące zadanie dla moich kursów języków formalnych i automatów, w pewnym sensie utknąłem na ćwiczeniach obejmujących języki jednoargumentowe (mam nadzieję, że to właściwy termin), tj. Języki oparte na jednej literze. Nie chcę jednak pytać o konkretne ćwiczenia, ale raczej o bardziej ogólną hipotezę, którą wymyśliłem:

Niech i . Moja hipoteza to: $\Sigma=\{a\}$ $L=\{a^{f(n)}\in\Sigma^*:n\in\mathbb N_0\}$

L is regular \Leftrightarrow \exists x, y \in N_{0} : f (n) = x \cdot n + y

$L\text{ is regular}\Leftrightarrow \exists x,y\in\mathbb N_0:f(n)=x\cdot n+y$

Czy to pytanie było wcześniej traktowane naukowo? Czy to „oczywiście” prawda / fałsz?

Dla mnie oczywiście kierunek „ ” jest prawdziwy, ponieważ można po prostu zbudować DFA ze stanami , który przechodzi przez stany po przeczytaniu stanów i przyjmuje, że jest pod numerem stanu . $\Leftarrow$ $x+y$ $x$ $y$ $y$

formal-languages regular-languages

— SEJPM
źródło

Dobra robota, dzięki czemu ta obserwacja nie jest niczym, czego oczekuję od przeciętnych studentów!

— Raphael

Zgoda. To bardzo miła obserwacja.

— Rick Decker

Nie jest to oczywiste z tytułu, ale mieliśmy już to pytanie, aż do małego lematu równoważności: Jakie są możliwe zestawy długości słów w zwykłym języku?

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

9

Liniowy jest bliski, ale szukany termin techniczny jest półliniowy: to znaczy skończony związek zbiorów liniowych.

Połowa tego dowodu jest następstwem twierdzenia Parikha , które mówi, że każdy bezkontekstowy język ma półliniową mapę Parikha (to znaczy zbiór wektorów zawierających wystąpienia każdej litery w alfabecie).

W przypadku języka jednoargumentowego parikhową mapą języka jest sam język (tzn. Każde słowo jest jednoznacznie identyfikowane przez liczbę liter), więc każdy zwykły język jest półliniowy.

Druga połowa dowodu pokazuje, że możesz zbudować zwykły język zawierający każdy jednoargumentalny zestaw półliniowy. To wymaga trochę pracy, ale nie jest zbyt trudne, jeśli używasz wyrażeń regularnych:

$a^k$ rozpoznaje język $\{ k \}$
$(a^k)^*$ rozpoznaje $\{xk \mid x \in \mathbb{N}_0 \}$
$R_1 R_2$ rozpoznaje jeśli rozpoznaje i rozpoznaje , gdzie Oto dodanie elementu mądry $S_1 + S_2$ $R_1$ $S_1$ $R_2$ $S_2$ $+$
$R_1 | R_2$ rozpoznaje jeśli rozpoznaje i rozpoznaje , gdzietutaj jest związek wyrażeń regularnych. $S_1 \cup S_2$ $R_1$ $S_1$ $R_2$ $S_2$ $|$

— jmite
źródło

6

Masz prawie rację. Musisz wziąć pod uwagę fakt, że możesz mieć kilka funkcji liniowych, takich jak lub możesz mieć skończone języki, takie jak (W obu przypadkach łączymy zwykłe języki, więc wszystko działa tak, jak powinno).

L = {a^{k} ∣ k = 3 n + 1 or k = 7 n + 4}

$L=\{a^k\mid k=3n+1\text{ or }k=7n+4\}$

L = {a^{k} ∣ k = 4 n + 2 or k = 13}

$L=\{a^k\mid k=4n+2\text{ or }k=13\}$

— Rick Decker
źródło