[Gramatyki] Lemat o pompowaniu
-
- 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
\(\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
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.
Powód: Nawiasy klamrowe to \{, \}. Poprawa wiadomości.
-
- 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
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.
-
- 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
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}\)
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] .
Powód: Całe wyrażenia matematyczne umieszczaj w tagach
-
- 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
\(\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}\).
-
- 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
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
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
-
- 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
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}\).
-
- 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
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?
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?
-
- 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
\(\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}\)
\\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.
Powód: Symbol mnożenia to \cdot.
-
- 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
Ź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.
-
- 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
A nie należy do języka bo...?
Bo symboli a miało być tyle ile jest \(\displaystyle{ n}\), a jest 3x więcej?
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.
Powód: Poprawa wiadomości.
-
- 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
Nie, ciągle nie rozumiesz idei.turson pisze:Bo symboli a miało być tyle ile jest N, a jest 3x więcej?
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.