lemat o pompowaniu

Zdania. Tautologie. Język matematyki. Wszelkie zagadnienia związane z logiką matematyczną...
robertos18
Użytkownik
Użytkownik
Posty: 423
Rejestracja: 6 paź 2014, o 20:03
Płeć: Mężczyzna
Lokalizacja: Torun
Podziękował: 127 razy
Pomógł: 2 razy

lemat o pompowaniu

Post autor: robertos18 »

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}\) ?
Ostatnio zmieniony 29 maja 2019, o 01:28 przez Jan Kraszewski, łącznie zmieniany 2 razy.
Powód: Nieregulaminowy zapis - obrazki zamiast zapisu w LaTeX-u.
krl
Użytkownik
Użytkownik
Posty: 609
Rejestracja: 10 lis 2009, o 22:39
Płeć: Mężczyzna
Lokalizacja: Wrocław
Pomógł: 135 razy

Re: lemat o pompowaniu

Post autor: krl »

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}\)).
robertos18
Użytkownik
Użytkownik
Posty: 423
Rejestracja: 6 paź 2014, o 20:03
Płeć: Mężczyzna
Lokalizacja: Torun
Podziękował: 127 razy
Pomógł: 2 razy

lemat o pompowaniu

Post autor: robertos18 »

Ok dziękuję rozumiem rozwiązanie znalezione w moich notatkach o jakie luki chodzi?
krl
Użytkownik
Użytkownik
Posty: 609
Rejestracja: 10 lis 2009, o 22:39
Płeć: Mężczyzna
Lokalizacja: Wrocław
Pomógł: 135 razy

Re: lemat o pompowaniu

Post autor: krl »

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.
ODPOWIEDZ