Matematyka.pl

\(\displaystyle{ \left\{ z\in\left\{0,1\right\}^{*}:z\mbox{ ma tyle }1\mbox{ co 0} \right\}}\). Pokazać przy pomocy lematu o pompowaniu, że język nie jest regularny.

Z czym konkretnie masz problem? Napisz to ci pomogę.

Wiem jak udowodnić, że język nie jest regularny dla \(\displaystyle{ 0^n1^n}\) ale to jest tylko szczególny przypadek i będzie to palindrom. Nie wprost - Biorę \(\displaystyle{ i=2}\) (część pompowana) czyli \(\displaystyle{ xyyz}\) i doprowadzam do sprzeczności. Nie wiem jak zabrać się za zadanie gdy np. \(\displaystyle{ 0^{n-m}1^{n-k}0^{m}1^{k}}\) i to jeszcze chyba nie jest koniec, bo taki ciąg może być jeszcze dłuższy.

To wystarczy. W lemacie o pompowaniu masz ,,dla każdego słowa", więc wystarczy jak wskażesz jedno dla którego nie działa. Ogólnie możesz poczytać sobie dowód i wyrobić sobie pewnie intuicje czytając te slajdy:
... mall15.pdf

Jeszcze mam pytanie, czy ten język jest bezkontekstowy. Jedyne co mi przychodzi na myśl, to lemat o pompowaniu dla języka bezkontekstowego, gdy dzielimy wyraz na 5 części i 2 są pompowane. Wtedy trzeba doprowadzić do sprzeczności i uzyska się, że język nie jest bezkontekstowy. Jak język jest regularny to jest bezkontekstowy, ale wiem, że jest nieregularny:/

Tak jak języki regularne są równoważne z automatami, to języki bezkontekstowe są równoważne z automatami ze stosem. Dość łatwo tutaj taki automat napisać.
Jeśli chcesz większą podpowiedź to daj znać.

wiedzmac, jesteś jeszcze obecny na forum ?

Tak, jestem.