Języki regularne - lemat o pompowaniu

Lewo · Post autor: **Lewo** » 7 sty 2016, o 00:04

Jest język \(\displaystyle{ L = \{abba\}}\) ( z jednym słowem \(\displaystyle{ abba}\) )
Wiem, że jest regularny, ale nie wiem jak znaleźć jakąkolwiek stałą \(\displaystyle{ n}\) ( z lematu o pompowaniu ), jakbym chciał to sprawdzić przez ten lemat. Tzn pompowanie jakiekolwiek części ze środka tego słowa da jakieś inne słowo które nie jest w języku \(\displaystyle{ L}\).

Medea 2 · Post autor: **Medea 2** » 7 sty 2016, o 17:14

... egularnych

\(\displaystyle{ n = 5}\)

Lewo · Post autor: **Lewo** » 7 sty 2016, o 20:10

a możesz mi powiedzieć, jak dzielisz słowo i którą dokładnie część mogę pompować w nieskończoność i będzie należeć do języka z jednym słowem?

ps. definicje pomowania z wykładu się trochę różni i mam napisane że
\(\displaystyle{ n \le \left| word\right|}\)

Medea 2 · Post autor: **Medea 2** » 7 sty 2016, o 20:23

Nie dzielę słowa, nie pompuję żadnej jego części i nie ma w tym żadnej sprzeczności.

Lewo · Post autor: **Lewo** » 8 sty 2016, o 03:17

okej, ale jak czytam

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Lemat_o_pompowaniu_dla_j%C4%99zyk%C3%B3w_regularnych

to jest napisane

Nieformalnie - dostatecznie długie słowo w języku regularnym może być pompowane

plus

Jeżeli dany język L jest regularny, to istnieje takie \(\displaystyle{ n\geq 1}\), ...

rozumiem, że twierdzenie służy do wykluczania regularności, ale dla języka regularnego powinno dać się znaleźć takie \(\displaystyle{ n}\) które spełni resztę twierdzenia ( czyli, że jest jakiś podział słowa który można pompować ).
W tym przypadku jest to język z jednym słowem także "brute forcem" jak szukam podziału słowa to nie mogę znaleźć.

Medea 2 · Post autor: **Medea 2** » 8 sty 2016, o 06:43

Nie mam pojęcia, czego właściwie dotyczy ten lemat, ale podstawowa wiedza ze wstępu do matematyki powinna wystarczyć, żeby zrozumieć, dlaczego \(\displaystyle{ n = 5}\) jest dobre.

Można to nawet uogólnić.

Lemat. Niech \(\displaystyle{ L}\) będzie językiem o skończenie wielu słowach. Wtedy \(\displaystyle{ L}\) jest regularny.

"Niedowód". Nie ma sprzeczności z lematem o pompowaniu dla \(\displaystyle{ n}\) równego długości najdłuższego słowa z \(\displaystyle{ L}\) powiększonej o jeden. Jeżeli słowo jest dłuższe niż \(\displaystyle{ n}\), to można je podzielić na trzy części (implikacja spełniona w próżni, bo takie słowa nie istnieją!).

Lemat nie służy sprawdzaniu regularności (jak zauważyłeś), ale nieregularności. Przyjrzyj się definicji regularności.

norwimaj · Post autor: **norwimaj** » 8 sty 2016, o 08:41

Medea 2 pisze:Lemat. Niech \(\displaystyle{ L}\) będzie językiem o skończenie wielu słowach. Wtedy \(\displaystyle{ L}\) jest regularny.

Czy masz na uwadze, że lemat o pompowaniu mówi: "Jeśli język jest regularny, ..."?

A co do \(\displaystyle{ n=5}\) oczywiście masz rację. Prawdziwe jest każde zdanie postaci: "Jeśli \(\displaystyle{ w\in L}\) jest słowem długości co najmniej \(\displaystyle{ 5}\), to ...".

Medea 2 · Post autor: **Medea 2** » 8 sty 2016, o 09:03

Tak, mam. To, co napisałam niżej, nie jest dowodem tego faktu (stąd "niedowód"). Ja bym narysowała drzewo, w którym ścieżki od liści do korzenia odpowiadają słowom języka. Czy taki dowód nie byłby już poprawny?

norwimaj · Post autor: **norwimaj** » 8 sty 2016, o 20:31

Tak, taki automat załatwia sprawę. A żeby to miało jakiś związek z treścią zadania, to dodajmy, że liczba stanów automatu jest dobrym \(\displaystyle{ n}\) do tezy lematu o pompowaniu.

Lewo · Post autor: **Lewo** » 9 sty 2016, o 02:02

ok słowo "co najmniej" w twierdzeniu mnie pokonało, ale w końcu zrozumiałem. dzięki za pomoc.