Ist eine unäre Sprache regulär, wenn ihr Exponent eine lineare Funktion ist?

Während ich die aktuelle Aufgabe für meinen formalen Sprach- und Automatenkurs erledigte, blieb ich bei Übungen mit unären Sprachen hängen (ich hoffe, das ist der richtige Begriff), dh Sprachen, die auf einem einzelnen Buchstaben aufbauen. Ich möchte jedoch nicht nach den spezifischen Übungen fragen, sondern nach einer viel allgemeineren Vermutung, die ich mir ausgedacht habe:

Lassen und L = { a f ( n ) ∈ Σ * : n ∈ N 0 } . Meine Vermutung ist: L  regulär ist ⇔ ∃ x , y ∈ N 0 : f ( n ) = x ⋅ n + $\Sigma=\{a\}$$L=\{a^{f(n)}\in\Sigma^*:n\in\mathbb N_0\}$

Hat diese Frage schon einmal eine wissenschaftliche Behandlung erfahren? Ist es "offensichtlich" wahr / falsch?

Für mich ist die " " -Richtung offensichtlich wahr, weil man einfach einen DFA mit x + y- Zuständen konstruieren kann , der nach dem Durchlesen durch die x- Zustände wechselt$\Leftarrow$$x+y$$x$ Zustände durchgelesen wurden, und akzeptiert, wenn er bei der Zustandsnummer y liegt .$y$$y$

Linear ist nah, aber der Fachbegriff, den Sie suchen, ist semilinear: dh eine endliche Vereinigung linearer Mengen.

Die Hälfte des Beweises dafür ist eine Folge von Satzes Parikh , der besagt, dass jede kontextfreie Sprache eine semilineare Parikh-Karte hat (dh die Menge von Vektoren, die die Vorkommen jedes Buchstabens im Alphabet enthält).

Für eine unäre Sprache ist die Parikh-Karte der Sprache die Sprache selbst (dh jedes Wort wird durch die Anzahl der Buchstaben eindeutig identifiziert), sodass jede unäre reguläre Sprache semilinear ist.

Die andere Hälfte des Beweises zeigt, dass Sie eine reguläre Sprache konstruieren können, die jede unäre semilineare Menge enthält. Dies erfordert ein wenig Arbeit, ist jedoch nicht allzu schwierig, wenn Sie reguläre Ausdrücke verwenden:

• erkennt die Sprache { k $a^k$$\{ k \}$
• erkennt { x k ∣ x ∈ N 0$(a^k)^*$$\{xk \mid x \in \mathbb{N}_0 \}$
• erkennt S 1 + S 2 , wenn R 1 erkennt S 1 und R 2 erkennt S 2 , wobei + hier ist elementweise Addition$R_1 R_2$$S_1 + S_2$$R_1$$S_1$$R_2$$S_2$$+$
• $R_1 | R_2$$S_1 \cup S_2$$R_1$$S_1$$R_2$$S_2$$|$

Du hast fast recht. Sie müssen die Tatsache berücksichtigen , dass Sie mehrere lineare Funktionen haben könnten, wie