Jest uzupełnieniem {www | …} Bez kontekstu?

Dobrze wiadomo, że uzupełnienie jest pozbawione kontekstu. Ale co z dopełnieniem ? $\{ ww \mid w\in \Sigma^*\}$ $\{ www \mid w\in \Sigma^*\}$

fl.formal-languages context-free domotorp
źródło

Odkryłem, że jest to Twierdzenie 4 w P. Dömösi, S. Horváth, M. Ito, L. Kászonyi, M. Katsura: Języki formalne składające się z prymitywnych słów. link.springer.com/chapter/10.1007/3-540-57163-9_15

domotorp

Odpowiedzi:

Nadal CFL, jak sądzę, z adaptacją klasycznego dowodu. Oto szkic.

Zastanów się , który jest uzupełnieniem , z usuniętymi słowami o długości nie mod . $L = \{xyz : |x|=|y|=|z| \land (x \neq y \lor y \neq z)\}$ $\{www\}$ $0$ $3$

Niech . Oczywiście jest CFL, ponieważ możesz odgadnąć pozycję i uznać, że kończy po tym. Pokazujemy, że . $L' = \{uv : |u| \equiv_3 |v| \equiv_3 0 \land u_{2|u|/3} \neq v_{|v|/3}\}$ $L'$ $p$ $u$ $p/2$ $L = L'$

$L \subseteq L'$ : Niech . Załóżmy, że istnieje takie jak . Następnie napisz dla pierwszych pierwszych znaków , a dla pozostałych. Oczywiście . Co to jest ? Pierwszy: $w = xyz \in L$ $p$ $x_p \neq y_p$ $u$ $3p/2$ $w$ $v$ $u_{2|u|/3} = x_p$ $v_{|v|/3}$

| v | / 3 = (| w | - 3 p / 2) / 3 = | w | / 3 - p / 2.

$|v|/3 = (|w| - 3p/2)/3 = |w|/3 - p/2.$

Zatem w jest to pozycja: lub innymi słowy, pozycja w . To pokazuje, że . $w$

| u | + | v | / 3 = 3 p / 2 + | w | / 3 - p / 2 = | w | / 3 + p,

$|u|+|v|/3 = 3p/2 + |w|/3 - p/2 = |w|/3 + p,$

p

$p$

y

$y$

u_{2 | u | / 3} = x_{p} \neq y_{p} = v_{| v | / 3}

$u_{2|u|/3} = x_p \neq y_p = v_{|v|/3}$

Jeśli , niech będzie pierwszymi znakami , tak że to ; jest resztą . Następnie: stąd podobnie, . $y_p \neq z_p$ $u$ ${3\over2}(|w|/3 + p)$ $w$ $u_{2|u|/3}$ $y_p$ $v$ $w$

| u | + | v | / 3 = 2 | w | / 3 + p

$|u| + |v|/3 = 2|w|/3 + p$

v_{| v | / 3} = z_{p}

$v_{|v|/3} = z_p$

$L' \subseteq L$ : Cofamy poprzedni proces. Niech . Napisz . Następnie: Zatem i (ponieważ jeśli ma postać , to musi zawierać, że dla wszystkich ). $w = uv \in L'$ $p = 2|u|/3$ $p + | w | / 3 = 2 | u | / 3 + | u v | / 3 = | u | + | v | / 3.$ $p+|w|/3 = 2|u|/3+|uv|/3 = |u| + |v|/3.$ $w_p = u_{2|u|/3} \neq v_{|v|/3} = w_{p + |w|/3}$ $w \in L$ $w$ $xxx$ $w_p = w_{p+|w|/3}$ $p$

Michaël Cadilhac
źródło

Wow, niesamowite! Nie twierdzę, że śledziłem każdy szczegół twojego argumentu, tak jak nie rozumiem, co masz na myśli przez ostatnią linię („za ostatni bit”), ani dlaczego nie rozdzielasz sprawy, gdy , ale twoje rozwiązanie ostatecznie działa. Podsumowałbym główną sztuczkę jako . Podobna sztuczka działa również dla uzupełnienia dowolnego . Zastanawiam się, czy jest pozbawiony kontekstu, czy nie.

| w | / 3 < p / 2

$|w|/3<p/2$

3 a + 3 b = 2 a + (b - a) + 2 a + 2 b

$3a+3b=2a+(b-a)+2a+2b$

L_{r} = {w^{r}}

$L_r=\{w^r\}$

L^{'} = {x y z : | x | = | y | = | z | \land (x \neq y)}

$L' = \{xyz : |x|=|y|=|z| \land (x \neq y)\}$

domotorp

@domotorp: Na zdrowie! W porządku, „ostatni kawałek” był niepotrzebny, dzięki! Jeśli chodzi o „przypadek, w którym ”, nie jestem pewien, co masz na myśli. Przegapiłem coś? Co do twojego , zastanawiałem się, czy to samo robi ten „dowód”! Jeszcze nie jestem pewien :)

| w | / 3 < p / 2

$|w|/3 < p/2$

L^{'}

$L'$

Michaël Cadilhac

Och, mój zły, zawsze się trzyma!

p / 2 \leq | w | / 3

$p/2\le |w|/3$

domotorp

Prawdopodobnie nie jest to problem, ale może być nieparzyste, więc powinieneś poradzić sobie z przypadkami Gdy jest nieparzyste.

p

$p$

| u | = 3 p / 2 (?)

$|u| = 3p/2 (?)$

p

$p$

Marzio De Biasi

@MarzioDeBiasi: Tak, właśnie dlatego jest to szkic :-)

Michaël Cadilhac

Oto sposób, w jaki myślę o rozwiązaniu tego problemu za pomocą PDA. Moim zdaniem jest to intuicyjnie wyraźniejsze.

Słowo $x$ $www$ $|x| \not\equiv 0$ $a$ $b$ $|w|$

Używamy zwykłej sztuczki polegającej na stosowaniu stosu w celu utrzymania liczby całkowitej poprzez posiadanie nowego symbolu spodzie stosu , przechowującego wartość bezwzględnąjako liczba liczników na stosie i sgn ( ) według stanu PDA. W ten sposób możemy zwiększyć lub zmniejszyć wykonując odpowiednią operację. $t$ $Z$ $|t|$ $t$ $t$

Celem jest użycie niedeterminizmu do odgadnięcia pozycji dwóch porównywanych symboli i użycie stosu do zarejestrowania , gdzie jest odległością między tymi dwoma symbolami. $t := |x|-3d$ $d$

Dokonujemy tego w następujący sposób: inkrement dla każdego widocznego symbolu aż do wybrania pierwszego odgadniętego symbolu i zapisz w stanie. Dla każdego kolejnego symbolu wejściowego, dopóki nie zdecydujesz, że zobaczyłeś , zmniejsz o ( dla długości wejściowej i dla odległości). Odgadnij pozycję drugiego symbolu i zapisz, czy . Kontynuuj zwiększanie dla kolejnych symboli wejściowych. Zaakceptuj, jeśli (wykrywalne przez u góry) i . $t$ $a$ $a$ $b$ $t$ $2$ $1$ $-3$ $b$ $a \not= b$ $t$ $t = 0$ $Z$ $a \not= b$

Zaletą tego jest to, że powinno być całkowicie jasne, jak rozszerzyć to na arbitralne uprawnienia.

Jeffrey Shallit
źródło

Rzeczywiście, bardzo schludnie!

domotorp

Ach, o wiele ładniej :-)

Michaël Cadilhac

Po prostu inna perspektywa („zorientowana na gramatykę”), aby udowodnić, że dopełnieniem $\{ w^k \}$ jest CF dla dowolnego ustalonego $k$ używającego właściwości zamknięcia.

Pierwsza wzmianka, że w dopełnienia $\{ w^k \}$ zawsze istnieje $i$ takie, które $w_i \neq w_{i+1}$ . Koncentrujemy się na $w_1 \neq w_2$ i zaczynamy od prostej gramatyki CF, która generuje:

$L = \{\underbrace{a00...0}_{w_1} \; \underbrace{b00...0}_{w_2} ... \underbrace{000...0}_{w_k} \mid |w_i|=n \} = \{ a 0^{n-1} \, b 0^{n(k-1)-1} \}$

Np. Dla $k = 3$ mamy $L = \{ a\,b\,0, a0\,b0\,00, a00\,b00\,000, ...\}$ , $G_L = \{ S \to ab0 | aX00, X \to 0X00 | 0b0 \}$

Następnie zastosuj zamknięcie w warunkach odwrotnego homomorfizmu i zjednoczenie :

Pierwszy homomorfizm: $\varphi(1) \to a, \varphi(0) \to b, \varphi(1)\to 0, \varphi(0) \to 0$

Drugi homomorfizm: $\varphi'(0) \to a, \varphi'(1) \to b, \varphi'(1)\to 0, \varphi'(0) \to 0$

$L' = \varphi^{-1}(L) \cup \varphi'^{-1}(L)$ wciąż nie zawiera kontekstu

Zastosuj zamknięcie przy cyklicznych przesunięciach do $L'$ aby uzyskać zestaw ciągów o długości $kn$ nie w postaci $w^k$ :

$L'' = Shift(L') = \{ u \mid u \neq w^k \land |u| = kn \}$ .

Na koniec dodaj zwykły zestaw ciągów, których długości nie można podzielić przez $k$ , aby uzyskać dokładnie dopełnienie $\{w^k\}$ :

$L'' \cup \{\{0,1\}^n\mid n \bmod k \neq 0\} = \{ u \mid u \neq w^k\}$

Marzio De Biasi
źródło