Czy ten język jest zdefiniowany przy użyciu podwójnych liczb pierwszych regularnych?

Pozwolić

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

Czy regularny?$L$

To pytanie wyglądało podejrzanie na pierwszy rzut oka i zdałem sobie sprawę, że jest związane z hipotezą o podwójnej liczbie pierwszych . Mój problem polega na tym, że domysł nie został jeszcze rozwiązany, więc nie jestem pewien, jak mogę kontynuować ustalanie, że język jest prawidłowy.

Jeśli hipoteza podwójnej liczby pierwotnej jest prawdziwa, to , która jest regularna. Jeśli hipoteza o podwójnej liczbie pierwszych nie jest prawdziwa, wówczas istnieje wiele skończonych liczb pierwszych; w rzeczywistości istnieje największa para podwójnych liczb pierwszych { p , p + 2 } . W tym przypadku L = { a n | n < p + 1 } , język skończony. W obu przypadkach otrzymujesz zwykły język, więc myślę, że bezpiecznie jest to wywnioskować$L = a^{*}$$\{p, p + 2\}$$L = \{a^{n} | n < p + 1\}$ jest językiem zwykłym ... po prostu nie będziemy wiedzieć, który to jest, dopóki nie rozwiąże się hipoteza podwójnej liczby pierwotnej.$L$

Tak, ten język jest regularny. Hipoteza podwójnej liczby pierwszej nie musi być rozwiązana, aby to zobaczyć:

Załóżmy, że hipoteza podwójnej liczby pierwszej jest prawdziwa, to znaczy dla dowolnego możemy znaleźć liczbę pierwszą p ≥ n taką, że p + 2 jest liczbą pierwszą. W szczególności L = { a n | n ∈ N } , ponieważ warunek jest zawsze spełniony. Ten ostatni jest język eksprymowanej przez a * i stąd regularne.$n$$p \geq n$$p+2$$L = \{ a^n | n \in N \}$$a^*$

$N$$p$$p+2$$n > N$$p$$p+2$$L = \{ a^n | n \leq N \}$

$L$

W obu przypadkach jest to normalne.

• $L=\{a^n:n\geq 0\}=L(a^*)$
• $L$