4130649326

4130649326



Inaczej mówiąc (q, w, s) G S* jeżeli istnieje bieg automatu A na słowie w rozpoczynający się od stanu q i kończący się w stanie s. Zastosowaliśmy tu pojęcie biegu w nieścisły sposób ponieważ zgodnie z definicją bieg musi się rozpoczynać w stanie początkowym, ale zakładamy, że taki zabieg jest zrozumiały i będziemy go stosować również w dalszej części pracy.

Rozmiarem automatu skończonego będziemy nazywać liczbę jego stanów. Przyjmiemy oznaczenie |.A| na rozmiar automatu A.

Definicja 1.1.2 Deterministyczny automat skończony na słowach (DFAz ang. De-terministic Finite Automaton) jest to taki automat skończony, którego relacja przejścia jest funkcją 5 : Q xE —» Q, iw którym jest tylko jeden stan początkowy. Takie automaty będziemy czasem zapisywać w postaci (Q, S, 5, qo, F) zamiast (Q, S, 5, {ęo}, F).

Ważną cechą automatu deterministycznego jest fakt, że na każdym słowie ma najwyżej jeden bieg. Automat akceptuje jeżeli ten jedyny bieg jest akceptujący. Warto zauważyć dodatkowo, że taki bieg możemy konstruować od lewej do prawej nie podejmując żadnych decyzji. Dzięki temu, że relacja przejścia jest funkcją, w żadnym miejscu nie mamy wyboru i jeżeli na pewnym słowie istnieje poprawny bieg to nie może się zdarzyć, że konstruując bieg na tym słowie napotkamy na sytuację, że nie możemy przedłużyć biegu częściowego do pełnego biegu. Uwaga ta wydaje się oczywista ale zyska ona na istotności w kontekście rozważań nad automatami działającymi na drzewach.

Przypomnimy tu jeszcze dobrze znany ale bardzo ważny fakt.

Fakt 1.1.3 (Determinizacja) Jeżeli język słów skończonych jest rozpoznawany przez pewien automat skończony to jest on również rozpoznawany przez pewien deterministyczny automat skończony.

Automat deterministyczny, o którym mowa w powyższym fakcie można skonstruować z automatu niedeterministycznego rozpoznającego dany język. Wystarczy jako stany wziąć podzbiory zbioru stanów wyjściowego automatu. Tę konstrukcję nazywamy konstrukcją podzbiorów1. Szczegóły dowodu powyższego twierdzenia można znaleźć na przykład w książce Hopcrofta i Ullmana2.

1.2. Drzewa nieurangowane

Zdefiniujemy teraz centralne pojęcie tej pracy.

Definicja 1.2.1 Drzewo nieurangowane nad skończonym alfabetem S jest to funkcja t : Dom(t) —> E, której dziedzina Dom(t) jest skończonym podzbiorem N* takim, że dla a € N tinSN* jeżeli waG Dom(t) to:

•    w ę. Dom(t) (zamkniętość na prefiksy),

•    wbE Dom(t) dla każdego b < a.

Elementy Dom(t) nazywamy węzłami (lub wierzchołkami), a wartości funkcji tetykietami węzłów. Jeżeli aG N iwGN* to wa jest dzieckiem (lub synem) w, a w ojcem wa. Węzeł e nazywamy korzeniem, a węzły bez dzieciliśćmi drzewa.

1

'ang. subset construction

2

zob. [HU] twierdzenie 2.1



Wyszukiwarka

Podobne podstrony:
IMG) BLOK 1 > ► a) Bieg indywidualny na czas rozpoczyna się o godzinie osiemnastej. Na rysunku po
Przyrost łodygi na grubość rozpoczyna się od odróżnicowania się w miękiszu promieni
aktualnościRekrutacja 2012/2013 We wrześniu zakończyła się rekrutacja na studia rozpoczynające się o
Obraz10 do abstrakcji i od abstrakcji do konkretu. Inaczej mówiąc, poglądowoję te ^ poszukiwaniem t
LUDZIE Jako twórca chyba mam prawo oceniać tylko samego siebie. Jeżeli ten mój osąd na samym sobie s
(konformista), jeżeli swoje poglądy zmienia na rozkaz, sprzeniewierza się swoim obowiązkom, tak
img14 JAGUAR (Panthera one a) Ten wielki kot żyje na terenach rozciągających się od południowej częś
b. Spis treści Powinien zawierać wykaz wszystkich części pracy z podaniem strony, na której rozpoczy
P1020809 (2) obrażni skończona I na chwilę uwalniam się od mdlącej męki pożądania. Czy to Yeats? „Po
RECENZJE 231 recenzowanej pracy rozpoczyna się od spojrzenia na zmiany w metodach gospodarowania. Cz
w044 Ratownictwo medyczne w wypadkach masowych Mycie rozpoczyna się od głowy i włosów, a kończy na s
skanuj0007 (56) w jej pyszczku - ale wskazuje na nic więcej niż preferencję do uwolnienia się od sta
656 (2) Rozdział 5. Dawność 121 ■r ogólnej reguły bieg przedawnienia rozpoczyna się od dnia wymagał-

więcej podobnych podstron