JFiZO - Zadanie 09.032

Zadanie 32. Czy język L_3 = \{ w \in \{0, 1, 2\}^* : \not \exists x \in \{0, 1, 2\}^* \, w = xx \} jest bezkontekstowy?

Twierdzenie. L_3 jest bezkontekstowy.

Dowód. Pokażemy gramatykę G, a następnie udowodnimy, że L(G) = L_3. Zbiorem produkcji gramatyki G będą następujące relacje:

S \to X \mid Y \mid Z \mid XY \mid XZ \mid YX \mid YZ \mid ZX \mid ZY

X \to 0 \mid a_1 X a_2 \quad a_1, a_2 \in \{0, 1, 2\}

Y \to 1 \mid a_1 Y a_2

Z \to 2 \mid a_1 Z a_2

  1. L(G) \subseteq L_3
    1. S \to X \mid Y \mid Z – długość jest nieparzysta, więc nie da się podzielić słów na połowy.
    2. S \to XY \quad w = w_1 0 w_2 \, w_3 1 w_4. Niech k = |w_1| = |w_2| i l = |w_3| = |w_4|. Widac zatem, ze |w| = 2\cdot(k + 1 + l). Jesli podzielimy w na polowy o takiej dlugosci, to w kazdej polowie na k-tej pozycji znajda sie dwa rozne symbole.
  2. L_3 \subseteq L(G). Weźmy najkrótsze słowo w z L, które nie da się wyprowadzić z G.
    1. |w| jest nieparzysta, więc można wyprowadzić z X, Y lub Z.
    2. |w| jest parzysta, więc można wyprowadzić z XY, XZ, etc.

Patrzymy na pierwsza pozycje, na ktorej sie roznia polowy, np. w = w_1 0 w_2 \, w_3 1 w_4. Niech k = |w_1| = |w_3| i l = |w_2| = |w_4|.

Mozemy slowo w rozbic na w_1 0 w_2' w_3' 1 w_4 takie, ze |w_2'| = |w_3| i analogicznie |w_3'| = |w_2|. Wtedy |w_1 0 w_2'| = 2k + 1 i |w_3' 1 w_4| = 2l + 1.

Poniewaz to sa slowa o dlugosci nieparzystej, to mozemy je wyprowadzic z X, Y lub Z, a cale slowo z S \to XY \mid \ldots \mid ZY.

Idea

Mamy słowo (bez straty ogólności) w postaci X^i1X^iX^k0X^k, gdzie X→ 0|1|2.
Skąd mamy pewność, że różnią się one na jednej pozycji?
X^i1X^iX^k0X^k = X^i1X^{i+k}0X^k = X^i1X^kX^i0X^k
Jest to słowo składające się z dowolnych i znaków, potem jedynki, dowolnych k znaków, dowolnych i znaków, zera, dowolnych k znaków.
Czyli słowa różniące się na i+1szej pozycji.