7738996295

Dlaczego konstrukcja ta nie działa?

Jeśli automat B akceptuje słowo nieskończone w, to oczywiście w L.

Przeciwna implikacja jest jednak fałszywa. Weźmy język L = 0 nad alfabetem jednoliterowym {a} oraz następujący automat A:

Nie akceptuje on żadnego słowa, bo każdy bieg co najwyżej raz przechodzi przez stan akceptujący. Zatem językiem rozpoznawanym przez A jest 0.

Dla słowa a^u (jedynego nad tym alfabetem) zachodzi:

= {p}

Pi={p,q}

Pi = {p,q,r} = P₃ = P₄ = P₅ = ...

Wobec tego automat B też nie akceptuje słowa a“' (a powinien). Wynika to z faktu, że automat A ma dowolnie długie biegi dochodzące do stanu akceptującego q, ale nie dają się one połączyć w jeden bieg. Potrzebna jest więc inna, subtelniejsza konstrukcja automatu B.

Niech M oznacza zbiór macierzy A spełniających warunki:

•    A jest rozmiaru |Q| x \Q\,

•    wiersze i kolumny A są indeksowane przy pomocy stanów automatu A,

•    elementy A należą do zbioru {_L; 1; 0}.

Każdemu słowu skończonemu w € A* przyporządkowujemy pełną informację na jego temat jeśli chodzi o automat A. Ta informacja jest macierzą M_w € M zdefiniowaną następująco. W komórce (p,q) wartość macierzy M_w to

± jeśli nie istnieje bieg automatu A na słowie w, zaczynający się w stanie p, który kończy się w stanie q

1 jeśli istnieje bieg automatu A na słowie w, zaczynający się w stanie p, który kończy się w stanie q i po drodze przechodzi przez stan akceptujący

0 w przeciwnym przypadku, czyli da się przejść z p do q, ale nie da się przechodząc przez stan akceptujący Aby uzyskać informację na temat konkatenacji w- v (gdzie w,v € A*) wystarczy znać informację na temat w i v. Inaczej mówiąc, relacja równoważności utożsamiająca słowa o tej samej macierzy jest kongruencją ze względu na konkatenację.

Można to zapisać i uzasadnić definiując mnożenie macierzy w odpowiednim (przemiennym) półpierścieniu. Nośnikiem pólpierścienia jest (X; 1; 0}, operacją dodawania jest maksimum według porządku

-L<0<1

a mnożenie jest zdefiniowane następująco:

1- _L= 1- ±=±-1 = 0- 1=J_- 0 =_L 11=10=01=1 00 = 0

14