Czy { } nie jest kontekstowe?

30

Czy język { } jest bezkontekstowy?aibjck | ij,ik,jk

Uświadomiłem sobie, że spotkałem prawie wszystkie warianty tego pytania z różnymi warunkami dotyczącymi związku między i, j i k, ale nie tym.

Domyślam się, że nie jest pozbawiony kontekstu, ale czy masz dowód?

Cem Say
źródło
11
@ Sariel: Mam nadzieję, że nie jest to zadanie domowe, ponieważ nie wiem, jak to rozwiązać.
Tsuyoshi Ito
3
Wygląda to na problem z zadaniami domowymi, ponieważ niektóre inne warianty, o których wspominam, są wystarczająco łatwe, by stanowić zadania domowe. Ale ten wariant nie jest problemem domowym. Byłbym zadowolony, gdyby ktokolwiek mógł podać mi link do dowolnej strony kursu, na której ten problem został przypisany jako zadanie domowe.
Cem Powiedz
2
Czy możesz wyjaśnić, dlaczego standardowe techniki nie działają?
Warren Schudy,
3
@Tsuyoshi ... Tak. Masz rację. To trudniejsze niż się wydaje.
Sariel Har-Peled
3
Co ciekawe, ten język (i zastosowanie lematu Ogdena) można znaleźć w przykładzie 6.3 (s. 130) w klasycznej wersji Hopcroft i Ullmana „Wprowadzenie do teorii automatów, języków i obliczeń”.
Dominik D. Freydenberger

Odpowiedzi:

28

Lemat Ogdena powinien działać:

Dla danego wybierz i zaznacz wszystkie (i nic więcej).a i b p c k bpaibpckb

k b b i ki i są tak dobrane, że dla każdego wyboru ile „s faktycznie pompowana jest jedna pompowanie wykładnik takie, że liczba ” s jest równa i jeden, gdzie jest on równy .kbbik

To jest i mają być ze zbioru .k 1 n p { p - n + m n m N 0 }ik1np{pn+mnmN0}

Jestem całkiem pewien, ale zbyt leniwy, aby formalnie udowodnić, że ten zestaw jest nieskończony.

Frank Weinberg
źródło
5
Zakładając, że IN_0 oznacza zbiór liczb całkowitych nieujemnych, wspomniany zbiór jest nieskończony, ponieważ zawiera p + im dla i = 0, 1, 2,…, gdzie m jest najmniejszą wspólną wielokrotnością {1,…, p}.
Tsuyoshi Ito
11
Ci, którzy nie znali lematu Ogdena (jak ja), mogą uznać Wikipedię za pomocną.
Tsuyoshi Ito
2
@Tsuyoshi: Tak, masz rację. Wczoraj wieczorem nie widziałem tego prostego przedstawienia.
Frank Weinberg
1
Ta odpowiedź znajduje się na blogu społeczności .
Aaron Sterling
Podobny dowód przedstawiono w tej odpowiedzi na stronie cs.se.
Hsien-Chih Chang 張顯 之
-4

Jeśli relacja między trzema ograniczeniami to „LUB”, wówczas językiem jest CFL. Rozwiązanie wykorzystuje fakt, że świetlówki kompaktowe są zamknięte w ramach unii. Oczywiste są następujące CFL: , , (jeśli nie jest się przekonanym, można spojrzeć na jako konkatenację CFL i zwykły język. Na przykład jest połączony z .L1={aibjckij, k0}L2={aibjckik, j0}L3={aibjckjk, i0}LiL1{ c } {aibjij}{c}

Pożądanym językiem jest połączenie powyższego . To jest CFL.L=L1L2L3

R_G
źródło
5
To jest źle. Na przykład a zatem w twoim , ale . L a a b c c { a i b j c k | i j , i k , j k }aabccL1Laabcc{aibjck | ij,ik,jk}
Dave Clarke
4
Zakładasz, że »relacja między trzema ograniczeniami to„ LUB ”«, ale nie jest to zamierzone znaczenie. Wszystkie ograniczenia muszą zostać spełnione (por. Kontrprzykład Dave'a Clarke'a), a wtedy język nie jest pozbawiony kontekstu (por. Odpowiedź powyżej).
DaniCL