[Gramatyki] Lemat o pompowaniu

turson
Użytkownik
Użytkownik
Posty: 36
Rejestracja: 31 maja 2015, o 13:26
Płeć: Mężczyzna
Lokalizacja: pl
Podziękował: 3 razy
Pomógł: 1 raz

[Gramatyki] Lemat o pompowaniu

Post autor: turson »

\(\displaystyle{ L = \{a^nb^n : n \in \NN \}}\)

Mam wykazać, że to nie jest język regularny. Tylko błagam łopatologicznie, bo przeczytałem notatki wykładowcy, artykuły w sieci i dalej nie rozumiem
Ostatnio zmieniony 19 cze 2015, o 00:02 przez Jan Kraszewski, łącznie zmieniany 2 razy.
Powód: Nawiasy klamrowe to \{, \}. Poprawa wiadomości.
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

[Gramatyki] Lemat o pompowaniu

Post autor: Afish »

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Lemat_o_pompowaniu_dla_j%C4%99zyk%C3%B3w_regularnych

Teoria, nawet przykład ten sam.
turson
Użytkownik
Użytkownik
Posty: 36
Rejestracja: 31 maja 2015, o 13:26
Płeć: Mężczyzna
Lokalizacja: pl
Podziękował: 3 razy
Pomógł: 1 raz

[Gramatyki] Lemat o pompowaniu

Post autor: turson »

Niestety nawet tamtejszy opis nic mi nie mówi.
Jak rozumiem słowo \(\displaystyle{ A}\) składa się z części \(\displaystyle{ xyz}\). Zatem:
\(\displaystyle{ xy=a^n}\)
\(\displaystyle{ z=b^n}\)
bo
\(\displaystyle{ |xy|\le n}\)
\(\displaystyle{ n}\) - stała

i tego dalej co tam jest nie rozumiem z \(\displaystyle{ p}\) i \(\displaystyle{ q}\)
Ostatnio zmieniony 17 cze 2015, o 21:25 przez Afish, łącznie zmieniany 1 raz.
Powód: Całe wyrażenia matematyczne umieszczaj w tagach [latex] [/latex].
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

[Gramatyki] Lemat o pompowaniu

Post autor: Afish »

\(\displaystyle{ a^n}\) trzeba rozbić na dwie części, więc przyjmujemy, że jedna część ma długość \(\displaystyle{ p}\), a druga ma długość \(\displaystyle{ q}\).
turson
Użytkownik
Użytkownik
Posty: 36
Rejestracja: 31 maja 2015, o 13:26
Płeć: Mężczyzna
Lokalizacja: pl
Podziękował: 3 razy
Pomógł: 1 raz

[Gramatyki] Lemat o pompowaniu

Post autor: turson »

Rozumiem jak dotąd.
Dalej jest
\(\displaystyle{ a^{n-p-q}b^n}\)
i tutaj nie czaję
\(\displaystyle{ a^{n-p-q}}\)
to skąd bierze się \(\displaystyle{ n-p-q}\) zamiast \(\displaystyle{ p+q}\), bo moim zdaniem \(\displaystyle{ n-p-q}\) da 0
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

[Gramatyki] Lemat o pompowaniu

Post autor: Afish »

Nie da zera, bo \(\displaystyle{ p + q < n}\), ponieważ z założenia mamy \(\displaystyle{ |xy|<n}\). A dalej mamy \(\displaystyle{ a^{n-p-q}}\), co oznacza resztkę literek \(\displaystyle{ a}\) bez części \(\displaystyle{ x}\) i \(\displaystyle{ y}\).
turson
Użytkownik
Użytkownik
Posty: 36
Rejestracja: 31 maja 2015, o 13:26
Płeć: Mężczyzna
Lokalizacja: pl
Podziękował: 3 razy
Pomógł: 1 raz

[Gramatyki] Lemat o pompowaniu

Post autor: turson »

U mnie na wykładzie założenie wyglądało trochę inaczej, bo
\(\displaystyle{ |xy| \le n}\)
to w tym wypadku może dać 0.
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

[Gramatyki] Lemat o pompowaniu

Post autor: Afish »

No to da zero (w szczególnym przypadku), co i tak nic nie zmienia.
turson
Użytkownik
Użytkownik
Posty: 36
Rejestracja: 31 maja 2015, o 13:26
Płeć: Mężczyzna
Lokalizacja: pl
Podziękował: 3 razy
Pomógł: 1 raz

[Gramatyki] Lemat o pompowaniu

Post autor: turson »

Ok. Idźmy dalej.

Więc
\(\displaystyle{ A=BCD
\\B=a^p
\\C=a^q
\\D=b^n}\)

więc
\(\displaystyle{ A=a^pa^qb^n}\)

dopompowuję C. Załóżmy, że dodaję 1 więcej, więc mam
\(\displaystyle{ A=BC^iD =a^p(a^q)^2b^n=a^pa^qa^qb^n=a^pa^{2q}b^n}\)
dobrze?
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

[Gramatyki] Lemat o pompowaniu

Post autor: Afish »

Trochę nieprecyzyjnie. Co to jest \(\displaystyle{ i}\)? No i jaki wniosek z tego pompowania płynie?
turson
Użytkownik
Użytkownik
Posty: 36
Rejestracja: 31 maja 2015, o 13:26
Płeć: Mężczyzna
Lokalizacja: pl
Podziękował: 3 razy
Pomógł: 1 raz

[Gramatyki] Lemat o pompowaniu

Post autor: turson »

\(\displaystyle{ N \in \mathbb{N}
\\A=BCD
\\B=a^p
\\C=a^q
\\D=b^n
\\
\\A=BCD=a^p a^q b^n
\\p+q \le N}\)

więc \(\displaystyle{ BC}\) jest zgodne z warunkiem
\(\displaystyle{ |BC| \le N}\)

dalej pompowanie.
można zastosować przykład
\(\displaystyle{ i=3
\\BC^3D = a^p a^{q \cdot 3} b^n
\\p+q \cdot 3 > N}\)

co sprzeczne z warunkiem
\(\displaystyle{ |BC| \le N}\)
Ostatnio zmieniony 19 cze 2015, o 00:03 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

[Gramatyki] Lemat o pompowaniu

Post autor: Afish »

Źle. Nie chodzi o to, że po pompowaniu długość \(\displaystyle{ BC}\) jest większa od \(\displaystyle{ n}\), bo przecież pompujemy, więc jest to naturalny skutek. Chodzi o to, że przez pompowanie utworzyliśmy słowo, które nie należy do języka.
turson
Użytkownik
Użytkownik
Posty: 36
Rejestracja: 31 maja 2015, o 13:26
Płeć: Mężczyzna
Lokalizacja: pl
Podziękował: 3 razy
Pomógł: 1 raz

[Gramatyki] Lemat o pompowaniu

Post autor: turson »

A nie należy do języka bo...?
Bo symboli a miało być tyle ile jest \(\displaystyle{ n}\), a jest 3x więcej?
Ostatnio zmieniony 19 cze 2015, o 08:48 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
Medea 2
Użytkownik
Użytkownik
Posty: 2491
Rejestracja: 30 lis 2014, o 11:03
Płeć: Kobieta
Podziękował: 23 razy
Pomógł: 479 razy

[Gramatyki] Lemat o pompowaniu

Post autor: Medea 2 »

Bo jezyk składa się ze słów, które mają pewną liczbę liter \(\displaystyle{ a}\), a później tyle samo liter \(\displaystyle{ b}\)?
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

[Gramatyki] Lemat o pompowaniu

Post autor: Afish »

turson pisze:Bo symboli a miało być tyle ile jest N, a jest 3x więcej?
Nie, ciągle nie rozumiesz idei.
Lemat o pompowaniu mówi, że jeżeli mamy język regularny, to możemy dla słowa znaleźć podział na trzy części i jedną z nich pompować, a powstałe słowo ciągle należy do języka. W tej kolejności - fakt, że możemy pompować nie oznacza, że język jest regularny.
Wykorzystując to możemy spróbować zrobić dowód nie wprost - jeżeli pokażemy, że po pompowaniu jakieś słowo nie należy do języka, to z tego wynika, że język nie jest regularny.
Dlatego przyjmujemy, że język jest regularny i istnieje jakaś stała \(\displaystyle{ n}\) z lematu. Potem wybieramy wygodne dla nas słowo z języka i próbujemy pokazać, że po napompowaniu słowo już do języka nie należy, co kończy dowód.
W podanym przez Ciebie przykładzie mamy język składający się ze słów mających pewną liczbę liter \(\displaystyle{ a}\), a potem dokładnie tyle samo liter \(\displaystyle{ b}\). Bierzemy stałą \(\displaystyle{ n}\), o której zakładamy, że istnieje (bo przyjęliśmy, że język jest regularny, więc musi istnieć stała z lematu), następnie bierzemy wygodne dla nas słowo (w tym przypadku wygodą jest fakt, że znamy postać pierwszych dwóch członów rozkładu, a dokładniej wiemy, że mają one tylko litery \(\displaystyle{ a}\)), pompujemy i pokazujemy, że po napompowaniu słowo nie należy do języka, bo ma więcej liter \(\displaystyle{ a}\) niż \(\displaystyle{ b}\). Kompletnie nie interesuje nas tak naprawdę, ile liter ma to słowo, jaką ma postać, albo jak dokładnie wygląda rozkład (w sensie liczby liter w każdej części). Dla nas ważny jest fakt, że możemy napompować tak, aby słowo nie należało do języka, z czego możemy wywnioskować, że język nie jest regularny.
ODPOWIEDZ