Tilakone: teoria ja toteutus. Äärelliset koneet, kuinka ohjelmoida ilman jumiutumista Äärillinen kone nukkeille

Äärillisten automaattien teoria

Automaattiteoria on kääntäjien rakentamisen teorian taustalla. Tilakone on yksi peruskäsitteistä. Automaatti ei tarkoita tosielämän teknistä laitetta, vaikka sellainenkin voidaan rakentaa, vaan jotain matemaattista mallia, jonka ominaisuuksia ja käyttäytymistä voidaan jäljitellä tietokoneella olevan ohjelman avulla. Äärillinen automaatti on automaatiteorian malleista yksinkertaisin ja toimii pääsääntöisesti kaikkien muiden automaatiotyyppien ohjauslaitteena. Tilakoneella on useita ominaisuuksia:

· Tilakone pystyy ratkaisemaan useita helppoja käännöstehtäviä. Leksikaalinen lohko rakentuu lähes aina tilakoneen ympärille.

Äärillisen tilan koneen toiminnalle on ominaista suuri nopeus.

· Tilakonesimulaatio vaatii kiinteän määrän muistia, mikä yksinkertaistaa muistin hallintaa.

· On olemassa useita lauseita ja algoritmeja, joiden avulla voit suunnitella ja yksinkertaistaa äärellisiä automaatteja.

Kirjallisuudessa on useita erinomaisia tilakoneen määritelmiä. Niille on kuitenkin yhteistä, että tilakone mallintaa kiinteällä muistimäärällä varustetun laskentalaitteen, joka lukee johonkin syöttöjoukkoon kuuluvia syötesymbolien sarjoja. Perusteelliset erot määritelmissä liittyvät siihen, mitä automaatti tekee lähdössä. Automaattin lähtö voi olla osoitus siitä, onko annettu syötemerkkijono "sallittu". "Admissible" on hyvin muotoiltu tai syntaktisesti oikea merkkijono. Esimerkiksi merkkijonoa, jonka pitäisi edustaa numeerista vakiota, pidetään virheellisenä, jos se sisältää kaksi desimaalipistettä.

Määritelmä: Tilakone on muodollinen järjestelmä, joka määritellään käyttämällä seuraavia objekteja:

rajallinen joukko syöttösymboleja;

äärellinen joukko tiloja;

· siirtymäfunktio, joka yhdistää jokaisen parin (nykyinen tila, tulosymboli) uuteen tilaan;

alkutila;

· osajoukko tiloja, jotka on valittu hyväksyttäviksi tai lopullisiksi.

Esimerkki. Analysoidaan ohjaimen toimintaa, joka tarkistaa parillisen tai parittoman määrän ykkösiä mielivaltaisessa nollien ja ykkösten ketjussa. Oletetaan, että vastaavan äärellisen automaatin on "sallittava" kaikki merkkijonot, jotka sisältävät parittoman määrän ykkösiä, ja "hylättävä" merkkijonot, joissa on parillinen määrä niitä. Kutsutaan tätä automaattia "pariteettisäätimeksi". Uskomme, että muita symboleja kuin 0 ja 1 ei voida syöttää automaatin tuloon. Ohjaimen syöteaakkoset ovat siis joukko (0, 1) . Oletetaan, että tietyllä ajanhetkellä äärellinen automaatti käsittelee vain yhtä syötesymbolia ja tallentaa tiedon syöttöketjun aikaisemmista symboleista käyttämällä äärellistä tilajoukkoa. Tilajoukkona tarkastelemme joukkoa ( parillinen, pariton ), joista yksi tulee valita alkutilaksi. Olkoon se tila (parillinen), koska ensimmäisessä vaiheessa luettujen yksiköiden lukumäärä on nolla ja nolla on parillinen luku. Seuraavaa syöttösymbolia luettaessa automaatin tila joko muuttuu tai pysyy samana ja sen uusi tila riippuu syöttösymbolista ja sen hetkisestä tilasta. Tätä tilanmuutosta kutsutaan siirtymäksi.

Automaattia voidaan kuvata matemaattisesti siirtymäfunktiolla, joka on muotoa d(Stack, x) = Snew. Muuten se voidaan kirjoittaa näin:

d(parillinen, 0) = parillinen d (parillinen, 1) = pariton.

d(pariton, 0) = pariton. d (pariton, 1) = parillinen

Ohjaimella on yksi hyväksyntätila, ODD, ja EVEN on "kielto"-tila. Kuvataanpa automaatin siirtymäjärjestystä, kun ketju 1101 syötetään sen sisääntuloon.

EVEN ® ODD ® EVEN® EVEN® ODD

Tällaisen automaatin siirtymätaulukon muoto on:


jopa	jopa	outo
outo	outo	jopa

Määritelmä. Tilakone on muodollinen järjestelmä

S = (A, Q, d, l, V),

joiden objektit ovat seuraavat:

* A - rajallinen joukko syöttösymboleja (set

terminaalit);

* Q - äärellinen joukko automaatin sisäisiä tiloja

(monia ei-päätteitä);

* V - tulossymbolien rajallinen joukko (lähtöaakkoset);

* d - siirtymäfunktio, jolle on tunnusomaista A´Q® Q;

* l on lähtötoiminto, joka määrittää näkymän näytön.

Tänään puhumme konekivääreistä, mutta emme suinkaan niistä, joita pidetään Venäjän armeijan sotilaiden käsissä. Puhumme niin mielenkiintoisesta mikro-ohjainten ohjelmointityylistä kuin automaattinen ohjelmointi. Tarkemmin sanottuna tämä ei ole edes ohjelmointityyli, vaan koko konsepti, jonka ansiosta mikrokontrolleriohjelmoija voi tehdä elämästään paljon helpompaa. Tämän ansiosta monet ohjelmoijalle esitetyt tehtävät ratkeavat paljon helpommin ja yksinkertaisemmin, mikä vapauttaa ohjelmoijan päänsärystä. Muuten, automaattista ohjelmointia kutsutaan usein SWITCH-tekniikka.

Haluan huomauttaa, että sysäys tämän postauksen kirjoittamiseen oli SWITCH-teknologiaa käsittelevä artikkelisarja Vladimir Tatarchevski. Artikkelisarjan nimi on "SWITCH-tekniikan soveltaminen mikro-ohjainsovellusohjelmistojen kehittämiseen". Joten tässä artikkelissa yritän suurimmaksi osaksi antaa esimerkin toimivasta koodista ja sen kuvauksesta.

Muuten, olen suunnitellut ohjelmointia koskevia artikkeleita, joissa tarkastelen yksityiskohtaisesti ABP-mikrokontrollerien ohjelmointitekniikoita, Älä missaa…. No mennään!

Ohjelma suorittaa peräkkäin ohjelmoijan määrittämät komennot. Tavanomaiselle tietokoneohjelmalle on täysin normaalia, kun ohjelma on valmis ja lopettanut suorituksensa samalla kun se näyttää työnsä tulokset näytöllä.

Mikrokontrolleriohjelma ei voi yksinkertaisesti lopettaa sen suorittamista. Kuvittele, että olet käynnistänyt soittimen tai nauhurin. Olet painanut virtapainiketta, valinnut haluamasi kappaleen ja nauttinut musiikista. Kuitenkin, kun musiikki lopetti tärykalvon heilumisen, soitin jäätyy eikä reagoi millään tavalla painikkeiden painamiseen, eikä varsinkaan tamburiinilla tanssimiseen.

Ja mikä tämä on? Kaikki on hyvin - soittimesi syvyyksissä oleva ohjain on juuri suorittanut ohjelmansa. Täällä voit nähdä, kuinka epämiellyttäväksi se osoittautuu.

Joten tästä päättelemme, että mikro-ohjaimen ohjelman ei yksinkertaisesti pitäisi pysähtyä. Pohjimmiltaan sen pitäisi olla ääretön silmukka - vain tässä tapauksessa soittimemme toimisi oikein. Seuraavaksi näytän sinulle, mitkä ovat mikro-ohjainten ohjelmakoodit, nämä eivät ole edes malleja, vaan joitain ohjelmointityylejä.

Ohjelmointityylit.

"Ohjelmointityylit" kuulostaa jotenkin käsittämättömältä, mutta no niin. Mitä haluan sanoa tällä? Kuvittele, että ihminen ei ole koskaan aiemmin ohjelmoinut, eli yleisesti ottaen täydellinen nukke.

Tämä henkilö on lukenut monia ohjelmointikirjoja, oppinut kaikki kielen perusrakenteet.Hän keräsi tietoa pala kerrallaan, koska nyt tiedon saanti on rajoittamaton. Kaikki tämä on hyvää, mutta miltä hänen ensimmäiset ohjelmansa näyttävät? Minusta näyttää, että hän ei filosofoi, vaan seuraa polkua yksinkertaisesta monimutkaiseen.

Nämä tyylit ovat siis askeleita, jotka johtavat yksinkertaiselta tasolta monimutkaisemmalle, mutta samalla tehokkaammin.

Aluksi en ajatellut mitään ohjelman suunnitteluominaisuuksia. Muodosin juuri ohjelman logiikan - piirsin vuokaavion ja kirjoitin koodin. Siitä, mitä jatkuvasti törmäsin haravaan. Mutta tämä oli ensimmäinen kerta, kun en käynyt höyrysaunassa ja käytin "yksinkertaista silmukka" -tyyliä, sitten aloin käyttää keskeytyksiä, sitten tuli automaatteja ja lähdettiin...

1. Yksinkertainen silmukka. Tässä tapauksessa ohjelma silmukoi ilman mitään monimutkaisuutta, ja tällä on hyvät ja huonot puolensa. Plus vain lähestymistavan yksinkertaisuudessa, sinun ei tarvitse keksiä ovelia malleja, kirjoitat kuten ajattelet (vähitellen kaivaa omaa hautaasi).

Void main(void) ( iniciaali_AL(); //oheislaitteen alustus while(1) ( Leds_BLINK(); //LED-vilkun toiminto signal_on(); //signaalin signaalin_off(); // signaalin sammutustoiminto l=button( ); // painikkeiden painamisesta vastaava muuttuja switch(l) // Muuttujan arvosta riippuen suoritetaan yksi tai toinen toiminto ( tapaus 1: ( Deistvie1 (); / / Funktion sijasta voi olla ehdollinen operaattori Deistvie2 (); // tai useat haarat vaihtavat kirjainkokoa Deistvie3(); Deistvie4(); Deistvie5(); ); tapaus 2: ( Deistvie6(); Deistvie7(); Deistvie8(); Deistvie9(); Deistvie10(); ); . . . . . . . . . . ) ) )

Ohjelman työpiste liikkuu järjestyksessä. Tässä tapauksessa kaikki toiminnot, ehdot ja syklit suoritetaan peräkkäin. Koodi alkaa hidastua, sinun on lisättävä paljon lisäehtoja, mikä vaikeuttaa havaintoa.

Kaikki tämä hämmentää ohjelmaa suuresti tehden koodista ehtojen sotkun. Seurauksena on, että tätä koodia ei voi lisätä tai poistaa, se muuttuu kuin monoliittinen kappale. Tietysti, kun volyymi ei ole suuri, koodia voidaan muokata, mutta mitä pidemmälle, sitä vaikeampaa.

Tällä lähestymistavalla kirjoitin useita ohjelmia, ne eivät olleet suuria ja melko toimivia, mutta näkyvyys jätti paljon toivomisen varaa. Uuden ehdon lisäämiseksi jouduin lapioimaan koko koodin, koska kaikki oli sidottu. Tämä aiheutti monia virheitä ja päänsärkyä. Kääntäjä vannoi niin pian kuin mahdollista, tällaisen ohjelman virheenkorjaus muuttui helvetiksi.

2. Cycle + keskeytykset.

Voit osittain ratkaista äärettömän jarrutusjakson keskeytyksiä käyttämällä. Keskeytykset auttavat irtautumaan noidankehästä, auttavat olemaan huomaamatta tärkeitä tapahtumia, lisäävät lisätoimintoja (keskeytykset ajastimista, ulkoiset keskeytykset).

Oletetaan, että voit keskeyttää painikkeiden käsittelyn tai tärkeän tapahtuman seurannan keskeytyksen yhteydessä. Tämän seurauksena ohjelmasta tulee visuaalisempi, mutta ei vähemmän hämmentävä.

Valitettavasti keskeytys ei pelasta sinua sotkusta, johon ohjelma muuttuu. Ei ole mahdollista jakaa osiin sitä, mikä on yksi kokonaisuus.

3. Automaattinen ohjelmointi.

Joten pääsemme tämän artikkelin pääaiheeseen. Ohjelmointi äärellistiloisissa koneissa säästää ohjelman kahdessa ensimmäisessä esimerkissä olevilta puutteilta. Ohjelma yksinkertaistuu, sitä on helppo muokata.

Automaattityyliin kirjoitettu ohjelma on kuin kytkin, joka olosuhteista riippuen siirtyy tilaan tai toiseen. Ohjelmoija tietää aluksi tilojen lukumäärän.

Karkeasti ottaen se on kuin valokytkin. On kaksi tilaa päällä ja pois päältä, ja kaksi ehtoa päällä ja pois päältä. No, ensimmäiset asiat ensin.

Multitaskingin käyttöönotto kytkinteknologiassa.

Mikrokontrolleri pystyy ohjaamaan kuormitusta, vilkkumaan LED-valoja, seuraamaan näppäinpainalluksia ja paljon muuta. Mutta kuinka tehdä tämä kaikki samaan aikaan? Tähän ongelmaan on monia ratkaisuja. Yksinkertaisin näistä, joista jo mainitsin, on keskeytysten käyttö.

Ohjelman aikana, kun keskeytys tapahtuu, ohjain siirtyy pois ohjelmakoodin suorittamisesta ja suorittaa hetken toisen osan ohjelmasta, josta keskeytys on vastuussa. Keskeytys toimii, sitten ohjelman työpiste jatkuu paikasta, josta ohjain keskeytti (sana itsessään osoittaa, että ohjain on keskeytetty).

Toinen tapa toteuttaa moniajo on käyttöjärjestelmien käyttö. Kyllä, pieniä käyttöjärjestelmiä on jo alkanut ilmestyä, joita voidaan käyttää vähän virtaa kuluttavassa ohjaimessa. Mutta usein tämä menetelmä osoittautuu hieman tarpeettomaksi. Loppujen lopuksi miksi tuhlata valvojan resursseja tarpeettomaan työhön, kun on täysin mahdollista tulla toimeen pienellä verenvuodatuksella.

Switch-tekniikalla kirjoitetuissa ohjelmissa tällainen "illuusio" moniajosta saadaan viestinvälitysjärjestelmän ansiosta. Kirjoitin "illuusio", koska se todella on, koska ohjelma ei fyysisesti voi suorittaa koodin eri osia samanaikaisesti. Puhun viestijärjestelmästä hieman pidemmälle.

Viestijärjestelmä.

Voit tuhota useita prosesseja ja luoda illuusion moniajosta käyttämällä viestijärjestelmää.

Oletetaan, että tarvitsemme ohjelman, jossa LED vaihdetaan. Täällä meillä on kaksi konetta, kutsutaan niitä LEDONiksi - kone, joka vastaa LEDin kytkemisestä päälle ja LEDOFF-kone - kone, joka vastaa LEDin sammuttamisesta.

Jokaisella automaatilla on kaksi tilaa, eli automaatti voi olla aktiivisessa tilassa tai ei-aktiivisessa tilassa, kuten veitsikytkin on joko päällä tai pois päältä.

Kun yksi kone on aktivoitu, LED syttyy, kun toinen kone on aktivoitu, LED sammuu. Harkitse pientä esimerkkiä:

Int main(void) ( INIT_PEREF(); //oheislaitteiden (LED) alustus InitGTimers(); //ajastimien alustus InitMessages(); //viestinkäsittelymekanismin alustus InitLEDON(); //LEDON-automaatin alustus InitLEDOFF(); // LEDOFF-automaatin alustus SendMessage(MSG_LEDON_ACTIVATE); //aktivoi LEDON-automaatti sei(); //Ota keskeytykset käyttöön //Ohjelma pääsilmukka while(1) ( ProcessLEDON(); //LEDON:n iteraatio automaatti ProcessLEDOFF(); //LEDOFF-automaatin ProcessMessages iteraatio (); //viestinkäsittely ); )

Riveillä 3-7 tapahtuu erilaisia alustuksia, joten emme ole erityisen kiinnostuneita tästä nyt. Mutta sitten tapahtuu seuraavaa: ennen pääsilmukan käynnistämistä (kun (1)) lähetämme viestin automaatille

Lähetä viesti (MSG_LEDON_ACTIVATE)

vastuussa LEDin valaistuksesta. Ilman tätä pientä askelta meidän hurdy-gurdymme ei toimi. Seuraavaksi pääinfinite while -silmukka tekee suurimman osan työstä.

Pieni poikkeama:

Viestissä on kolme tilaa. Viestitila voi nimittäin olla ei-aktiivinen, asetettu mutta ei-aktiivinen ja aktiivinen.

Kävi ilmi, että viesti oli alun perin ei-aktiivinen, kun lähetimme viestin, se sai tilan "asennettu mutta ei-aktiivinen". Ja tämä antaa meille seuraavan. Kun ohjelma suoritetaan peräkkäin, LEDON-automaatti ei saa viestiä. Tapahtuu LEDON-automaatin joutokäynti, jossa viestiä ei yksinkertaisesti voida vastaanottaa. Koska viestin tila on "asennettu, mutta ei-aktiivinen", ohjelma jatkaa suoritustaan.

Kun kaikki automaatit ovat käyttämättömänä, jono saavuttaa ProcessMessages()-funktion. Tämä toiminto sijoitetaan aina silmukan loppuun, kun kaikki automaattiset iteraatiot on suoritettu. ProcessMessages()-funktio yksinkertaisesti muuttaa viestin "asetettu mutta ei-aktiivisesta" tilasta "aktiiviseen" tilaan.

Kun ääretön silmukka suorittaa toisen kierroksen, kuva on jo täysin erilainen. ProcessLEDON-automaatin iteraatio ei ole enää tyhjäkäynnillä. Kone pystyy vastaanottamaan viestin, siirtymään valaistuun tilaan ja myös lähettämään viestin vuorotellen. Se osoitetaan LEDOFF-automaatille ja viestin elinkaari toistetaan.

Haluan huomata, että "aktiivisessa" tilassa olevat viestit tuhoutuvat, kun ne kohtaavat ProcessMessages-toiminnon. Siksi vain yksi automaatti voi vastaanottaa viestin. On olemassa toisentyyppisiä viestejä - nämä ovat lähetysviestejä, mutta en ota niitä huomioon, ne ovat myös hyvin käsitelty Tatarchevskiyn artikkeleissa.

Ajastimet

Asianmukaisella viestinnällä voimme hallita tilakoneiden työjärjestystä, mutta emme tule toimeen ilman viestejä yksin.

Olet ehkä huomannut, että edellinen esimerkkikoodinpätkä ei toimi tarkoitetulla tavalla. Koneet vaihtavat viestejä, LEDit vaihtuvat, mutta emme näe tätä. Näemme vain hämärästi valaistun LEDin.

Tämä johtuu siitä, että emme miettineet asiantuntevaa viivästysten käsittelyä. Loppujen lopuksi ei riitä, että käännämme LED-valot vuorotellen päälle ja pois, LEDin on viipyttävä jokaisessa tilassa esimerkiksi sekunti.

Algoritmi tulee olemaan seuraava:

Voit klikata suurentaaksesi

Unohdin lisätä tähän lohkokaavioon, että kun ajastin tikittää, suoritetaan tietysti toiminto - LED syttyy tai sammutetaan.

1. Siirrymme tilaan vastaanottamalla viestin.

2. Tarkistamme ajastimen/laskurin lukemat, jos se tikittää, niin suoritamme toiminnon, muuten lähetämme vain viestin itsellemme.

3. Lähetämme viestin seuraavalle automaatille.

4. Poistu

Seuraavassa merkinnässä kaikki toistetaan.

SWITCH-teknologiaohjelma. Kolme askelta.

Ja kirjoitetaan ohjelma äärellisillä automaateilla ja tätä varten meidän on tehtävä vain kolme yksinkertaista vaihetta. Ohjelma on yksinkertainen, mutta kannattaa aloittaa yksinkertaisista asioista. Meille sopii kytkentä-LED-ohjelma. Tämä on erittäin hyvä esimerkki, joten älkäämme keksikö mitään uutta.

Kirjoitan ohjelman C-kielellä, mutta tämä ei tarkoita ollenkaan, että äärellisissä automaateissa sinun on kirjoitettava vain C-kielellä, on täysin mahdollista käyttää mitä tahansa muuta ohjelmointikieltä.

Ohjelma on modulaarinen ja siksi jaetaan useisiin tiedostoihin. Moduulimme ovat:

Ohjelman pääsilmukkamoduuli sisältää tiedostot leds_blink.c, HAL.c, HAL.h
Ajastinmoduuli sisältää tiedostoja timers.c, timers.h
Viestinkäsittelymoduuli sisältää tiedostoja messages.c, messages.h
Konemoduuli 1 sisältää ledon.c-, ledon.h-tiedostoja
Konemoduuli 2 sisältää ledoff.c-tiedostoja, ledoff .h

Vaihe 1.

Luomme projektin ja yhdistämme siihen välittömästi staattisten moduuliemme tiedostot: timers.c, timers.h, messages.c, messages.h.

Ohjelman pääjakson moduulin tiedosto leds_blink.c.

#include "hal.h" #include "messages.h" //viestinkäsittelymoduuli #include "times.h" //ajastinmoduuli //Ajastin keskeyttää //############# # ################################################# ############################ ISR(TIMER0_OVF_vect) // Keskeytä vektorin siirtymä (T0 laskurin ajastimen ylivuoto) ( ProcessTimers(); / /Ajastimen keskeytyskäsittely) //########################################### Int main (void) ( INIT_PEREF(); //oheislaitteiden (LED) alustus InitGTimers(); //ajastimien alustus InitMessages(); //viestinkäsittelymekanismin alustus InitLEDON(); //LEDON-automaatin alustus Aloita LEDON-automaatti ProcessLEDOFF(); ProcessMessages( ); //viestinkäsittely ); )

Ensimmäisillä riveillä loput moduulit on kytketty pääohjelmaan. Tässä näemme, että ajastinmoduuli ja viestinkäsittelymoduuli on kytketty. Seuraavaksi ohjelmassa on ylivuotokeskeytysvektori.

Riviltä int main (void) voidaan sanoa, että pääohjelma alkaa. Ja se alkaa kaiken ja kaiken alustamisesta. Täällä alustamme oheislaitteet, eli asetamme alkuarvot vertailijan tulo/lähtöportteihin ja kaikkeen muuhun ohjaimen sisältöön. Kaikki tämä tehdään INIT_PEREF-funktiolla, suoritamme sen täällä, vaikka sen päärunko on hal.c-tiedostossa.

Seuraavaksi näemme ajastimien alustuksen, viestinkäsittelymoduulin ja automaattien alustuksen. Täällä nämä toiminnot myös yksinkertaisesti käynnistetään, vaikka itse toiminnot on kirjoitettu niiden moduulien tiedostoihin. Katso kuinka kätevää. Ohjelman pääteksti on edelleen helppolukuinen, eikä se ole täynnä ylimääräistä koodia, joka rikkoo jalkasi.

Tärkeimmät alustukset on ohi, nyt meidän on aloitettava pääsilmukka. Tätä varten lähetämme aloitusviestin ja lisäksi käynnistämme kellomme - käynnistämme ajastimen.

AloitaGTimer(TIMER_SEK); //Käynnistä ajastin SendMessage(MSG_LEDON_ACTIVATE); //aktivoi FSM1-kone

Ja pääsilmukka, kuten sanoin, näyttää hyvin yksinkertaiselta. Kirjoitamme kaikkien automaattien toiminnot muistiin, kirjoitamme ne vain sarakkeeseen noudattamatta järjestystä. Nämä toiminnot ovat automaattiohjaimia ja sijaitsevat automaatiomoduuleissa. Viestinkäsittelymoduulin toiminto täydentää tämän automaattipyramidin. Tietenkin kerroin tämän jo aiemmin, kun käsittelin viestintäjärjestelmää. Nyt voit nähdä, miltä pääohjelmasilmukan moduulin kaksi muuta tiedostoa näyttävät

Hal.h on ohjelman pääsilmukkamoduulin otsikkotiedosto.

#ifndef HAL_h #määritä HAL_h #sisällytä #sisältää //Vakiokirjasto sisältäen keskeytykset #define LED1 0 #define LED2 1 #define LED3 2 #define LED4 3 #define Komparator ACSR //comparator #define ViklKomparator 1<

Kuten näet, tämä tiedosto ei sisällä luonnostaan yhtä riviä suoritettavaa koodia - nämä ovat kaikki makrokorvauksia ja kirjastoyhteyksiä. Tämä tiedosto tekee elämästä erittäin hyvää, se parantaa näkyvyyttä.

Mutta Hal.c-tiedosto on jo suoritettava tiedosto, ja kuten jo mainitsin, se sisältää erilaisia oheislaitteiden alustuksia.

#include "hal.h" void INIT_PEREF(void) ( //Alusta I/O-portit //############################ ################################################# # ##### Komparator = ViklKomparator; //vertailijan alustus - sammuta DDRD = 1<

No, näytin ohjelman pääsyklin moduulin, nyt meidän on otettava viimeinen askel, meidän on kirjoitettava itse automaattien moduulit.

Vaihe 3

Meidän tehtävämme on kirjoittaa äärellisten automaattien moduulit, meidän tapauksessamme LEDON-automaatti ja LEDOFF-automaatti. Aluksi annan LEDin sytyttävän koneen ohjelman tekstin, ledon.c-tiedoston.

//tiedosto ledon.c #include "ledon.h" #include "times.h" #include "messages.h" unsigned char ledon_state; //tilamuuttuja void InitLEDON(void) ( ledon_state=0; //tässä voit alustaa muita automaattimuuttujia, jos niitä on )) //jos on viesti, se hyväksytään ( //ja ajastin tarkistetaan if(GetGTimer(TIMER_SEK)==one_sek) //jos ajastin on asettanut 1s, niin suorita ( StopGTimer(TIMER_SEK); PORTD = 1<

Täällä ensimmäisillä riveillä, kuten aina, kirjastot yhdistetään ja muuttujat ilmoitetaan. Seuraavaksi olemme jo käyneet ne toiminnot, jotka olemme jo tavanneet. Tämä on InitLEDON-automaatin alustustoiminto ja itse ProcessLEDON-automaatinkäsittelijän toiminto.

Käsittelijän rungossa ajastinmoduulin ja viestimoduulin toimintoja käsitellään jo. Ja itse automaatin logiikka perustuu kytkinkotelon suunnitteluun. Ja tässä näet, että automaatin käsittelijä voi myös monimutkaista lisäämällä muutama tapauskytkin.

Automaattien otsikkotiedosto olisi vieläkin yksinkertaisempi:

//fsm1-tiedosto #ifndef LEDON_h #määritä LEDON_h #sisällytä "hal.h" void InitLEDON(void); void ProcessLEDON(void); #loppu Jos

Tässä yhdistetään linkkitiedosto hal.h ja määritetään myös funktioiden prototyypit.

LEDin sammuttamisesta vastaava tiedosto näyttää melkein samalta vain peilikuvassa, joten en näytä sitä tässä - vastahakoisuus 🙂

Voit ladata kaikki projektitiedostot tästä linkistä ====>>> LINKKI.

Tässä on vain kolme vaihetta ja ohjelmamme on saanut valmiin ilmeen, mikä tarkoittaa, että tämän päivän tehtäväni on ohi ja on aika päättää. Minusta näyttää siltä, että tässä artikkelissa annetut tiedot ovat erittäin hyödyllisiä sinulle. Mutta siitä on todellista hyötyä vain, kun käytät tätä tietoa käytännössä.

Muuten, olen suunnitellut useita mielenkiintoisia projekteja, joista tulee erityisen mielenkiintoisia, joten muista tehdä se tilaa uusia artikkeleita . Aion lähettää myös lisämateriaaleja, joten monet ihmiset ovat jo tilaaneet sivuston pääsivun kautta. Voit myös tilata täältä.

No, nyt minulla on todella kaikki, joten toivon sinulle onnea, hyvää mieltä ja nähdään taas.

N/A Vladimir Vasiliev

Tässä artikkelissa termi "tilakone" viittaa algoritmiin, joka voi olla jossakin pienestä määrästä tiloja. "Tila" on tietty ehto, joka määrittää tulo- ja lähtösignaalien sekä tulosignaalien ja sitä seuraavien tilojen tietyn suhteen. Älykäs lukija huomaa heti, että tässä artikkelissa kuvatut tilakoneet ovat Mealy-koneita. Mealy-kone on äärellisen tilan kone, jossa lähdöt ovat nykyisen tilan ja tulon toimintoja, toisin kuin Mooren kone, jossa lähdöt ovat vain tilan toimintoja. Molemmissa tapauksissa seuraava tila on nykyisen tilan ja tulosignaalin funktio.

Harkitse esimerkkiä yksinkertaisesta äärellistilakoneesta. Kuvittele, että tekstimerkkijonossa sinun on tunnistettava merkkijono "//". Kuva 1 näyttää kuinka tämä tehdään tilakoneella. Ensimmäinen kauttaviivan esiintyminen ei tuota lähtösignaalia, mutta se saa automaatin siirtymään toiseen tilaan. Jos automaatti ei löydä kauttaviivaa toisesta tilasta, se palaa ensimmäiseen, koska se tarvitsee 2 kauttaviivaa peräkkäin. Jos toinen vinoviiva löytyy, automaatti antaa "valmis" -signaalin.

Ota selvää, mitä asiakas tarvitsee.

Piirrä tilasiirtymäkaavio

Koodaa tilakoneen "luuranko" ilman siirtymätoimintojen yksityiskohtia.

Varmista, että siirrokset toimivat oikein.

Määritä siirtymien yksityiskohdat.

Tehdä testi.

Tilakoneesimerkki

Tarkastellaanpa mielenkiintoisempaa esimerkkiä äärellistilakoneesta - ohjelmaa, joka ohjaa lentokoneen laskutelineen sisään- ja ulosvetämistä. Vaikka useimmissa lentokoneissa tämä toimenpide suoritetaan sähköhydraulisella ohjausmekanismilla (vain siksi, että koneessa ei ole tietokonetta), joissain tapauksissa, kuten miehittämättömissä ilma-aluksissa, kannattaa käyttää ohjelmistoohjausta.

Ensin käsitellään laitteita. Lentokoneen laskuteline koostuu etututetelijasta, vasemmasta päätelineestä ja oikeasta päätelineestä. Niitä ohjaa hydraulinen mekanismi. Sähkökäyttöinen hydraulipumppu tuottaa painetta tehotoimilaitteelle. Ohjelmiston avulla pumppu kytketään päälle tai pois päältä. Tietokone säätää suuntaventtiilin asentoa - "alas" tai "ylös" salliakseen paineen nostaa tai laskea alustaa. Jokaisessa laskutelineen jalassa on rajakytkin: yksi niistä on kiinni, jos laskuteline nostetaan, toinen - jos se on kiinnitetty "alas"-asentoon. Sen määrittämiseksi, onko lentokone maassa, nokkavaihdetuen rajakytkin sulkeutuu, jos lentokoneen paino on nokkavaihteen päällä. Ohjaajan hallintalaitteet koostuvat ylemmästä/alemmasta laskutelineen varresta ja kolmesta valosta (yksi jokaiselle jalalle), jotka voidaan sammuttaa, vihreä (alas-asento) tai punainen (siirtymäasento).

Ja nyt siirrytään äärellisen tilakoneen kehittämiseen. Ensimmäinen ja vaikein askel on ymmärtää asiakkaan todelliset odotukset. Yksi tilakoneen eduista on se, että se pakottaa ohjelmoijan pohtimaan kaikki mahdolliset tapaukset ja sen seurauksena saamaan kaikki tarvittavat tiedot asiakkaalta. Miksi tämä on mielestäni vaikein vaihe? Ja kuinka monta kertaa sinulle on annettu tällainen tehtäväkuvaus: älä vedä laskutelinettä sisään, jos kone on maassa.

Tämä on tietysti tärkeää, mutta asiakas uskoo, että tähän kaikki loppuu. Entä muut tapaukset? Riittääkö laskutelineen sisäänvetäminen sillä hetkellä, kun kone nousee maasta? Entä jos lentokone pomppii kiitotiellä olevan kohoumasta? Entä jos lentäjä siirtää vaihdevivun "ylös"-asentoon pysäköinnin aikana ja sen seurauksena alkaa nousta? Pitäisikö alustan nousta tässä tapauksessa?

Yksi tilakoneen ajattelun eduista on se, että voit nopeasti piirtää tilasiirtymäkaavion projektiotaululle suoraan asiakkaan eteen ja käydä läpi prosessin hänen kanssaan. Tilasiirtymän seuraava nimitys hyväksytään: "siirtymän aiheuttanut tapahtuma" / "siirtymän seurauksena lähtösignaali". Jos olisimme kehittäneet vain sen, mitä asiakas alun perin pyysi ("älä vedä laskutelinettä sisään, jos lentokone on maassa"), olisimme saaneet kuvan 2 mukaisen koneen.

Kun laadit tilasiirtymäkaaviota (tai mitä tahansa muuta algoritmia), pidä mielessä seuraavat asiat:

Tietokoneet ovat erittäin nopeita verrattuna mekaanisiin laitteisiin.

Mekaaninen insinööri, joka selittää, mitä on tehtävä, ei välttämättä tiedä tietokoneista ja algoritmeista yhtä paljon kuin sinä. Ja tämä on myös positiivinen asia, muuten sinua ei tarvittaisi!

Miten ohjelmasi käyttäytyy, jos mekaaninen tai sähköinen osa rikkoutuu?

Tilakone, joka perustuu siihen, mitä asiakas todella haluaa, on esitetty kuvassa 3. Tässä halutaan estää lentokoneen laskutelineiden vetäytyminen sisään ennen kuin se on varmasti ilmassa. Tätä varten kone odottaa muutaman sekunnin laskukytkimen avaamisen jälkeen. Haluamme myös reagoida lentäjän vivun nousevaan reunaan tason sijaan, jolloin vältytään ongelmilta, jos joku liikuttaa vipua koneen ollessa pysäköitynä. Laskutelineen sisään- tai ulosvetäminen vie muutaman sekunnin ja meidän on varauduttava tilanteeseen, että ohjaaja muuttaa tämän toimenpiteen aikana mielensä ja siirtää vipua vastakkaiseen suuntaan. Huomaa myös, että jos kone laskeutuu uudelleen ollessamme "Odottaa nousua" -tilassa, ajastin käynnistyy uudelleen ja vetäytyminen tapahtuu vain, jos kone on ollut ilmassa 2 sekuntia.

State Machine -toteutus

Lista 1 on toteuttamani tilakoneen kuvassa 3. Keskustellaanpa joistakin koodin yksityiskohdista.

/*listaus 1*/

typedef enum(VAIHDE_ALAS = 0, WTG_FOR_TKOFF, RAISING_GEAR, GEAR_UP, LOWERING_GEAR) Tilatyyppi;

/*Tämä taulukko sisältää osoittimia tietyissä tiloissa kutsuttaviin funktioihin*/

mitätön(*tilataulukko)() = (GearDown, WtgForTakeoff, RaisingGear, GearUp, LoweringGear);

Tila_tyyppi nykyinen_tila;

InitializeLdgGearSM();

/* Automaattin sydän on tämä loputon silmukka. Vastaava toiminto

Nykyinen tila, kutsutaan kerran iteraatiossa */

sillä aikaa (1) {

tila_taulukko();

DecrementTimer();

mitätön InitializeLdgGearSM( mitätön )

nykyinen_tila = VAIHDA_ALAS;

/*Pysäytä laitteisto, sammuta valot jne.*/

mitätön Vaihtaa pienemmälle vaihteelle( mitätön )

/* Siirry odotustilaan, jos kone

Ei maassa ja saatiin käsky nostaa alusta * /

jos((vaihdevipu == YLÖS) && (edellinen_vaihdevipu == ALAS) && (kyykkykytkin == YLÖS)) (

curr_state = WTG_FOR_TKOFF;

prev_gear_lever = vaihdevipu;

mitätön RaisingGear( mitätön )

jos((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (

nykyinen_tila = VAIHTO_YLÖS;

/*Jos lentäjä on muuttanut mielensä, mene laskutelineen alas-tilaan*/

jos(vaihdevipu == ALAS) (

nykyinen_tila = LOWERING_GEAR;

mitätön Varustautua( mitätön )

/*jos lentäjä siirsi vivun "alas"-asentoon,

Siirry tilaan "laskuteline alas" * /

jos(vaihdevipu == ALAS) (

nykyinen_tila = LOWERING_GEAR;

mitätön WtgForTakeoff( mitätön )

/* Odota ennen kuin nostat rungon. */

jos(ajastin<= 0.0) {

nykyinen_tila = NOSTO_KÄYTTÖ;

/*Jos koskemme uudelleen tai lentäjä muutti mielensä, aloita kaikki alusta*/

jos((squat_switch == DOWN) || (vaihdevipu == ALAS)) (

nykyinen_tila = VAIHDA_ALAS;

/* En halua vaatia hänen vaihtamaan vipua uudelleen

Tämä oli vain pomppiminen.*/

prev_gear_lever = ALAS;

mitätön Laskuvaihde( mitätön )

jos(vaihdevipu == YLÖS) (

nykyinen_tila = NOSTO_KÄYTTÖ;

jos((nosegear_is_down == MADE) && (leftgear_is_down == MADE) &&(rtgear_is_down == MADE)) (

nykyinen_tila = VAIHDA_ALAS;

Ensinnäkin saatat huomata, että kunkin tilan toiminnallisuus on toteutettu erillisellä C-funktiolla. Automaatti olisi tietysti mahdollista toteuttaa kytkinkäskyllä, jossa jokaiselle tilalle on oma tapaus, mutta tämä voi johtaa erittäin pitkään funktioon (10-20 koodiriviä per 1 tila kutakin 20-30 tilaa kohti ). Se voi myös johtaa virheisiin, jos muutat koodia testauksen viimeisessä vaiheessa. Et ehkä ole koskaan unohtanut break-lausetta tapauksen lopussa, mutta minulla on ollut sellaisia tapauksia. Yhden tilan koodi ei koskaan pääse toisen tilan koodiin, jos sinulla on erillinen toiminto jokaiselle tilalle.

Switch-käskyn käyttämisen välttämiseksi käytän tilafunktioita osoittavia osoittimia ja ilmoitan taulukon indeksinä käytetyn muuttujan olevan tyyppiä enum.

Yksinkertaisuuden vuoksi I/O-laitteisto, joka vastaa kytkimien tilan lukemisesta, pumppujen käynnistämisestä ja sammuttamisesta jne., on esitetty yksinkertaisina muuttujina. Oletetaan, että nämä muuttujat ovat "maagisia osoitteita", jotka on liitetty laitteistoon näkymättömin keinoin.

Toinen ilmeinen asia on, että koodilla ei tässä vaiheessa ole erityistä roolia. Se vain kulkee tilasta toiseen. Tämä on tärkeä välivaihe, eikä sitä pidä jättää huomiotta. Muuten, olisi kiva lisätä ehdollisten käännösohjeiden väliin print-lauseita (#ifdef DEBUG .. #endif), jotka tulostaisivat tulosignaalien nykyisen tilan ja arvot.

Menestyksen avain piilee koodissa, joka aiheuttaa tilasiirtymän, ts. määrittää, että syöttö on tapahtunut.

Jos koodi kulkee oikein kaikkien tilojen läpi, seuraava vaihe on kirjoittaa koodin "täyte" eli tarkalleen mikä tuottaa lähtösignaalin. Muista, että jokaisella siirrolla on tulosignaali (tapahtuma, joka laukaisi sen) ja lähtösignaali (laitteiston I/O-laite, kuten esimerkissämme). Usein on hyödyllistä tallentaa tämä tilasiirtymätaulukon muodossa.

Tilasiirtymätaulukossa on yksi rivi tilasiirtymää kohti.

Kun koodaat tilakonetta, yritä pitää se vahvana - vahva vastaavuus asiakkaan vaatimusten ja koodin välillä. Voi olla tarpeen piilottaa laitteiston yksityiskohdat toiseen toimintokerrokseen, esimerkiksi jotta tilakonekoodi näyttäisi mahdollisimman tarkasti tilasiirtymätaulukolta ja tilasiirtymäkaaviolta. Tämä symmetria auttaa estämään virheitä ja selittää, miksi tilakoneet ovat niin tärkeä osa sulautetun ohjelmoijan arsenaalia. Saman vaikutuksen voisi tietysti saavuttaa valintaruuduilla ja äärettömällä määrällä sisäkkäisiä if-lauseita, mutta koodia olisi erittäin vaikea seurata ja verrata asiakkaan toiveisiin.

Listing 2:n koodinpätkä laajentaa RaisingGear()-funktiota. Huomaa, että RaisingGear()-funktion koodilla on taipumus peilata Raising Gear -tilan siirtymätaulukon kahta riviä.

mitätön RaisingGear( mitätön )

/*Kun kaikki kytkimet ovat ylhäällä, siirry "runko ylös" -tilaan*/

jos((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (

pumpun_moottori=OFF;

gear_lights = SAMMUTA;

nykyinen_tila = VAIHTO_YLÖS;

/*Jos lentäjä muuttaa mielensä, aloita laskutelineen sisäänveto*/

jos(vaihdevipu == ALAS) (

pumpun_suunta = ALAS;

nykyinen_tila = VAIHDE_LASKUS;

Muista välttää piilotiloja. Piilotettu tila tulee näkyviin, kun yrität laiskuudesta lisätä ehdollisen alitilan konkreettisen tilan lisäämisen sijaan. Jos koodisi esimerkiksi käsittelee samaa syötettä eri tavoilla (eli käynnistää eri tilasiirtymiä) tilasta riippuen, se on piilotettu tila. Tässä tapauksessa ihmettelen, eikö tätä tilaa pitäisi jakaa kahteen osaan? Piilotettujen tilojen käyttö mitätöi kaikki tilakoneen käytön edut.

Käytännössä voit pidentää juuri tarkastelemaamme tilakonetta lisäämällä aikakatkaisun rungon sisään- tai pidentämisjaksoon, kuten koneinsinööri ei halua hydraulipumpun käyvän yli 60 sekuntia. Jos sykli päättyy, ohjaajaa on varoitettava vaihtamalla vihreä ja punainen valo ja hänen on voitava siirtää vipua uudelleen yrittääkseen uudelleen. Voit myös kysyä hypoteettiselta koneinsinööriltä, miten pumppuun vaikuttaa suunnan vaihto sen ollessa käynnissä, koska se tapahtuu 2 tapauksessa, kun ohjaaja muuttaa mieltään. Tietenkin mekaanikko sanoo, että se on negatiivinen. Miten sitten muuttaisit tilakoneen pysäyttämään pumpun nopeasti suunnan vaihtamisen yhteydessä?

Tilan konetestaus

Koodausalgoritmien kauneus äärellisen tilan koneina on, että testisuunnitelma kirjoittaa lähes automaattisesti itsensä. Sinun tarvitsee vain käydä läpi jokainen tilasiirtymä. Teen tämän yleensä markkeri kädessä ja vedän yli nuolet tilasiirtymäkaaviosta, kun ne läpäisevät testin. Tämä on hyvä tapa välttää "piilotettuja tiloja" - ne jäävät väliin useammin testeissä kuin konkreettisia tiloja.

Tämä vaatii paljon kärsivällisyyttä ja paljon kahvia, sillä keskikokoisessakin tilakoneessa voi olla jopa 100 erilaista siirtymää. Muuten, hyppyjen määrä on loistava tapa mitata järjestelmän monimutkaisuutta. Jälkimmäinen määräytyy asiakkaan vaatimusten mukaan, ja tilakone tekee testauksen laajuuden ilmeiseksi. Vähemmän organisoidulla lähestymistavalla vaadittavien testausten määrä voi olla yhtä vaikuttava, mutta et vain tiedä siitä.

Koodissa on erittäin kätevää käyttää tulostettuja lausuntoja, jotka näyttävät nykyisen tilan, tulo- ja lähtösignaalien arvot. Näin voit helposti havaita, mitä "ohjelmistotestauksen kultainen sääntö" ilmaisee: testaa, että ohjelma tekee sen, mitä sen on tarkoitus tehdä, ja myös, ettei se tee mitään ylimääräistä. Toisin sanoen, saatko vain odotuksiasi, ja mitä muuta tapahtuu sen lisäksi? Onko olemassa "kovia" tilasiirtymiä, ts. tilat, jotka menevät satunnaisesti läpi, vain yhden silmukan iteraation aikana? Muuttuvatko tulokset, kun et odota niiden muuttuvan? Ihannetapauksessa printfs-tulosten tulisi muistuttaa läheisesti tilasiirtymätaulukkoa.

Lopuksi - ja tämä koskee kaikkia sulautettuja ohjelmistoja, ei vain tilakonepohjaisia ohjelmistoja - ole erittäin varovainen, kun suoritat ohjelmiston ensimmäistä kertaa oikealla laitteistolla. On erittäin helppoa saada napaisuus väärin - "Hups, luulin, että '1' tarkoitti rungon nostamista ja 0 tarkoitti sen laskemista." Monissa tapauksissa laitteisto-assistentti käytti väliaikaista "kanakytkintä" suojellakseen arvokkaita komponentteja, kunnes hän oli varma, että ohjelmistoni liikutti asioita oikeaan suuntaan.

tuoda markkinoille

Kun kaikki asiakkaan vaatimukset täyttyvät, voin käynnistää tämän monimutkaisen tilakoneen parissa päivässä. Melkein aina automaatit tekevät mitä haluan. Vaikeinta on tietysti ymmärtää tarkalleen mitä asiakas haluaa ja varmistaa, että asiakas itse tietää mitä haluaa. Jälkimmäinen kestää paljon kauemmin!

Martin Gomez on ohjelmoija Johns Hopkinsin yliopiston Applied Physics Laboratoryssa. Osallistuu ohjelmistojen kehittämiseen tutkimusavaruusalusten lentämistä varten. Hän on työskennellyt sulautettujen järjestelmien kehittämisen parissa 17 vuotta. Martinilla on kandidaatin tutkinto ilmailutekniikasta ja MS sähkötekniikasta Cornellin yliopistosta.

Automaattiteoria

Automaatti ja sen lajikkeet. Taulukot ja kaaviot siirtymistä ja poistumisista. Subautomaatit. Pelkistetty automaattilause

Toimenpiteet koneiden kanssa

Jauhokoneen muuttaminen Moore-koneeksi ja Moore-koneen muuttaminen jauhokoneeksi. Automaattien vastaavuus. Automaattien tilojen erottuvuus. Automaattien minimointi. Automaattien synteesi. Automaattien tunnistaminen

Automaattinen - mekanismien, laitteiden järjestelmä, jossa energian, materiaalien, tiedon hankinta-, muunnos-, siirtoprosessit ovat täysin automatisoituja. Termiä "automaattinen" käytetään kahdessa suhteessa:

1) tekninen,

2) matemaattinen.

Matemaattisessa lähestymistavassa automaatilla tarkoitetaan teknisen laitteen matemaattista mallia, jolla on oltava sisäänmenot, sisäiset tilat ja lähdöt. Laitteen rakenteen yksityiskohdista ei pitäisi olla tietoa.

Teknisessä lähestymistavassa automaatilla ymmärretään hyvin todellinen laite, esimerkiksi puhelinkoppi, myyntiautomaatti jne. Tällöin laitteen sisäisen rakenteen yksityiskohdat ovat tietysti tiedossa.

Erityinen ja tärkeä automaatin tapaus on digitaalinen automaatti (DA), jossa digitaalisen tiedon vastaanotto-, muunnos-, tallennus- ja luovutusprosessit ovat täysin automatisoituja.

Signaalien näkökulmasta CA on hyödyllistä määritellä järjestelmäksi, joka voi vastaanottaa tulosignaaleja niiden vaikutuksen alaisena siirtyä tilasta toiseen, tallentaa sitä seuraavan tulosignaalin saapumiseen asti ja antaa lähtösignaaleja.

CA katsotaan äärelliseksi, jos tulosignaalien X, tilojen S ja lähtösignaalien joukot Y ovat äärellisiä. Äärillinen automaatti voidaan liittää laitteeseen, kuten tietokoneeseen. Tietokone prosessoi saapuvat syöttötiedot lähtötiedoiksi (tuloksiksi), mutta tämä tulos ei vastaa vain syöttödataa, vaan myös tietokoneen senhetkistä tilaa, ts. ne tiedot, jotka on tallennettu tietokoneen muistiin, esimerkiksi aikaisempien laskelmien tulokset, laskentaohjelmat.

Varmentajan työ suoritetaan automaattisessa ajassa, joka määräytyy tulosignaalien vastaanottojaksojen lukumäärän mukaan.

Abstrakti automaatti on matemaattinen malli erillisestä laitteesta, jossa on yksi tulokanava, joka vastaanottaa minkä tahansa kielen symbolijonoja, yksi lähtökanava, josta otetaan minkä tahansa muun kielen symbolisekvenssit ja joka on missä tahansa tilassa jokaisella diskreetin ajan hetki. Graafisesti abstrakti automaatti on esitetty kuvassa.

Syöttökielen sanat voidaan esittää symboleilla joukosta X=(x 1 ,x 2 ,...x n ), joka on ns. syöttöaakkoset, ja lähtökielen sanat ovat symboleja joukosta Y=(y 1 ,y 2 ,...y p ), jota kutsutaan ns. lähtö aakkoset. Automaattin tilajoukkoa S=(s 1 ,s 2 ,...s m ) kutsutaan ns. valtion aakkoset.

konsepti koneen tila käytetään kuvaamaan järjestelmiä, joiden lähtösignaalit eivät ole riippuvaisia pelkästään tulosignaaleista kulloinkin, vaan myös jostain esihistoriasta, ts. signaalit, jotka tulivat järjestelmän tuloihin aikaisemmin. Näin ollen digitaaliset automaatit kuuluvat peräkkäisiin piireihin, joissa, kuten jo todettiin, on muisti. Automaattitilan käsite vastaa jotakin menneisyyden muistoa, joten tämän käsitteen käyttöönotto mahdollistaa ajan eliminoimisen eksplisiittisenä muuttujana ja ulostulosignaalien ilmaisemisen tilojen ja tulosignaalien funktiona.

Abstraktin automaatin toimintaa tulee tarkastella suhteessa tiettyihin aikaväleihin, koska jokainen diskreetti intervalli t vastaa sen tulostetta y(t). Näin ollen automaatin toimintaa tarkastellaan diskreettien, rajallisen pituisten aikaväleiden kautta. Digitaalisten automaattien abstraktissa teoriassa katsotaan, että tulosignaalit vaikuttavat synkroniseen automaattiin jokaisen automaatin alussa. i-th intervalli (kvantti) vastaavan kellopulssin (syklin) varaamasta ajasta ja automaatin sisäisten tilojen muutos tapahtuu vierekkäisten kellopulssien välisissä aikaväleissä, kun tulosignaaleilla ei ole vaikutusta.

Käsitettä "tila" käytetään määrittämään automaatin generoiman lähtökielen symbolien ja/tai sanojen toiminnallinen riippuvuus syöttökielen symboleista ja/tai sanoista, kun automaatti toteuttaa annetun algoritmin. Jokaiselle automaattisen sОS tilalle ja jokaiselle symbolille xОX diskreetin ajan hetkellä [t] generoidaan laitteen lähtöön symboli yОY. Tämä riippuvuus määräytyy automaatin j lähtöfunktiosta. Jokaiselle automaattisen nykyiselle tilalle sОS ja jokaiselle symbolille xОX diskreetin ajanhetkellä [t] automaatti siirtyy seuraavaan tilaan sОS. Tämä riippuvuus määräytyy automaatin y siirtymäfunktiosta. Automaatti toimii kahden sekvenssin generoimisena: peräkkäisten automaattisten tilojen sarjan (s 1[ s 2 s 3 ...) ja sekvenssin lähtösymboleja (y 1 y 2 y 3 ...), jotka symbolien sarjalle (x 1 x 2 x 3 ...) avautuvat diskreetin ajan hetkinä t = 1,2,3,.... Suorakaiteen muotoisissa suluissa merkitään diskreetin ajan hetket, joita muuten kutsutaan jaksoiksi. sulut - aakkosten X, Y ja S symbolisarjat.

Niinpä äärellisen automaatin matemaattinen malli on kolmiperusalgebra, jonka kantoaaltoja ovat kolme joukkoa X, Y ja S ja operaatiot kaksi funktiota j ja y.

Automaattiteoria on diskreetin matematiikan osa, joka tutkii diskreettien tiedonmuuntimien malleja. Tällaiset muuntimet ovat sekä todellisia laitteita (tietokoneet, elävät organismit) että kuvitteellisia laitteita (aksiomaattiset teoriat, matemaattiset koneet). Pohjimmiltaan äärellisen tilan konetta voidaan kuvata laitteeksi M , jolla on tulo- ja lähtökanavat, kun taas kullakin diskreetillä aikahetkellä, jota kutsutaan kellohetkeksi, se on jossakin lopputiloista.

Tulokanavalla milloin tahansa t =1, 2, ... laitteelle M tulosignaalit saapuvat (joistakin äärellisistä signaalijoukosta). Tilanmuutoslaki seuraavaan ajanhetkeen asetetaan tulosignaalin ja laitteen kulloisenkin hetken tilan mukaan. Lähtösignaali riippuu tilasta ja tulosignaalista kulloinkin (kuva 1).

Tilakone on todellisten diskreettien tietojenkäsittelylaitteiden matemaattinen malli.

valtion kone kutsutaan järjestelmäksi A= (X , K , Y ,  ,  ), missä X , K , Y ovat mielivaltaisia ei-tyhjiä äärellisiä joukkoja, ja  ja  - toiminnot, joista:

joukko X ={a 1 , ..., a m ) kutsutaan syöttöaakkoset , ja sen elementit ovat tulosignaalit , niiden sekvenssit ovat sisällä iskulauseet ;

joukko K ={q 1 , ..., q n ) kutsutaan monet osavaltiot automaatti ja sen elementit - valtioita ;

joukko Y ={b 1 , ..., b p ) kutsutaan lähtö aakkoset , sen elementit ovat lähtösignaalit , niiden sekvenssit ovat lähtösanoja ;

toiminto  : X  K K olla nimeltään siirtymätoiminto ;

toiminto  :X  K Y olla nimeltään lähtötoiminto .

Tällä tavalla,  (x , q )K ,  (x , q )Y varten  x X , q K .

Tilakoneeseen liittyy kuvitteellinen laite, joka toimii seuraavasti. Se voi olla sarjan tilassa K , vastaanottaa signaaleja laitteesta X ja lähettää signaaleja sarjasta Y .

2. Menetelmät äärellisen automaatin määrittelemiseksi

Abstraktien automaattien määrittämiseen on useita vastaavia tapoja, joista kolme ovat: taulukkomainen , geometrinen ja toimiva .

2.1 Koneen taulukkomääritys

Automaattin määritelmästä seuraa, että se voidaan aina määritellä taulukolla, jossa on kaksi sisääntuloa T linjat ja P sarakkeet, missä sarakkeen leikkauskohdassa q ja linjat a funktioarvot ovat arvokkaita  (a i , q j ),  (a i , q j ).

q a	q 1	q j	q n
a 1	(a 1 , q 1),  (a 1 , q 1)	(a 1 , q j ),  (a 1 , q j )	(a 1 , q n ),  (a 1 , q n )

a i	(a i , q 1),  (a i , q 1)	(a i , q j ),  (a i , q j )	(a i , q n ),  (a i , q n )

a m	(a m , q 1),  (a m , q 1)	(a m , q j ),  (a m , q j )	(a m , q n ),  (a m , q n )

2.2. Automaattien määrittely Mooren kaaviolla

Toinen tapa määrittää äärellisen tilan kone on graafinen eli graafin käyttö. Automaatti esitetään merkittynä suunnattuna graafina G(K , D ), jossa on useita pisteitä K ja monia kaaria D ={(q j ,  (a i , q j ))| q j K , a i X ), kun taas kaari ( q j ,  (a i , q j )) on merkitty parilla ( a i ,  (a i , q j )). Näin ollen tällä menetelmällä automaattin tilat on kuvattu ympyröillä, joihin syötetään tilojen symbolit q j (j = 1, …, n ). Jokaisesta ympyrästä suoritetaan T nuolet (suunnatut reunat) yksi yhteen vastaamaan syötetyn aakkoston merkkejä X ={a 1 , ..., a m ). Kirjainta vastaava nuoli a i X ja poistumassa ympyrästä q j K , pari ( a i ,  (a i , q j )), ja tämä nuoli johtaa ympyrään, joka vastaa  (a i , q j ).

Tuloksena olevaa piirrosta kutsutaan automaatiokaavio tai, Mooren kaavio . Ei kovin monimutkaisille automaateille tämä menetelmä on havainnollistavampi kuin taulukkomainen.