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ē \boldsymbol{A=(\Sigma, S, s_0, \delta, F)}, 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: \delta: S \times \Sigma \rightarrow S.
  • 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

Lifta darbības modelis
Palielināt
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: T(oD,c)\rightarrow cD
T(cD,o)\rightarrow oD
T(cD,U)\rightarrow cU
T(cU,D)\rightarrow cD
T(cU,o)\rightarrow oU
T(oU,c)\rightarrow cU
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ā.