Język nie jest regularny - lemat o pompowaniu.

krupka888 · Post autor: **krupka888** » 24 maja 2016, o 13:15

\(\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.

wiedzmac · Post autor: **wiedzmac** » 24 maja 2016, o 16:01

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

krupka888 · Post autor: **krupka888** » 24 maja 2016, o 22:42

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.

wiedzmac · Post autor: **wiedzmac** » 25 maja 2016, o 09:22

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

krupka888 · Post autor: **krupka888** » 27 maja 2016, o 13:46

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:/

wiedzmac · Post autor: **wiedzmac** » 27 maja 2016, o 21:34

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ć.

no_name · Post autor: **no_name** » 8 gru 2016, o 18:33

wiedzmac, jesteś jeszcze obecny na forum ?

wiedzmac · Post autor: **wiedzmac** » 8 gru 2016, o 18:37

Tak, jestem.