Lemat pompowania (język regularny)

Question

Potrzebuję pomocy z problemem lematu pompującego.

L = { {a,b,c}* | #a(L) < #b(L) < #c(L) } 

To właśnie się tak dalece:

y = uvw is the string from the pumping lemma. 

niech Y = abbc^n, n ma długość od lematu pompowania. y jest w L, ponieważ liczba a: s jest mniejsza niż liczba b: s, a liczba b: s jest mniejsza niż liczba c: s.

Pozwoliłem u = a, v = bb i w = c^n. | uv | < y, jak stwierdzono w pompowaniu lematu. Jeśli "pompuję" (bb)^2, otrzymam

y = abbbbc^n which violates the rule #b(L) < #c(L). 

Czy to prawda? Czy jestem na "właściwej ścieżce"?

Dzięki

Answer 1

Ideą pompowania lemat jest powiedzieć, że gdy masz język regularny L z nieskończonej liczby terminów znajduje się wzór w języku, który powtarza się na zawsze.

Wyrażenie regularne powiązane z tym językiem będzie zawierało KLEENE-STAR (wzór).

Automat przypisany do tego wyrażenia regularnego (i języka) będzie zawierał pętlę.

Dowód jest przeprowadzany przy użyciu zasady gołębi.

To jest bardzo sugestywne pod tym numerem .

Należy pamiętać, że wszystkie terminy muszą zaczynać się w q0, a zakończyć w qn w tym przypadku. Zatem automaty definiujące język są skończone (maksymalne stany N), więc istnieje ograniczona liczba stanów, ale słowa (to znaczy terminy) mogą mieć> N liter. Zasada gołębi mówi nam, że musi istnieć stan, który jest osiągany 2 razy, więc w tym stanie będzie obecna pętla.

W swoim zapisie, można dokonać korespondencji z obrazem tak:

• swój u jest x z obrazka

• v jest y w obrazie

• w jest z od image

Aby dotrzeć z q0 do qn, można użyć dowolnego ciągu z zestawu: { uw , uvw, uvvw, uvvvw, ... }.

W tym konkretnym przypadku wzorzec P jest y, zestaw X jest {xz xyz xyyz xyyyz ...} i S jest length(x)+length(y).