Galīgais automāts
Vikipēdijas raksts
Galīgais automāts - diskrētas sistēmas matemātiskas abstrakcijas modelis, kas apraksta sistēmas izmaiņas diskrētos laika momentos atkarībā no ieejas datiem un iepriekšējā stāvokļa. Par galīgu sauc tādēļ, ka ieejas, izejas un stāvokļu kopas var būt tikai galīgas. Galīgais automāts ir viens no abstraktā automāta gadījumiem.
Pēc tā, vai automāts vienā laika momentā var atrasties vienā vai vairākos stāvokļos, izšķir determinētos galīgos automātus un nedeterminētos galīgos automātus.
Satura rādītājs |
[izmainīt šo sadaļu] Matemātiskais modelis
Gala automātu parasti apzīmē , kur:
- Σ - ieejas alfabēts (galīga ne tukša simbolu kopa).
- S - galīga ne tukša stāvokļu kopa.
- s0 - sākuma stāvoklis, kāds elements vai elementu apakškopa no S.
- δ - stāvokļa pārejas funkcija:
.
- F - beigu stāvokļa kopa (iespējams, tukša), S apakškopa.
[izmainīt šo sadaļu] Piemēri
[izmainīt šo sadaļu] Vienkāršota lifta darbības modelis
Ir lifts, kurš var izpildīt 4 komandas:
o - atvērt durvis,
c - aizvērt durvis,
U - uzbraukt otrajā stāvā,
D - nobraukt uz pirmo stāvu.
Lifts var atrasties 4 stāvokļos (oD - pirmajā stāvā, durvis atvērtas; cD - pirmajā stāvā, durvis aizvērtas; cU - otrajā stāvā, durvis aizvērtas; oU - otrajā stāvā, durvis atvērtas). Sākotnēji tas atrodas stāvoklī oD. Lifts var izpildīt programmu cUo - aizvērt durvis, uzbraukt 2. stāvā, atvērt durvis. Piem., programma oUc nebūs pareiza - nevar ar atvērtām durvīm braukt augšā.
Ja stāvokļu kopa ir S = {oD,cD,cU,oU}, sākumstāvoklis s0 = oD, beigu stāvoklisun pārejas funkcijas ir definētas:
Ja programma cUocDo būs ieejas alfabēts Σ = {c,U,o,c,D,o}, tad galīgais automāts korekti darbosies. Programma cocDo nebūs korekta, jo stāvoklī cD nav pieļaujama pāreja D.
[izmainīt šo sadaļu] Pielietojums
Galīgos automātus izmanto ciparu elektronikā, programmējamās loģiskās ierīcēs.
Plašs pielietojums ir programmatūrā, piemēram, sintaksisko analizatoru, regulāro izteiksmju realizācijā.