Этот язык определен с использованием одинарных простых чисел?

Позволять

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

Является регулярным?$L$

На первый взгляд этот вопрос выглядел подозрительно, и я понял, что он связан с гипотезой о двойном простом числе . Моя проблема в том, что эта гипотеза еще не решена, поэтому я не уверен, как мне решить, что язык является регулярным.

Если гипотеза двойного простого числа верна, то , что регулярно. Если гипотеза двойного простого числа неверна, то существует конечное число простых двойников; действительно, существует наибольшая пара двойниковых простых чисел { p , p + 2 } . В этом случае L = { a n | n < p + 1 } , конечный язык. В любом случае вы получаете обычный язык, поэтому я думаю, что можно с уверенностью заключить, что L - это обычный язык ... мы просто не будем знать, какой это язык, пока не будет решена гипотеза двойного простого числа.$L = a^{*}$$\{p, p + 2\}$$L = \{a^{n} | n < p + 1\}$$L$

Да, этот язык регулярный. Гипотеза двойного простого не должна быть решена, чтобы увидеть это:

Предположим, что гипотеза двойного простого числа верна, то есть для любого мы можем найти простое число p ≥ n такое, что p + 2 простое. Тогда, в частности, L = { a n | n ∈ N } , так как условие всегда выполняется. Этот последний язык выражается через ∗ и, следовательно, регулярно.$n$$p \geq n$$p+2$$L = \{ a^n | n \in N \}$$a^*$

Предположим, что гипотеза двойного простого числа неверна. Тогда существует некоторое такое, что существует некоторое простое p такое, что p + 2 простое, и для любого n > N не существует p такого, что p + 2 простое. В этом случае L = { a n | n ≤ N } , который является конечным языком и, следовательно, регулярным.$N$$p$$p+2$$n > N$$p$$p+2$$L = \{ a^n | n \leq N \}$

По различию случая мы заключаем, что регулярно.$L$

Это регулярно в любом случае.

• Если бесконечно много простых чисел-близнецов, то .$L=\{a^n:n\geq 0\}=L(a^*)$
• Если конечных простых чисел конечное множество, то конечно, поэтому регулярно.$L$