7738996296

Mnożenie macierzy jest zdefiniowane następująco:

(M- W)(m) = mg(M(p,r)). (W(r,«)).

Po wprowadzeniu tej terminologii możemy napisać, że:

M_w._v = M_W-M_V

Inaczej mówiąc, przyporządkowanie w i-» M_w jest homormofizmem monoidów (z lewej wolnego A*, a z prawej M). Aby to udowodnić, wystarczy zauważyć, że:

•    M_w._v{p,q) =-L <=> dla każdego stanu r € Q jedno z dwóch przejść jest niemożliwe: (po słowie w od p do r) oraz (po słowie v od r do q) 4=4- dla każdego stanu r € Q zachodzi M_w{p,r) =J_ lub M_v(r,q) =_L

•    M_w._v(p,q) = 1 <=>• istnieje stan r € Q taki, że są możliwe przejścia (po słowie w od p do r) oraz (po słowie v od r do q) a ponadto jedno z nich przechodzi przez stan akceptujący <=> istnieje stan r € Q taki, że zbiór {M_w(p,r), M_v(r,q)} jest równy {1} lub {0,1}

Lemat 6. Dla dowolnego automatu A i macierzy M € M z odpowiadającego A zbioru M, regularny jest język

L_m = {w 6 A* : M_w = M).

Dowód: Automat czyta słowo i oblicza macierz odpowiadającą już przeczytanemu prefiksowi. Ten automat jest zdefiniowany następująco:

•    stanami są wszystkie możliwe macierze z M

•    stanem początkowym jest macierz M₍

•    ze stanu N po przeczytaniu litery a automat przechodzi do stanu N-M_a (macierz M_a jest macierzą dla słowa jednoliterowego a)

Jeśli stanem akceptującym uczynimy M, automat akceptuje dokładnie słowa ze zbioru Lm- D

Teraz sformułujemy kluczowy lemat.

Lemat 7 (Kluczowy). Niech w e A“. Wówczas istnieją

•    macierze M, N takie, że M- N = M i N- N = N,

•    podział w = W0W1W2W3 ■. gdzie Wi € A⁺, takie, że

•    M_Wo = M,

•    M_Wi=N dlai = 1,2,3,....

A więc:

•    dla dowolnego i słowu wqW\W2 ■ ■ - w, odpowiada macierz M,

•    dla dowolnych i < j słowu w,Wi₊iWi+2 ■■ -Wj odpowiada macierz N.

Zanim przystąpimy do dowodu, przypomnimy twierdzenie Ramseya, które się przyda w dowodzie lematu.

15