7738996305

Rozdział 1

Słowa skończone

Spisali: Karolina Sołtys i Mateusz Tarkowski

1.1 Wstęp

Zacznijmy od obserwacji, że możemy łatwo opisywać pewne własności słów za pomocą formuł logicznych. Załóżmy, że dysponujemy relacją a(x), oznaczającą, że x-tą literą w słowie jest litera a. Wtedy na przykład formuła 3_X a(x) będzie spełniona dla słów, które zawierają co najmniej jedną literę a, a formuła V_x3j, y > xAa(y) — dla słów, które kończą się na a. W obu przypadkach język złożony ze wszystkich słów, dla których dana formuła jest prawdziwa, jest językiem regularnym — odpowiednie wyrażenia regularne to A*a A* oraz A'a. Nasuwa się pytanie, czy każdy język regularny daje się zapisać za pomocą formuły logiki pierwszego rzędu, oraz czy każda taka formuła wyznacza jakiś język regularny.

Sformalizujmy trochę pojęcia, z których korzystaliśmy w poprzednim akapicie. Niech A będzie skończonym alfabetem i niech w = (iq ... a_n_i będzie słowem nad alfabetem A. Słowo w będziemy reprezentować strukturą relacyjną

w = ({l,...,n}, <(x, y), s(x, y), {a(x)}_a6>ł),

gdzie zbiór {1,... ,n} interpretujemy jako zbiór pozycji w słowie w, s jest relacją następnika, a predykaty a(x) (dla a £ A) wyznaczają pozycje w słowie, na których znajduje się litera a.

Przez L_v będziemy oznaczać język zdefiniowany formułą p:

= {w £ A* : w\= <p}.

Okazuje się, że nie wszystkie języki regularne dają się wyrazić za pomocą formuły logiki pierwszego rzędu. Z poniższego lematu wynika, że nie możemy tak wyrazić np. języka (aa)*.

Lemat 1. Dla każdej formuły ip £ FO(<,s) o rozmiarze n zachodzi a²" 1= p -*=> a²"⁺¹ [= ip.

Dowód

Dowód polega na nietrudnej analizie gry Ehrenfeuchta na słowach a² i a² +1. Szczegóły pozostawiamy czytelnikowi. □

5