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:
Mw.v = MW-MV
Inaczej mówiąc, przyporządkowanie w i-» Mw jest homormofizmem monoidów (z lewej wolnego A*, a z prawej M). Aby to udowodnić, wystarczy zauważyć, że:
• Mw.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 Mw{p,r) =J_ lub Mv(r,q) =_L
• Mw.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 {Mw(p,r), Mv(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
Lm = {w 6 A* : Mw = 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-Ma (macierz Ma 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
• MWo = M,
• MWi=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
Wyszukiwarka
Podobne podstrony:
Politechnika Wrocławska • Mnożenie macierzy jest tączne: A(BC)=(AB)C •
IMAG0755 (2) d2 ^ećfśpa gwintu [mm] Pozorny kąt tarcia jest zdefiniowany następują
mnożenia macierzy jest pierścieniem. Pierścień ten posiada element neutralny mnożenia / ( a więc jes
6 (2096) 2. MACIERZE I WYZNACZNIKI 1. Zdefiniuj następujące pojęcia: macierz rzeczywista (zespolona)
106 107 106 c> uniom 1 na wyjściu. S jest sekwencją o następująoyoh wtaanośoUoh
> kolumn i wierszy, a kolejność mnożenia macierzy jest dowolna >
106 107 106 O tlałem 1 na wyjściu. S jest sekwencją o następująoyoh »)>wit»Uohi po O pojawia się
86122 yyy7 Zofia Sokół Już następnego dnia po wprowadzeniu stanu wojennego -14 grudnia 1981 r. w Po
dziedziny atrybutu a. Jest zdefiniowana w następujący sposób: Split(Sa) = Zl S’ gdzie Sj jest
Podstawową metodą pacy na lekcjach języka polskiego jest praca z tekstem literackim. Po wprowadzeniu
Image144 stany: A = 1, B — C — ... / = 0. Następnie informacja jest wpisywana do rejestru. Po ośmiu
karta pracy miesięcy Jest dwanaście miesięcy i zawsze następują po sobie w tej samej kolejności.
więcej podobnych podstron