Matematyka.pl

Rozstrzygnij czy jezyk \(\displaystyle{ L _{2}=\left\{ w \in \left\{ a,b\right\} ^{*}: |w| _{a} = 2 |w|_{b}\right\}}\)

Moja odpowiedz:
Załozmy ze \(\displaystyle{ L _{2} \in REG}\). Wtedy istnieje stała \(\displaystyle{ N}\) z LOP.
Weżmy \(\displaystyle{ z=a ^{2N}b ^{N}}\). Oczywiscie \(\displaystyle{ z \in L _{2} }}\) i \(\displaystyle{ |z| = 3N \ge N}\)
Zastanowmy się jak rozlozyc slowo na konkatenacje \(\displaystyle{ z=uvw}\), gdzie
\(\displaystyle{ |uv| \le N}\) i \(\displaystyle{ |v| \ge 1}\). Jedyna mozliwoscia jest, ze
\(\displaystyle{ uv = a ^{p}}\) gdzie \(\displaystyle{ 1 \le p \le N}\)
\(\displaystyle{ v=a ^{q}}\) gdzie \(\displaystyle{ 1 \le q \le p \le N}\)

\(\displaystyle{ \overbrace{\underbrace{aa\ldots aa}_{p-q}\underbrace{aa\ldots aa}_{q}\underbrace{aa\ldots aa}_{2N-p}}^{2N}\overbrace{bb\ldots bb}^{N}}\)

I teraz mam problem bo skąd wzięlo się te \(\displaystyle{ p-q , q}\) i \(\displaystyle{ 2N-p}\).

Na przykład dla \(\displaystyle{ i=2}\),\(\displaystyle{ z _{2}=uv ^{2}w=uvvw=a ^{p-q}a ^{q} a ^{q} a ^{2N-p}b ^{N} =a ^{2N+q} b ^{N}}\) a z tego wychodzi sprzecznosc bo \(\displaystyle{ 2 ^{N+q} \neq 2N}\)
I teraz mam problem dlaczego zostały podstawione takie wartosci \(\displaystyle{ p-q , q}\) i \(\displaystyle{ 2N-p}\) ?

Rozumiem, że masz problem z własną odpowiedzią, z rozumowaniem, które jakoby sam wymyśliłeś.
Nie kupuję tego. Rozumowanie jest zasadniczo poprawne (choć ma pewne wady, luki). Gdybyś sam je wymyślił, to byś je rozumiał.
Co do meritum:
\(\displaystyle{ uv}\) to początkowy odcinek słowa \(\displaystyle{ z=a^{2N}b^N}\), \(\displaystyle{ uv}\) ma długość \(\displaystyle{ p\leq N}\), zaś \(\displaystyle{ v}\) ma długość \(\displaystyle{ q}\). Wobec tego \(\displaystyle{ u}\) (jako słowo \(\displaystyle{ uv}\) pomniejszone o \(\displaystyle{ v}\)) ma długość \(\displaystyle{ p-q}\). Skoro \(\displaystyle{ p\leq N}\), to słowo \(\displaystyle{ uv}\) jest odcinkiem początkowym słowa \(\displaystyle{ a^{2N}}\) (wewnątrz \(\displaystyle{ z}\)). Więc to słowo \(\displaystyle{ a^{2N}}\) rozkłada się kolejno na część \(\displaystyle{ u}\) (długości \(\displaystyle{ p-q}\)), część \(\displaystyle{ v}\) (długości \(\displaystyle{ q}\)) i resztę (długości \(\displaystyle{ 2N-p}\)).

Ok dziękuję rozumiem rozwiązanie znalezione w moich notatkach o jakie luki chodzi?

Luka: gdy rozważasz rozkład słowa \(\displaystyle{ z}\) do postaci \(\displaystyle{ uvw}\), to to nie jest dowolny rozkład, tylko rozkład dostarczony przez lemat o pompowaniu (wtedy ten rozkład ma odpowiednie dalsze własności, które prowadzą do sprzeczności w dowodzie nie wprost). To powinno być powiedziane w dowodzie.