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).
  • 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.