Czy nieskończona jedność języków bezkontekstowych jest zawsze pozbawiona kontekstu?

Niech , , , będą nieskończoną sekwencją języków bezkontekstowych, z których każdy jest zdefiniowany wspólnym alfabetem . Niech będzie nieskończoną jednością , , , ; tj. . $L_1$ $L_2$ $L_3$ $\dots$ $Σ$ $L$ $L_1$ $L_2$ $L_3$ $\dots$ $L = L_1 \cup L_2 \cup L_3 \cup \dots$

Czy zawsze jest tak, że $L$ jest językiem bezkontekstowym?

formal-languages context-free closure-properties

— Gigili
źródło

Są tutaj dwa najczęściej niezależne pytania. Pierwszy jest bardzo elementarny, ale na drugi można nawet łatwo odpowiedzieć za pomocą Wikipedii. Sugeruję edycję, aby skupić się na pierwszym pytaniu.

— Raphael

@Raphael: Zrobiłem to sam przed twoją sugestią, ale potem pomyślałem, że niektóre części odpowiedzi mogą być bezużyteczne.

— Gigili,

@Raphael: Ta edycja unieważnia większość tego, co napisałem! Nie sądzę, że dobrym pomysłem jest przekształcanie takich pytań, gdy już są odpowiedzi.

— Aryabhata,

@Aryabhata: Czy można edytować swoją odpowiedź, proszę? Zredagowałem go, aby nie było tak łatwo, jak powiedział! Wyślę na ten temat meta pytanie.

— Gigili,

@Gigili: Mogę, ale mówiłem ogólnie. Wyobraź sobie przypadek, w którym ktoś przeprowadza badania i dokłada starań, aby napisać szczegółową odpowiedź. Teraz idź i zmień pytanie, które unieważnia większość tej odpowiedzi. W przypadku tego pytania może to nie mieć znaczenia, prawdopodobnie prawdopodobnie mogę po prostu usunąć swoją odpowiedź, ponieważ będziemy mieli dwie odpowiedzi mówiące to samo, a jedna z nich byłaby po prostu hałasem.

— Aryabhata,

Związek nieskończenie wielu języków bezkontekstowych może nie być pozbawiony kontekstu. W rzeczywistości sumą nieskończenie wiele języków może być niemal wszystko: niech będzie językiem, i zdefiniować dla każdego przycisk (skończone) język . Unia w stosunku do wszystkich tych języków jest . Skończone języki są regularne, ale może nawet nie być rozstrzygalny (a tym samym zdecydowanie nie kontekstowy). $L$ $l \in L$ $L_l = \{ l \}$ $L$ $L$

Właściwości zamykania języków bezkontekstowych można znaleźć na Wikipedii .

— Alex ten Brink
źródło

Dziękuję za Twoją odpowiedź. Więc odpowiedź brzmi „nie”? Czy możesz podać kontrprzykład?

— Gigili,

{a^{n} b^{n} c^{n} | n \geq 1}

$\{ a^n b^n c^n | n \geq 1 \}$

L_{1} = {a b c}, L_{2} = {a a b b c c}, L_{3} = {a a a b b b c c c}, \dots

$L_1 = \{ a b c \}, L_2 = \{ aa bb cc \}, L_3 = \{ aaa bbb ccc \}, \dots$

L_{i}

$L_i$

@Gigili Powinieneś być w stanie używać dowolnego języka bezkontekstowego jako licznika przy użyciu tego, co napisał Alex.

— Raphael

L = ⋃_{n \in N} {w \in L ∣ | w | \leq n}

$L = \bigcup_{n\in\mathbb{N}} \{w \in L \mid |w| \le n\}$

„W rzeczywistości związek nieskończenie wielu języków może dotyczyć wszystkiego ” (podkreślenie dodane) W rzeczywistości może to być wszystko, kropka, a nie „tylko”. Twój przykład to pokazuje. Cóż, zerowy zestaw / język może być problemem, ale puste związki są w porządku. Może to być najdziwniejszy, w większości nieprzenikalny zestaw, tak wysoko w hierarchii, jak tylko chcesz. Może to być dowolny zestaw.

— David Lewis,