7738996293

Zgodnie z definicją, wyrażeń opatrzonych lo nie można zagnieżdżać, natomiast zapis A*aA^u + (■i4*a)“' jest jak najbardziej poprawny.

Definicja 2. Warunek Buchiego dla niedeterministycznych automatów rozpoznających słowa nieskończone brzmi:

Bieg automatu jest akceptujący, jeśli pewien stan akceptujący wystąpi w nim nieskończenie wiele razy.

Niedeterministyczne automaty z warunkiem Buchiego będziemy oznaczać przez NBA, z angielskiego nonde-terministic Biichi automaton.

Można zadać pytanie, czy deterministyczne automaty z warunkiem Buchiego (DBA), są równoważne NBA. Odpowiedź na to pytannie jest negatywna, zachodzi następująca zależność:

DBA $ NBA

Świadkiem powyższej nierówności jest język opisany wyrażeniem (a+6)*6“, inaczej mówiąc: słowa zawierające skończenie wiele a.

Fakt 4. Nie istnieje deterministyczny automat z warunkiem Buchiego rozpoznający język (a + 6)*6^U'. Dowód

Rozważmy dowolne słowo z tego języka, na przykład 6“’. Pokażemy, że dzięki drobnej modyfikacji zawsze będziemy w stanie oszukać nasz automat. Wczytując słowo, przy założeniu poprawności naszego automatu, na pewnej pozycji i musimy znaleźć się w stanie ackeptującym q 6 F. Jeśli w naszym słowie podmienimy literę i +1 na a, nie zmieni to stanu w pozycji i, z powodu determinizmu. Konstrukcję tę można powtórzyć, zakładając, że litera a nie występuje po pozycji i + 2. Słowo modyfikujemy w ten sposób, za każdym razem, gdy stwierdzimy, iż znaleźliśmy się w stanie akceptującym. □

2.2 Dowód twierdzenia Buchiego

((3) => (2)) W poniższej konstrukcji wygodnie korzystać z e-przejść. Łatwo pokazać, że e-przejścia można eliminować z NBA, tak samo jak w automatach na skończonych słowach.

Z powodu niedeterminizmu i e-przejść, języki rozpoznawane przez NBA są zamknięte na sumę. A więc wystarczy wskazać NBA dla języków postaci LK^W. Niech A będzie automatem (na słowach skończonych) rozpoznającym L, natomiast B niech będzie automatem (znów na słowach skończonych) rozpoznającym K.

Skonstruujemy teraz NBA dla języka LK^, nazwijmy go C. Stany automatu C to: stany A, stany B, oraz jeden dodatkowy stan r. Dodatkowy stan r będzie jedynym stanem akceptującym w automacie C. Automat z warunkiem Buchiego dla języka działa w następujący sposób:

1.    zaczyna w stanie początkowym automatu A.

2.    działa przez pewien czas zgodnie z automatem A

3.    w pewnym momencie (wybranym niedeterministycznie, gdy jest w stanie akceptującym automatu >4) przechodzi e-przejściem do stanu początkowego automatu B

4.    działa przez pewien czas zgodnie w automatem B

5.    w pewnym momencie (wybranym niedeterministycznie, gdy jest w stanie akceptującym automatu B) przechodzi e-przejściem do stanu r a następnie e-przejściem do stanu początkowego automatu B.

6.    GOTO 4

12