====== JFiZO - Zadanie 09.027 ======
$L = \{w:$ dwa razy więcej zer niż jedynek, i parzysta ilość jedynek$\}$
  * $|w|_1 = 2*n$
  * $|w|_0 = 4*n$
  * $|w| = 6*n$

$L' = S \rightarrow \epsilon |$ wszystkie permutacje $000011$ z poprzeplatanymi $S$
  * $L' \subseteq L$ - trivial
  * $L \subseteq L'$ -
    * W każdym $w \in L$ istnieje podciąg, który jest permutacją $000011$.
      * Dowód: niech $f(0w) = -1 + f(w)$, $f(1w) = 2 + f(w)$, $f(\epsilon) = 0$. Wiemy, że $f(w) = 0$. Wykazać, że dla każdego $w \in L$ istnieje $n$ t. że $f(n) = f(n+6)$. TODO
    * Po usunięciu tego podciągu $w$ dalej $\in L$.

Inna solucja:
Pobawmy się taką gramatyką, która w nieterminalu $S$ ma słowa z naszego języka, a w nieterminalu $T$ słowa podobne - z tą jedynie różnicą, że liczba jedynek jest nieparzysta. No i zauważmy, że $S \rightarrow 1T00 | 00T1 | \ldots | 0T0S1 | \ldots | SS$, że $T \rightarrow coś$, no i tu się da rozważyć każdy przypadek i dowód zawierania w obie strony jest za darmo.

{{tag>listy_zadan}}