Czy { } nie jest kontekstowe?

Czy język { } jest bezkontekstowy? $a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$

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?

automata-theory fl.formal-languages grammars

— Cem Say
źródło

@ Sariel: Mam nadzieję, że nie jest to zadanie domowe, ponieważ nie wiem, jak to rozwiązać.

— Tsuyoshi Ito

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

Czy możesz wyjaśnić, dlaczego standardowe techniki nie działają?

— Warren Schudy,

@Tsuyoshi ... Tak. Masz rację. To trudniejsze niż się wydaje.

— Sariel Har-Peled

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:

Lemat Ogdena powinien działać:

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

$i$ 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 . $k$ $b$ $b$ $i$ $k$

To jest i mają być ze zbioru . $i$ $k$ $\bigcap_{1 \leq n \leq p} \lbrace p-n + m*n \mid m \in \mathbb{N}_0\rbrace$

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

— Frank Weinberg
źródło

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

Ci, którzy nie znali lematu Ogdena (jak ja), mogą uznać Wikipedię za pomocną.

— Tsuyoshi Ito

@Tsuyoshi: Tak, masz rację. Wczoraj wieczorem nie widziałem tego prostego przedstawienia.

— Frank Weinberg

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 . $L_1=\{a^ib^jc^k \mid i\ne j,\ k\ge 0\}$ $L_2=\{a^ib^jc^k \mid i\ne k,\ j\ge 0\}$ $L_3=\{a^ib^jc^k \mid j\ne k,\ i\ge 0\}$ $L_i$ $L_1$ $\{a^ib^j\mid i\ne j \}$ $\{c\}^*$

Pożądanym językiem jest połączenie powyższego . To jest CFL. $L=L_1\cup L_2\cup L_3$

— R_G
źródło

To jest źle. Na przykład a zatem w twoim , ale .

a a b c c \in L_{1}

$aabcc\in L_1$

L

$L$

a a b c c \notin {a^{i} b^{j} c^{k} | i \neq j, i \neq k, j \neq k}

$aabcc\notin\lbrace a^ib^jc^k~|~i\neq j,i\neq k,j\neq k\rbrace$

— Dave Clarke

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