Pokaż, że {xy ∣ | x | = | y |, x ≠ y} jest pozbawione kontekstu

Pamiętam, że natrafiłem na następujące pytanie dotyczące języka, który podobno jest pozbawiony kontekstu, ale nie mogłem znaleźć dowodu na to. Czy może źle zapamiętałem pytanie?

Tak czy inaczej, oto pytanie:

Pokaż, że język jest wolne od kontekstu.$L = \{xy \mid |x| = |y|, x\neq y\}$

Twierdzenie : jest pozbawione kontekstu.$L$

Dowód na pomysł : musi istnieć co najmniej jedna różnica między pierwszą a drugą połową; podajemy gramatykę, która upewni się, że ją wygenerujemy, a resztę pozostawi dowolną.

Dowód : dla uproszczenia załóż binarny alfabet . Dowód łatwo rozciąga się na inne rozmiary. Rozważ gramatykę :$\Sigma = \{a,b\}$$G$

$\qquad\begin{align} S &\to AB \mid BA \\ A &\to a \mid aAa \mid aAb \mid bAa \mid bAb \\ B &\to b \mid aBa \mid aBb \mid bBa \mid bBb \end{align}$

Jest całkiem jasne, że generuje

$\qquad \mathcal{L}(G) = \{ \underbrace{w_1}_k x \underbrace{w_2v_1}_{k+l}y\underbrace{v_2}_l \mid |w_1|=|w_2|=k, |v_1|=|v_2|=l, x\neq y \} \subseteq \Sigma^*;$

podejrzany może wykonać zagnieżdżoną indukcję w stosunku do i z rozróżnieniem wielkości liter w parach . Teraz i dojeżdżają do pracy (intuicyjnie, i mogą wymieniać symbole, ponieważ oba zawierają symbole wybrane niezależnie od reszty słowa). Dlatego też, i mają tę samą pozycję (w odpowiednich pół), co oznacza, , ponieważ nie nakłada żadnych ograniczeń innych jego języka.$k$$l$$(x,y)$$w_2$$v_1$$w_2$$v_1$$x$$y$$\mathcal{L}(G) = L$$G$

Zainteresowanym czytelnikom mogą spodobać się dwa problemy:

Ćwiczenie 1 : Wymyśl PDA dla !$L$

Ćwiczenie 2 : Co z ?$\{xyz \mid |x|=|y|=|z|, x\neq y \lor y \neq z \lor x \neq z\}$