Dodatkowo podpowiedź:Korzystając z lematu o pompowaniu pokazać, że następujący język jest regularny.
\(\displaystyle{ B = \left\{ a^{n}b^{m} | n \neq m \right\}}\)
Rozwiązanie:\(\displaystyle{ w = a^{p} b ^{p + p!}}\), gdzie p jest stałą pompowania.
Nieregularność języka \(\displaystyle{ B}\) można udowodnić wprost, stosując lemat o pompowaniu. Załóżmy, że:
1: Język B jest regularny
2: Słowo \(\displaystyle{ w \in B}\)
Ustaliłem, że mogą występować trzy przypadki podziału słowa w (na podstawie lematu):
1) przypadek kiedy y leży w całości w części \(\displaystyle{ a^{n}}\).
\(\displaystyle{ x=a^{r} , y = a ^{t}, v=a ^{n-r-t}b ^{m}}\)
wtedy słowo możemy zapisać w postaci: \(\displaystyle{ xy ^{2} v = a^{r}a ^{t}a ^{t}a ^{n-r-t}b ^{m}= a ^{n+t}b ^{m}}\)
Możliwe jest, że słowo pompowane nie należy do języka. Dzieje się tak np. dla \(\displaystyle{ n = 3 , t = 1, m = 4}\).
Ogólnie rzecz ujmując słowa niezgodne w tym przypadku to takie, które spełniają warunek:
\(\displaystyle{ m>n\wedge t=1 \wedge m=n+ t ^{k}}\)
2) przypadek, kiedy \(\displaystyle{ y}\) leży w całości w obu częściach.
\(\displaystyle{ x=a^{n-t} , y = a ^{t}b ^{q} , v=b ^{m-q}}\)
Weźmy słowo \(\displaystyle{ w = a^{n-t} a ^{t}b ^{q}b ^{m-q}}\)
Wtedy kolejne słowo po napompowaniu miałoby postać:
\(\displaystyle{ w' = a^{n-t} a ^{t}b ^{q} a ^{t}b ^{q}b ^{m-q}}\)
Wiemy jednak, że do języka nie należą słowa, które mają na przemian postać \(\displaystyle{ ab}\), a więc \(\displaystyle{ y}\) nie może leżeć w obu częściach, bo wtedy nie należałby do języka \(\displaystyle{ B}\).
3) przypadek, kiedy y leży w całości w części \(\displaystyle{ b^{m}}\).
Podobnie jak w przypadku pierwszym.
\(\displaystyle{ m<n \wedge t=1 \wedge n=m+ t ^{k}}\)
Pyt1: Czy założenia i ogólnie rozwiązanie jest poprawne?
Pyt2: Jak zapisać formalnie takie rozwiązanie?
Pyt3: Martwi mnie jednak brak wykorzystania podpowiedzi... Czy więc ktoś wie jak ją wykorzystać?
Podpowiedź raczej jest dobra dla 3 przypadku, bo dla pierwszego musiałoby być \(\displaystyle{ p = r+ t +s}\)., co oznacza, że ilość a musiałaby być równa stałej pompowania i jednocześnie podziałowi słowa. W drugim przypadku wiemy, że nie jest możliwe stworzenie słowa, które spełnia jednocześnie założenia z lematu o pompowaniu i należy do języka \(\displaystyle{ B}\), więc podpowiedź raczej dotyczy 3 przypadku, a do 1 jego odwrócona wersja... ( mogę się mylić, ale jeśli tak to poprawcie mnie)
