Mașini finite

Aparatul de stat (denumit în continuare SC) - abstract dispozitivul de calcul cu o cantitate fixă ​​și finită de memorie care se citește la intrarea lanțului (secvența de simboluri ale unui alfabet), precum și de ieșire spune că ele aparțin unei multitudini de care este construit pentru a recunoaște.

Principiul de funcționare a mașinilor de stat de diferite niveluri este utilizat pe scară largă în dispozitive de calcul, atât în ​​hardware și software în niveluri: compilatoare, programe de traducători, diverse codificatoare, software-ul antivirus, etc. În principiu, funcționarea oricărui program poate fi prezentat ca activitatea unui lanț de mașini de stat de complexitate diferite. Luați în considerare construirea unui simplu CA - recognizere. Următorii parametri trebuie să fie determinată în timpul construcției unei astfel de mașini de stare finită:

a) un automat finit de intrare alfabet V (set finit de simboluri de intrare care va recunoaște CA);

b) un set finit de state S;

c) starea inițială a AC - s0 (stare din care nava începe procesarea unui nou lanț);

d) o pluralitate de stări de acceptare - SDOP (subgrupul de stări, care este comparat cu elementele CS atins starea după aderarea la „capătul lanțului de“ simbol);

e) tabelul de tranziție (tabelul de control), care este o pereche de „starea curentă - simbolul de intrare“ atribuie o nouă stare a navei spațiale din setul S de state).

1 set de simboluri de intrare includ în mod necesar un simbol special „capăt al lanțului“, care spune nava spatiala care a ajuns la stat pentru a compara SI cu elementele SDOP si daca si Î SDOP. sări lanțul; în caz contrar, lanțul este respins. În textul acestui personaj va arata - |.

SC începe întotdeauna de la starea s0 inițială. Simboluri de caractere de recunoscut prin șir de caractere primit de la prima și a schimbat nava spatiala de stat, în conformitate cu tabelul de salt. La primirea „sfârșitul lanțului de“ simbol de stat realizată în mod automat este fix și în comparație cu setul de stări care acceptă. Pe baza acestei comparații, lanțul este permis sau refuzat. De fapt, nava spatiala acționează ca un filtru care trece „dreptul“ a lanțului. O altă interpretare a SC - algoritm compact pentru recunoașterea regulate, inclusiv seturi infinite, care este construirea unui programator pentru a codifica începutul (punerea în aplicare a algoritmului într-un anumit limbaj de programare).

nave spațiale de construcții să recunoască un set prestabilit de șiruri - un proces creativ și controversat. Teoretic, să recunoască același set de siruri de caractere, puteți construi un număr infinit de sateliți. Principiul de mai sus nu se aplică recunoașterii orice set regulate. Este eficient în următoarele cazuri:

- lanțuri de recunoscut cuprind anumite combinații de simboluri în începutul, sfârșitul, sau (ii) mijlocul lanțului;

- lanțuri de recunoscut conțin un număr limitat de repetiții ale anumitor caractere sau combinații ale acestora (nu mai mult de n; exact n în care n este cel puțin n = 1,2,3.);

- lanțuri de recunoscut conțin o interdicție privind anumite combinații de simboluri la începutul sau la sfârșitul (e) în lanț;

- lanțuri recunoscute conțin combinații de limitările de mai sus. (Pentru mai multe detalii - vezi DM curs.).