Czy {ww '| HamDist (w, w ')> 1} bez kontekstu?

Po przeczytaniu ostatniego pytania „Czy uzupełnienie pozbawione kontekstu?” $\{ www \mid ...\}$ ; Przypomniałem sobie podobny problem, którego nie byłem w stanie odeprzeć:

Czy bez kontekstu? $L = \{ ww' \mid w,w' \in \{0,1\}^* \land |w|=|w'| \land HamDist(w,w')>1 \}$

Tutaj wymagamy, aby dwa struny różniły się co najmniej w dwóch pozycjach (odległość Hamminga musi być większa niż ). $1$

Jest bezkontekstowy, jeśli wymagamy (tzn. Dwa ciągi muszą być po prostu różne). $HamDist(w,w')\geq 1$

Podejrzewam, że język nie jest pozbawiony kontekstu: jeśli przecinamy go ze zwykłymi , otrzymujemy przypadki, w których palmtop powinien „zapamiętać” dwie pozycje w odwrotnej kolejności po osiągnięciu połowy sznurka. $0^*10^*10^*10^*$

Aktualizacja: jeśli przecinamy ze zwykłym , otrzymujemy język bezkontekstowy, jak pokazuje domotorp w jego odpowiedzi; nieco bardziej złożone z (jeszcze aby „śledzić”) nadal sugeruje, że nie powinien być pozbawiony kontekstu. $L$ $R = \{ 0^*10^*10^*10^* \}$ $L \cap R'$ $R' = \{ 0^*10^*10^*10^*10^*10^* \}$ $1$ $L$

fl.formal-languages context-free

— Marzio De Biasi
źródło

L \cap R^{'}

$L\cap R'$ jest w rzeczywistości łatwiejsze, ponieważ dokładnie te słowa nie mają formy (przecięte przez ).

w w

$ww$

R^{'}

$R'$

— domotorp

@domotorp: racja! zmieniono na nieparzyste naprawiono s (chyba że twoją odpowiedź można by dostosować również do , dla każdego ustalonego nieparzystego )

1

$1$

{(0^{*} 1 0^{*})^{k}}

$\{ (0^* 1 0^*)^k \}$

k

$k$

— Marzio De Biasi

Ostatni komentarz: Nie pomaga zaczynać od wiodących zer, ponieważ języki bezkontekstowe są zamknięte na wszelkiego rodzaju cykliczne zmiany. Możesz po prostu wepchnąć je na stos, zaznaczyć ostatni ze specjalnym symbolem, wykonać resztę algorytmu udając, że stos zaczyna się tam, a na końcu go opróżnić. (Wykorzystuje to -transitions, ale to również łatwe, że takie PDA są równoważne z tymi bez.)

ϵ

$\epsilon$

— domotorp

może być łatwiej pomyśleć o alfabecie {0,1,2} i rozważyć ciągi znaków z dokładnie dwoma 1 i 2 2. Nie jest w twoim języku, jeśli odległość między 1s i odległość między 2s są równe n.

— Kaveh

Przecięcie z słowa o parzystości jest pozbawione kontekstu, ponieważ PDA może w pewien sposób zapamiętać dwie pozycje. Tak czy inaczej, niech najpierw zobaczyć, co ten język jest. Jego dopełnieniem jest . Dlatego . Możemy przepisać to jako . $R=\{0^*10^*10^*10^*\mid$ $\}$ $L$ $R\setminus L=\{0^a10^b10^c10^d\mid b=n/2 \vee c=n/2 \vee a+d=n/2\}$ $L=\{0^a10^b10^c10^d\mid b\ne n/2 \wedge c\ne n/2 \wedge a+d\ne n/2\}$ $L=\{0^a10^b10^c10^d\mid b> n/2 \vee c> n/2 \vee a+d> n/2 \vee b,c,a+d<n/2\}$

Pierwsze przypadki można łatwo zweryfikować, podobnie jak czwarty. $3$

$b>n/2$ : Rozpocznij układanie stosu do pierwszego 1, a następnie zacznij wyskakiwać ze stosu, aż nie będzie pusty. Po opróżnieniu ponownie zacznij układać stos, aż dojdziemy do drugiego 1. Od tego momentu pop stos.

$c>n/2$ : To samo.

$a+d>n/2$ : Zacznij wkładać stos do pierwszego 1, a następnie zacznij wyskakiwać ze stosu, aż nie będzie pusty. Po opróżnieniu ponownie zacznij kłaść stos, aż dojdziemy do trzeciego 1. Od tego momentu pop stos.

$b,c,a+d<n/2$ : Zacznij wkładać stos do pierwszego 1, a następnie zacznij wyskakiwać ze stosu, aż nie będzie pusty. Po opróżnieniu ponownie zacznij układać stos, aż dojdziemy do (domyślnie niedeterministycznie, gdzieś między drugim a trzecim 1). Od tego momentu pop stos. $a+n/2$

— domotorp
źródło

Dzięki domotorp, czytam twój pomysł; Myślę, że to (dwa 1s w lewej połowie) unia odwrotna (dwa 1s w prawej połowie). Jak więc uzyskać ?

R ∖ L

$R \setminus L$

{0^{a} 1 0^{b} 1 0^{c^{'}} 0^{c^{″}} 1 0^{d} ∣ (n / 2 = a + b + c^{'} = c^{″} + d + 1) \land [(a = c^{″}) \lor (c^{'} = d)}

$\{ 0^a 1 0^b 1 0^{c'} 0^{c''} 1 0^d \mid \ (n/2=a+b+c'=c''+d+1) \land [(a= c'')\lor (c' = d) \}$

b = n / 2 \lor c = n / 2 \lor a + d = n / 2

$b=n/2 \vee c=n/2 \vee a+d=n/2$

— Marzio De Biasi,

R \subset L

$R\subset L$ jest taki, że HamDist ma najwyżej . Dzieje się tak dokładnie wtedy, gdy dwa z trzech 1-tych pasują, tzn. Jeden jest w tej samej pozycji w pierwszej połowie, tak jak drugi w drugiej połowie. Jeśli te dwa 1 to pierwsze i drugie 1, to otrzymujemy , jeśli są to drugie i trzecie 1, otrzymujemy , a jeśli są to pierwsze i trzecie 1, otrzymujemy , lub równoważnie, (gdzie trochę oszukuję pewnymi stałymi ).

1

$1$

b = n / 2

$b=n/2$

c = n / 2

$c=n/2$

b + c = n / 2

$b+c=n/2$

a + d = n / 2

$a+d=n/2$

\pm 1

$\pm 1$

— domotorp

Czy to odpowiada na pełne pytanie?

— Michaël Cadilhac

@domotorp: ok, rozumiem, dzięki! Kolejna wątpliwość: z (co jest w porządku) piszesz ale czy jest to równoważne z: ? ( pominięto warunek )

L \cap R = {. . . b \neq n / 2 \land c \neq n / 2...}

$L \cap R = \{...b \neq n/2 \land c \neq n/2...\}$

L \cap R = {. . . b > n / 2 \lor c > n / 2 \lor b, c < n / 2}

$L \cap R = \{ ...b > n/2 \lor c > n/2 \lor b,c < n/2 \}$

L \cap R = {. . . (b < n / 2 \lor b > n / 2) \land (c < n / 2 \lor c > n / 2)}

$L \cap R = \{... (b < n/2 \lor b >n/2) \land (c < n/2 \lor c >n/2)\}$

a + d

$a+d$

— Marzio De Biasi

@Michael: Nie.

$~$

— domotorp