Języki, których nie możemy (nie) okazują się wolne od kontekstu

Szukam języków, które „prawdopodobnie nie są wolne od kontekstu”, ale nie jesteśmy w stanie (nie) udowodnić tego przy użyciu znanych standardowych technik.

Czy jest ostatnia ankieta na ten temat lub otwarta sekcja problemowa z ostatniej konferencji?

Prawdopodobnie nie ma wielu języków, o których nie wiadomo, że są CF, więc jeśli znasz taki, możesz również opublikować go jako odpowiedź.

Przykłady, które znalazłem to:

• dobrze znany język prymitywnych słów (jest na nim całkiem ładna książka: Języki bezkontekstowe i pierwotne słowa )$Q = \{ w \mid w \neq u^i (|u| > 1) \}$
• reprezentacje Base-k współdomeny wielomianu (patrz pytanie „ Reprezentacje Base-k współdomeny wielomianu - czy jest ono pozbawione kontekstu? ” na cstheory, które być może zostały rozwiązane przez domotorp, patrz jego przedruk )

Uwaga : jak pokazuje Aryeh w swojej odpowiedzi, możesz zbudować całą klasę takich języków, jeśli „podłączysz” język do nieznanej hipotezy o (nie) skończoności lub (nie) pustce niektórych zbiorów (np. nie może być wyrażony jako suma dwóch liczb pierwszych ). Nie jestem do końca zainteresowany takimi przykładami.$L_{Goldbach} = \{ 1^{2n} \mid 2n$$\}$

Kolejnym dobrym jest uzupełnienie zestawu ciągłych podtekstów (zwanych także „czynnikami”) sekwencji Thue-Morse'a . Aby dać pewien kontekst, Jean Berstel udowodnił , że dopełnienie zbioru z prefiksów tego słowa Thue-Morse jest kontekst wolny (a właściwie coś więcej niż ogólny). Ale odpowiedni wynik dla słów podrzędnych jest nadal otwarty.$S$${\bf t} = 0110100110010110 \cdots$T$T$

Co powiesz na język podwójnych liczb pierwszych? Tj. Wszystkie pary liczb naturalnych (reprezentowane, powiedzmy, w jedności), takie, że są zarówno liczbą pierwszą, jak i ? Jeśli hipoteza podwójnych liczb pierwszych jest prawdziwa, wówczas nie jest pozbawiony kontekstu; w przeciwnym razie jest skończony.$L_{TP}$$(p,p')$$p,p'$$p'=p+2$$L_{TP}$

Edycja: Pozwólcie, że dam szybki szkic dowodu, że domysł podwójnych liczb pierwszych sugeruje, że nie jest pozbawiony kontekstu. Powiąż z dowolnym językiem jego sekwencją długości , gdzie liczba całkowita pojawia się w sekwencji iff, w jest słowo długość . Jest to konsekwencja lematu pompującego, że dla które są regularne lub CFL, sekwencja długości spełnia właściwość ograniczonych różnic: istnieje takie, że dla wszystkich$L_{TP}$$L$0 ≤ a 1 ≤ a 2 ≤ … ℓ ℓ L L $0\le a_1\le a_2\le\ldots$$\ell$$\ell$$L$$L$$R>0$$a_{n+1}-a_n\le R$$n$. Jest to łatwy i dobrze znany fakt w teorii liczb, że liczby pierwsze nie mają ograniczonych różnic. Wreszcie, wszelkie nieskończone podsekwencje sekwencji naruszające samą właściwość różnic granicznych muszą ją naruszać.