Czy następująca transformacja zachowuje płynność kontekstową?

Napotkałem ten problem związany z manipulowaniem językiem bezkontekstowym. Niech będzie językiem bezkontekstowym. Zdefiniuj dla każdego . Czy zawsze jest pozbawione kontekstu? Domyślam się, że zachowa kontekstowość. Czy ktoś może przedstawić podstawowy dowód na to? $L$ $L^{\#} = \{ x : x^i \in L$ $i=0,1,2,...\}$ $L^{\#}$

formal-languages context-free

— guest100008
źródło

Gdy zamieszczasz pytanie w dwóch witrynach, ludzie doceniają je, jeśli zostawisz komentarz na temat zamieszczania postów, prowadząc do pytania na drugiej stronie.

— Tara B

Komentarz: w przypadku zwykłych języków jest to poprawne. Pozwolić

L \in R E G

$L\in REG$ , więc

L

$L$ ma DFA z

n

$n$ stwierdza wtedy dla każdego słowa

x

$x$ , gdyby

x, x^{2}, . . ., x^{n + 1}

$x,x^2,...,x^{n+1}$ wszyscy są w środku

L

$L$ , następnie

x \in L^{#}

$x\in L^\#$ , abyśmy mogli zbudować DFA, który rozpoznaje

L^{#}

$L^\#$ . Zastosowanie skończoności DFA sugeruje, że twierdzenie może nie być prawdziwe w przypadku świetlówek kompaktowych.

— Shaull

student.cs.uwaterloo.ca/~cs462 Zestaw problemów 7. Chciałem dodać znacznik zadania domowego, ale to nie zadziałało (?)

— Hendrik Jan

@HendrikJan Wygląda na to, że nie mają tutaj tagu pracy domowej

— Виталий Олегович

@VitalijZadneprovskij Tak się wydaje! Rozwiązanie jest planowane na 5 marca 2013 r. Odpowiem więc w najbliższą środę, kiedy będzie to nadal potrzebne. Świetny problem.

— Hendrik Jan

Kontrprzykład:

$L_1 = \{a^n b^n c^m \mid m,n \ge 1 \}$

$L_2 = \{a^m b^n c^n \mid m,n \ge 1 \}$

$L = (L_1 \cdot L_2^*) \cup \epsilon$ jest bezkontekstowy.

Każde niepuste słowo $x \in L^\#$ ma prefiks $p = a^n b^n c^m \in L_1$ . To musi być $n = m$ , ponieważ z powodu $L_2$ , dowolna para a $b^+$ i bezpośredni sukces $c^+$ w $x$ (po $p$ ) musi dzielić ten sam wykładnik. W związku z tym:

$L^\# = (\{a^n b^n c^n \mid n \ge 1 \} \cdot L_2^*) \cup \epsilon$ , który nie jest pozbawiony kontekstu.

— Simon S.
źródło

Nie jestem pewien, czy rozumiem, co chcesz powiedzieć. Ciąg jak

x = a^{n} b^{n} c^{n} a^{k} b^{k} c^{k}

$x = a^n b^n c^n a^k b^k c^k$ jest w

L^{#}

$L^\#$ ponieważ

a^{n} b^{n} c^{n} \in L_{1}, L_{2}

$a^n b^n c^n \in L_1,L_2$ i

a^{k} b^{k} c^{k} \in L_{2}

$a^k b^k c^k \in L_2$ , dzięki czemu możesz produkować wszystkie moce

x

$x$ z

x^{2} \in L_{1} L_{2} L_{2} L_{2} \subset L

$x^2 \in L_1 L_2 L_2 L_2 \subset L$ i tak dalej.

— Simon S

Jednak zdałem sobie sprawę, że umieściłem

L^{#}

$L^\#$ źle w jakiś sposób.

— Simon S

Rzeczywiście brakowało mi niektórych ciągów, ale moje argumenty nie były jasne, zgadzam się i prawdopodobnie źle napisane. Teraz wygląda mi to dobrze. Dzięki. Teraz usuwam ten komentarz.

— Hendrik Jan