====== 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$

  - $L(G) \subseteq L_3$
    - $S \to X \mid Y \mid Z$ -- długość jest nieparzysta, więc nie da się podzielić słów na połowy.
    - $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.
  - $L_3 \subseteq L(G)$. Weźmy najkrótsze słowo $w$ z $L$, które nie da się wyprowadzić z $G$.
    - $|w|$ jest nieparzysta, więc można wyprowadzić z $X$, $Y$ lub $Z$.
    - $|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+1$szej pozycji.