Lemat o pompowaniu dla języków regularnych.

Zdania. Tautologie. Język matematyki. Wszelkie zagadnienia związane z logiką matematyczną...
meron1122
Użytkownik
Użytkownik
Posty: 35
Rejestracja: 10 lut 2016, o 21:26
Płeć: Mężczyzna
Lokalizacja: Wielkopolska
Podziękował: 14 razy

Lemat o pompowaniu dla języków regularnych.

Post autor: meron1122 »

Jest takie zadanko, by wykazać że poniższy język nie jest regularny na podstawie rzeczonego lematu.
Język:
\(\displaystyle{ L=\{a^{n}b^{n-2}a^{n}: n \ge 0\}}\)
Język nie jest regularny, rozumiem że mogę go "pompować" na 3 sposoby:
1. Poprzez człon złożony z samych "\(\displaystyle{ a}\)"
2. Poprzez człon złożony z "\(\displaystyle{ ab}\)"
3. Oraz przez człon złożony z samych "\(\displaystyle{ b}\)".

Niestety nie mam pojęcia jak to zapisać formalnie, by udowodnić to w sposób pisemny. Będę wdzięczny za nakierowanie.
Ostatnio zmieniony 15 wrz 2020, o 20:33 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Nawiasy klamrowe to \{,\}. Poprawa wiadomości.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Lemat o pompowaniu dla języków regularnych.

Post autor: Dasio11 »

Załóż nie wprost, że podany język jest regularny. Z lematu o pompowaniu dostaniesz pewną liczbę naturalną \(\displaystyle{ N}\) o własności sformułowanej w tym lemacie - zastosuj ją do słowa \(\displaystyle{ a^{N+2} b^N a^{N+2}}\).
meron1122
Użytkownik
Użytkownik
Posty: 35
Rejestracja: 10 lut 2016, o 21:26
Płeć: Mężczyzna
Lokalizacja: Wielkopolska
Podziękował: 14 razy

Re: Lemat o pompowaniu dla języków regularnych.

Post autor: meron1122 »

Czemu akurat \(\displaystyle{ N+2}\) dla słów granicznych a nie pompowanie środka na przykład? I Czemu akurat +2?
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Lemat o pompowaniu dla języków regularnych.

Post autor: Dasio11 »

Chyba niezbyt rozumiem o co pytasz.

Czemu wybrałem akurat słowo \(\displaystyle{ a^{N+2} b^N a^{N+2}}\)? - Dlatego że w ten sposób da się rozwiązać zadanie. Oczywiście jest wiele takich słów, które prowadzą do równie dobrego rozwiązania, chociażby \(\displaystyle{ a^{N+7} b^{N+5}, a^{N+7}}\), ale żeby dać Ci sensowną wskazówkę musiałem któreś wybrać.

Czemu "nie pompowanie środka"? - Kto mówi, że masz nie pompować środka? Dysponując odpowiednią wersją lematu o pompowaniu można pompować zarówno początek, środek, jak i koniec, ale znów: trzeba się na coś zdecydować.

Możliwe jednak że znana Ci wersja lematu pozwala pompować tylko początek - jeśli masz takie obawy, to sformułuj ten lemat w postaci, którą dysponujesz.
meron1122
Użytkownik
Użytkownik
Posty: 35
Rejestracja: 10 lut 2016, o 21:26
Płeć: Mężczyzna
Lokalizacja: Wielkopolska
Podziękował: 14 razy

Re: Lemat o pompowaniu dla języków regularnych.

Post autor: meron1122 »

Więc tak, opieram się na deifnicji z wikipedii(

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Lemat_o_pompowaniu_dla_j%C4%99zyk%C3%B3w_regularnych
, będę wdzięczny za korekcję toku myślenia.

Muszę dowolne słowo \(\displaystyle{ z}\) rozłożyć na 3 człony \(\displaystyle{ xy^{k}z}\) oraz udowodnić że pompując \(\displaystyle{ y}\)(dla każdego \(\displaystyle{ k}\)) otrzymam wyraz nie będący w jezyku.
Dlatego nie rozumiem czemu rozpompowujemy człony związane z \(\displaystyle{ a}\).

Moje rozumowanie:
Formalnie w moim przypadku jest język(już nie mogę zmienić w treści tematu, ale zmiana jest kosmetyczna) \(\displaystyle{ L=\{a^{n}b^{n+2}a^{n}: n \ge 0\}}\), więc podział na 3 słowa może prowadzić do tego że słowo \(\displaystyle{ y}\) może być zbudowane z \(\displaystyle{ a}\), \(\displaystyle{ ab}\) i \(\displaystyle{ b}\).
W przypadku pompowania po \(\displaystyle{ a}\) nie spełniamy kryterium że \(\displaystyle{ a^{n}}\)
W przypadku pompowania po \(\displaystyle{ ab}\) rozsypuje nam się cała definicja w języku bo mamy styk abab, którego język nie dopuszcza
W przypadku nr. 3 mamy analogicznie jak w przypadku nr 1.
ODPOWIEDZ