Ist diese Sprache mit zwei regulären Primzahlen definiert?

Lassen

$\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}.$

Ist regelmäßig?$L$

Diese Frage sah auf den ersten Blick verdächtig aus und ich habe festgestellt, dass sie mit der Twin-Prime-Vermutung zusammenhängt . Mein Problem ist, dass die Vermutung noch nicht geklärt ist und ich nicht sicher bin, wie ich mit der Entscheidung fortfahren kann, dass die Sprache regulär ist.

Wenn die Twin-Prime-Vermutung wahr ist, dann ist , was regulär ist. Wenn die Twin-Prime-Vermutung nicht zutrifft, gibt es endlich viele Twin-Primzahlen. in der Tat gibt es ein größtes Paar von Doppelprimzahlen { p , p + 2 } . In diesem Fall ist L = { a n | n < p + 1 } , eine endliche Sprache. In beiden Fällen erhalten Sie eine reguläre Sprache, und ich denke, es ist sicher zu folgern, dass L eine reguläre Sprache ist. Wir werden nur nicht wissen, welche es ist, bis die Twin-Prime-Vermutung gelöst ist.$L = a^{*}$$\{p, p + 2\}$$L = \{a^{n} | n < p + 1\}$$L$

Ja, diese Sprache ist normal. Die Twin-Prime-Vermutung muss nicht aufgelöst werden, um dies zu sehen:

Angenommen, die Twin-Prime-Vermutung ist wahr, das heißt, wir können für jedes eine Primzahl p ≥ n finden, so dass p + 2 eine Primzahl ist. Dann ist insbesondere L = { a n | n ∈ N } , da die Bedingung immer wahr ist. Diese letzte Sprache ist durch ein ∗ auszudrücken und daher regelmäßig.$n$$p \geq n$$p+2$$L = \{ a^n | n \in N \}$$a^*$

Angenommen, die Twin-Prime-Vermutung ist falsch. Dann existiert etwas so dass es eine Primzahl p gibt, so dass p + 2 eine Primzahl ist, und für jedes n > N existiert kein p, so dass p + 2 eine Primzahl ist. In diesem Fall ist L = { a n | n ≤ N } ist eine endliche Sprache und daher regelmäßig.$N$$p$$p+2$$n > N$$p$$p+2$$L = \{ a^n | n \leq N \}$

Aufgrund der Fallunterscheidung schließen wir, dass regulär ist.$L$

It is regular in either case.

• $L=\{a^n:n\geq 0\}=L(a^*)$.
• Wenn es endlich viele Doppelprimzahlen gibt, dann $L$ ist endlich, also regelmäßig.