5

Potrzebuję pomocy z problemem lematu pompującego.Lemat pompowania (język regularny)

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

+0

Próbujesz użyć lematu pompowania, aby udowodnić, że opisany język jest regularny? Lub, że nie jest regularny?Tak czy inaczej, nie możesz wybrać podłańcucha do powtórzenia: lemat pompowania mówi jedynie, że istnieje jakieś * n * takie, że w dowolnym zdaniu * s * długości> = * n * istnieje podział na * s * do * uvw * takie, że | * uw * | <* n *, | * v * | > = 1 i * u * * v *^* i * * w * to zdanie dla wszystkich * i *. (Ponieważ "c" jest zawsze powtarzalne w tym języku, możesz mieć problem ze znalezieniem zdań, w których dzielenie zdania na niektóre wewnętrzne c nie działa.) –

Odpowiedz

6

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

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

+0

Dziękuję za to zdjęcie. Ale czy wybrałem dobry sznur do pompowania? – mrjasmin