Maszyny stanów skończonych w Pythonie
Wprowadzenie
Maszyny stanów skończonych (ang. Finite State Machine) to abstrakcyjne, matematyczne opisy zachowań systemów dynamicznych. Brzmi groźnie, prawda?
Okazuje się, że nie jest to takie straszne w praktyce. FSM są podwaliną np. wyrażeń regularnych w Perlu (i innych językach), odpowiadają za nawiązywanie połączeń TCP, znajdują się w grach komputerowych; w zasadzie są wszędzie. (Gdy dodać do nich nieskończoną pamięć, dostajemy maszynę Turinga, czyli prawie zwykły komputer.)
Zacznijmy od przykładu: spróbujmy znaleźć jakieś słowo w zdaniu. Powiedzmy, że szukamy słowa "kot", a zdanie to "Ala ma kota." W Pythonie ten problem łatwo rozwiązać bez pomocy matematyki dyskretnej, w taki sposób:
>>> "kot" in "Ala ma kota." True >>>
Niestety, z punktu widzenia tematu artykułu, wartość dydaktyczna tego eleganckiego rozwiązania jest żadna. Zastanówmy się, co robi ta prosta linijka kodu:
"kot" in "Ala ma kota."
Pierwszym pomysłem mógłby być taki algorytm:
- Zacznij od pierwszej pozycji w zdaniu.
- Jeśli na obecnej pozycji jest słowo "kot", to zakończ i zwróć True.
- Przejdź na następną pozycję, zwróć False jeśli koniec zdania; w przeciwnym przypadku przejdź do kroku 2.
Takie podejście, choć działające, jest nieoptymalne - każdy znak w zdaniu porównujemy niepotrzebnie kilka razy. Unikniemy tego tworząc automat stanów.
Automat stanów szukający słowa "kot".
Implementacja
Automaty można implementować na kilka sposobów; zacznijmy od najprostszego, czyli serii porównań.
def automat1(lancuch):
stan = 'start'
for znak in lancuch:
if stan == 'start':
if znak == 'k':
stan = 'k'
elif stan == 'k':
if znak == 'o':
stan = 'ko'
else:
stan = 'start'
elif stan == 'ko':
if znak == 't':
return True
elif znak == 'k':
stan = 'k'
else:
stan = 'start'
return False
Efekt działania (z drobną modyfikacją wypisującą stan i znak):
>>> automat1("Ala ma kota.")
A start
l start
a start
start
m start
a start
start
k start
o k
t ko
True
>>>
Nie jest to najszczęśliwsza implementacja - nie jest zbyt wydajna, a czytelność pozostawia wiele do życzenia. Stworzenie maszyny z większą ilością stanów w taki sposób ręcznie mija się z celem.
Drugi sposób to wykorzystanie struktur danych udostępnianych przez język. Użyjemy słownika (dicta w slangu Pythona) do przechowania tablicy przejść stanów.
tablica = {
'start': {
'k': 'k',
None: 'start' },
'k': {
'o': 'ko',
None: 'start' },
'ko': {
't': 'kot',
'k': 'k',
None: 'start' },
'kot': {
None: 'kot' }
}
Jak widać, użyliśmy None w znaczeniu "znak inny niż zdefiniowane." A oto gotowa funkcja realizująca nasz automat:
def automat2(lancuch):
tablica = {
'start': {
'k': 'k',
None: 'start' },
'k': {
'o': 'ko',
None: 'start' },
'ko': {
't': 'kot',
'k': 'k',
None: 'start' },
'kot': {
None: 'kot' },
}
stan = 'start'
for znak in lancuch:
if znak in tablica[stan]:
stan = tablica[stan][znak]
else:
stan = tablica[stan][None]
if stan == 'kot':
return True
return False
Efekt (ponownie z modyfikacją):
>>> automat2("Ala ma kota.")
A start
l start
a start
start
m start
a start
start
k start
o k
t ko
True
>>>
Bez zmian, czyli działa.
Przejście na styl deklaratywny (czyli opis maszyny za pomocą danych, a nie kodu) zdecydowanie upraszcza zapis i poprawia czytelność. Do tego można łatwo zgeneralizować naszą funkcję:
def automat2_uogolniony(lancuch, tablica, start, koniec):
stan = start
for znak in lancuch:
if znak in tablica[stan]:
stan = tablica[stan][znak]
else:
stan = tablica[stan][None]
if stan == koniec:
return True
return False
Dzięki temu wystarczy napisać odpowiednią tabelę przejść stanów, a funkcja załatwi resztę. Warto zauważyć, że dzięki dynamicznemu charakterowi Pythona ta funkcja nie jest ograniczona do łańcuchów znaków - może to być równie dobrze lista dowolnych obiektów.
Tablica przejść stanów jest dobrym i dość ogólnym sposobem, ale co, jeśli potrzebujemy wykonać jakąś akcję związaną ze stanami lub przejściami stanów? Najładniej byłoby zaprząc do tego zadania klasy z odpowiednimi metodami. A skoro będziemy mieli klasy, to można znowu wykorzystać dynamiczność Pythona w intrygujący sposób.
Mianowicie, w Pythonie można, podobnie jak w Javie i C#, w czasie wykonania poznać informacje o typach obiektów - ale nie tylko. Można także typ obiektu zmienić. Wygląda to tak:
>>> class A(object): ... def m(self): print 'jestem A.m' ... >>> class B(object): ... def f(self): print 'a ja jestem B.f' ... >>> o = A() >>> type(o) <class '__main__.A'> >>> o.m() jestem A.m >>> o.__class__ = B >>> type(o) <class '__main__.B'> >>> o.f() a ja jestem B.f
Po tej operacji metoda m() nie jest już dostępna:
>>> o.m() Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: 'B' object has no attribute 'm' >>>
Oczywiście, gdyby w klasie B zamiast metody "f" utworzyć metodę "m", to o.m() zadziałałoby po podmianie typu. Wykorzystamy właśnie tę własność.
class Stan(object):
def przejdz_do(self, stan):
self.przed_przejsciem(stan)
klasa = self.__class__
self.__class__ = stan
self.po_przejsciu(klasa)
def przed_przejsciem(self, nowy_stan):
"""Tu mozna zdefiniowac operacje do wykonania przed przejsciem w nowy stan."""
pass
def po_przejsciu(self, stary_stan):
"""Tu mozna zdefiniowac operacje do wykonania po przejsciu w nowy stan ze starego."""
pass
def przejscie(self, wejscie):
raise NotImplementedError("przejscie niezdefiniowane dla stanu %s" % self.__class__)
def akceptacja(self):
"""Podmnien te metode, aby zwracala True, jesli mozna zakonczyc automat."""
return False
Teraz zdefiniujemy stany i przejścia:
class Start(Stan):
def przejscie(self, wejscie):
if wejscie == 'k':
self.przejdz_do(K)
class K(Stan):
def przejscie(self, wejscie):
if wejscie == 'o':
self.przejdz_do(KO)
else:
self.przejdz_do(Start)
class KO(Stan):
def przejscie(self, wejscie):
if wejscie == 't':
self.przejdz_do(KOT)
elif wejscie == 'k':
self.przejdz_do(K)
else:
self.przejdz_do(Start)
class KOT(Stan):
def przejscie(self, wejscie):
pass
def akceptacja(self):
return True
I na koniec funkcja wykonująca automat na łańcuchu danych:
def automat3(lancuch):
stan = Start()
for znak in lancuch:
stan.przejscie(znak)
if stan.akceptacja():
return True
return False
Efekt (tym razem modyfikcja polega na wypisaniu znaku i nazwy klasy):
>>> automat3("Ala ma kota.")
A Start
l Start
a Start
Start
m Start
a Start
Start
k Start
o K
t KO
True
>>>
Jako ćwiczenie dla czytelnika pozostawię połączenie podejścia drugiego z trzecim (tzn. połączenia dynamicznego zmieniania typu z tablicą przejść stanów).
Podejście z obiektami zmieniającymi typ jest tym lepsze, im bardziej skomplikowana jest implementowana maszyna stanów i środowisko, w którym przyjdzie jej pracować. Przykład z szukaniem wyrazu nie oddaje w pełni możliwości, jakie daje ta strategia - można sobie wyobrazić np. prostą sztuczną inteligencję do jakiejś gry, która oprócz zmieniania stanu potrzebuje wykonywać dodatkowe operacje i przechowywać informacje nie związane bezpośrednio z automatem skończonym.
Aby dodawać komentarze musisz być zalogowany!