Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.1.WPROWADZENIE
chomieniazwracazawszetensamwynik.Niejestnatomiastmożliwe(wsposóbrozsądny)
zaimplementowaćtąmetodąnp.funkcjonalnościzamkakodowego.Wynikatozfaktu,
iżto,czyzameksięotworzyczynie,zależyodwpisanegokoduikolejnościjegowpisa-
nia.Pojawiasięwięctutajzależnośćmiędzykolejnościąoperacjiawyjściem.Tegotypu
zachowanianajlepiejjestimplementować,korzystajączautomatustanów.
1.1.1.Automatystanów
Automatstanówjesttomatematycznymodelobliczeń,którybazujenatablicyprzejść
międzyposzczególnymistanamipodwpływemokreślonychwarunków.Wtejtablicyzapi-
sanemogąbyćrównieżwartościwyjśćrozważanegoautomatu.Ogólnypodziałwyróżnia
automatyniedeterministyczneideterministyczne–będziemyzajmowaćsięwyłącznietymi
drugimi.Oznaczato,żeprzejściezobecnegodokolejnegostanujestprecyzyjnieokreślone
izawszejestjednoznaczne.Wautomacieniedeterministycznymsekwencjaprzejśćzależy
odcałościdanych,podczasgdywautomaciedeterministycznymwyłącznieoddanych
przeszłychiobecnych.Mimoiżtematjestniezwykleciekawy,wtymskrypcieomówione
zostanąwyłącznieautomatystanówdeterministyczne.
Rozważaniadotyczącekonkretnychautomatówwartopoprzedzićjeszczenotacjąigra-
ficznąreprezentacjąautomatówstanów.Automatytereprezentowanesąjakografyskie-
rowane(rys.1.1),gdziewęzełreprezentujepojedynczystan(wśrodkuwęzłazapisana
jestnazwalubsymbolstanu),natomiastkrawędźreprezentujemożliweprzejściemiędzy
stanami(nakrawędziznajdowaćsiępowinnanazwawarunkuprzejścialubsamwarunek
zapisanyjakowyrażenielogiczne).Dlaprzykładuwarunektakimógłbyoznaczać„czujnik
obecnościwykryłdetal”.Wartomiećnauwadze,żekrawędziesąskierowane,acozatym
idzie,przejściasąjednokierunkowe.Należyzauważyć,żeniniejszakonwencjarysowania
niejestcałkowiciezgodnazprzyjętymstandardem,gdyżzazwyczajpodwójnaliniare-
prezentujestannazywanystanemakceptującymwmaszyniestanów,podczasgdytutaj
wykorzystanajestonadooznaczeniastanupoczątkowegoautomatuzamiaststandardowej
strzałkiprowadzącejdopierwszegostanu,aleniemającejstanuźródłowego.Zapistenjest
łatwiejszywodbiorze–wprzypadkuwieluprzejśćmiędzystanami(częstoprzecinających
się)trudniejjestznaleźćtęjednąstrzałkębezźródłaniżokrągopodwójnejlinii.
Wzależnościodzastosowanegoautomatuoboknazwystanu(awszczególnościpod)
lubobokwarunkuprzejścia(częstotakżepod)znajdowaćsięmożeinformacjaotym,
jakimabyćzbiórsygnałówwyjściowych.Zazwyczajjednakzapisujesiętamjedyniete
sygnały,którychwartośćsięzmienia.Narysunku1.1wyjściasąoznaczonesymbolami,
gdziewpraktycekażdysymbolzostałbypóźniejosobnoopisany.Stanywprostychprojek-
tachzazwyczajnumerujesiękolejnymiliczbaminaturalnymi,natomiastzamiastsymboli
warunkówprzejśćistanówwyjśćwpisujesiękonkretnesygnaływejściowe(lubichkombi-
nacjęlogiczną)orazwartościzmieniającychsięsygnałówwyjściowych.Podkreślićnależy,
żeprzedstawionenarysunku1.1przykładoweautomatyniemusząbyćsobierównoważ-
ne,tj.nieopisujątegosamegozachowania,stądteżróżnenazwykombinacjisygnałów
wyjściowych.
1.1.2.AutomatMoore’a
AutomatstanówMoore’a[Moo56]jesttoautomatdeterministyczny,wktórymwar-
tościsygnałówwyjściowychzależąwyłącznieodstanu,wjakimautomatsięznajduje.
11
