Używanie pompowania lematu w celu udowodnienia, że język

19

Próbuję użyć lematu pompującego, aby udowodnić, że nie jest regularne. $L = \{(01)^m 2^m \mid m \ge0\}$

Oto co mam do tej pory: Załóżmy, że jest regularne i niech będzie długością pompowania, więc . Rozważ każdy rozkład pompowania taki, że i . $L$ $p$ $w = (01)^p 2^p$ $w = xyz$ $|y| >0$ $|xy| \le p$

Nie jestem pewien, co dalej.

Czy jestem na dobrej drodze? A może jestem daleko?

formal-languages regular-languages pumping-lemma

— Momagic
źródło

1

jesteś na dobrej drodze. jeśli „pompujesz”, zmieniasz liczbę zer i 1, ale nie liczbę 2 (dlaczego?). Doprowadzi to do sprzeczności.

— Ran G.

och, zauważ, że to nie może być

i

. To chyba literówka, a miałeś na myśli

.

| y | > p

$|y|>p$

| x y | < p

$|xy|<p$

| y | > 0

$|y|>0$

— Ran G.

1

Zauważ, że pompowanie lematu nie jest tutaj najszybszym sposobem, ponieważ

jest bardzo zbliżony do kanonicznych przykładów dla języków nieregularnych. Spróbuj użyć właściwości zamknięcia

!

L

$L$

R E G

$\mathrm{REG}$

— Raphael

1

Lub sprawdź dowód lematu pompowania, aby zdać sobie sprawę, że możesz mieć pompowaną strunę również pod koniec i pompować 2s, co jest łatwiejsze.

— vonbrand,

@vonbrand lub weź odwrotną wersję języka i zastosuj do tego prosty lemat pompowania.

— Al.G.

5

Wskazówka: Musisz rozważyć, jak wyglądają wszystkie dekompozycje , więc jakie są wszystkie możliwe rzeczy , i że . Następnie pompujesz każdy z nich i sprawdzasz, czy dostajesz sprzeczność, która będzie słowem nie w twoim języku. Każdy przypadek musi prowadzić do sprzeczności, która byłaby wówczas sprzecznością z pompującym lematem. Voila! Język nie byłby regularny. $w=xyz$ $x$ $y$ $z$ $xyz=(01)^p2^p$

Oczywiście musisz przejść przez szczegóły i rozważyć wszystkie możliwe podziały.

— Dave Clarke
źródło

5

Masz rozkład i ograniczenie długości . Co nam to mówi o tym, jak , i zmieści się w rozkładzie? W szczególności lemat pompowania pozwala ci powtarzać , więc twoim celem jest znalezienie sposobu, w jaki wielokrotne powtarzanie (lub usuwanie , czasem jest to prostsze) nieodwracalnie zaburzy wzór, który definiuje język. $xyz = (01)^p 2^p$ $|xy| \le p$ $x$ $y$ $z$ $y$ $y$ $y$

Wzór ma oczywistą granicę: pierwsza część zawiera powtórzenia , druga część zawiera tylko . Interesujące jest to, gdzie spada. Czy zawsze jest zawarty w jednej z tych części, czy też może obejmować obie te części? $01$ $2$ $y$ $y$

Ponieważ , jest całkowicie zawarte w części , a zawiera wszystkie . Więc jeśli powtórzysz jeszcze raz, otrzymasz dłuższą pierwszą część, ale część pozostaje taka sama. Innymi słowy, kończy się dokładnie literami . Aby poprawnie zakończyć dowód, pokaż, że zawiera zbyt wiele liter i $|xy| \le p$ $xy$ $(01)^p$ $z$ $2$ $y$ $2^p$ $xyyz$ $p$ $2$ $xyyz$ $0$ $1$ pasujące do wyrażenia regularnego.

— Gilles „SO- przestań być zły”
źródło

4

Trzy lata później udowodnimy, że przy nie jest regularne z powodu sprzeczności przy użyciu właściwości zamknięcia (sposób szybszy niż przy użyciu lematu pompującego ). $L = \{(01)^m 2^m \mid m \ge0\}$ $\Delta=\{0,1,2\}$

Najpierw przypuszczamy, że jest regularne. Wiemy, że zwykłe języki są zamknięte pod wpływem odwrotnego homomorfizmu. $L$

Rozważ homomorfizm z: $h:\Sigma^* \rightarrow \Delta^*$

$\Sigma = \{a,b\}$

$h(a)= 01$

$h(b)= 2$

Odwrotny homomorfizm jest: $L$

$h^{-1}(L)= \{a^nb^n| n\geq 0 \} = L'$

$L'$ $L$

— Renato Sanhueza
źródło

3

$a$ $b$ $c$ $ac$ $bc$

$n$ $(01)^1$ $(01)^2$ $\ldots$ $(01)^{n+1}$ $(01)^p$ $(01)^q$ $p\neq q$ $(01)^p2^p$ $(01)^q2^p$ $L$

— Louis
źródło

Używanie pompowania lematu w celu udowodnienia, że ​​język

Używanie pompowania lematu w celu udowodnienia, że język