Elementen van automatentheorie

Plan:

1. Het concept van een machine, het werkingsprincipe van de machine

2. Methoden voor het specificeren van eindige toestandsmachines

3. Algemene problemen van de automatentheorie

Theoretische informatie

De mens heeft er altijd naar gestreefd zijn werk gemakkelijker te maken door bepaalde mechanische apparaten voor zichzelf te laten werken zonder zijn eigen tussenkomst. Aanvankelijk waren dit sprookjes, daarna begonnen ze alledaagse dingen te worden. Auto's, tv's, wasmachines, hele industrieën werken zonder menselijke tussenkomst. Bovendien is menselijk ingrijpen in de meeste gevallen niet vereist, en in sommige gevallen kan een dergelijk ingrijpen tot negatieve verschijnselen leiden. Het concept van 'machinegeweer', als een apparaat dat een bepaald soort actie uitvoert, wordt door mensen al lang op precies deze manier geïnterpreteerd.

Het concept van een machine, het werkingsprincipe van de machine

Concept machine wordt op twee aspecten bekeken:

1. Automatisch apparaat, waarbij sommige functies worden uitgevoerd zonder directe menselijke deelname. Een automatische machine is een echt apparaat, begrijpelijk waarom en hoe het werkt, althans voor de mensen die het hebben ontworpen en vervaardigd. Een auto, een tractor, een vliegtuig, een stoplicht, een tv, een telefoon - dit zijn allemaal automatische machines. In dit aspect moet een computer worden opgevat als een automaat die werkt volgens een programma dat door een persoon is samengesteld.

2. Automaat – wiskundig concept, dat een wiskundig model van echte technische apparaten aangeeft. Een automatische machine is een abstract apparaat; het is niet duidelijk waarom en hoe het werkt en, in het algemeen, waarom het kan werken. In dit opzicht is de machine een ‘zwarte doos’ die theoretisch in staat is bepaalde acties uit te voeren. Vanuit het oogpunt van de wiskunde is het absoluut onbelangrijk wat, hoe en waarom bepaalde acties tot stand komen.

Elke automaat moet een bepaald aantal ingangen, een bepaald aantal uitgangen en een bepaald aantal interne toestanden hebben.

Algebraïsche automatentheorie is een tak van de theoretische cybernetica die discrete automaten bestudeert vanuit een abstract algebraïsch perspectief.

De algemene theorie van automaten bevat verschillende onderafdelingen. Afhankelijk van het studieonderwerp is het onderverdeeld in abstracte automatentheorie en structurele automatentheorie.

Abstracte automatentheorie bestudeert de overgangen die worden gemaakt door een automaat die wordt beïnvloed door ingangssignalen, evenals uitgangssignalen als gevolg van deze overgangen.

Onderwerp van studie structureel De theorie van automaten is de structuur van de automaat, evenals de structuur van invoer- en uitvoersignalen, bijvoorbeeld methoden voor het coderen van invoer- en uitvoersignalen, enz.

Definitie van eindige toestandsmachines

Machine- een abstract model van een apparaat dat in discrete tijd werkt en een eindige reeks ingangssignalen verwerkt en omzet in een eindige reeks uitgangssignalen (reacties).

Tijdens de werking van een eindige-toestandsmachine wordt een eindig aantal interne toestanden achtereenvolgens gewijzigd, en de toestand van de machine op een bepaald tijdstip wordt op unieke wijze bepaald door de invoer- en uitvoersignalen. Dergelijke machines vormen de basis van alle moderne computertechnologie en allerlei discrete automatische bewakings- en controlesystemen.

Het concept van een automaat is zo abstract dat het moeilijk te zeggen is wanneer iemand het ooit zonder automaten heeft gedaan. Elk apparaat voldoet aan de definitie van een aanvalsgeweer, inclusief apparaten waarmee primitieve mensen jaagden of stenen gooiden om hun huis tegen de vijand te beschermen.

Algoritme– begrijpelijk en een exacte formele instructie aan de uitvoerder, waarbij op ondubbelzinnige wijze de inhoud en volgorde van bewerkingen wordt gedefinieerd die een gegeven set invoergegevens in het gewenste resultaat vertalen

Er wordt aangenomen dat het eerste door de mens gemaakte softwareapparaat een horloge was. Klokmechanismen, die gebruik maken van een veer die tandwielen en nokkenmechanismen, tandwielen en hendels aandrijft, voeren een aantal specifieke acties uit. Een voorbeeld van zo'n klokmechanisme is de beroemde klok in het Centrale Poppentheater in Moskou, waar deze twaalf sprookjesfiguren op de wijzerplaat aandrijft.

Laten we wijzen op een aantal interessante historische feiten met betrekking tot automaten als mechanische apparaten.

1. De Duitse filosoof en alchemist Albert de Grote creëerde van 1216 tot 1246 een 'ijzeren' dienaar - een automaat, die de taken van poortwachter in het huis vervulde.

2. Astronoom Johann Müller (Regiamontan) (1436-1476) creëerde een mechanische adelaar, die met de kanteling van zijn kop en de beweging van zijn vleugels de intocht in Neurenberg van de heilige Romeinse keizer Maximiliaan II begroette.

3. Monteur Jacques de Vacanson (1709-1782) - auteur van 's werelds eerste automatische weefgetouw. Hij creëerde het beeld van een mechanische eend, een exacte kopie van zijn levende dubbelganger: hij zwom, maakte zijn veren schoon, slikte granen uit de palm van zijn hand. Zijn mechanische fluitist, die elf muziekstukken uitvoerde, verbaasde mensen die in die verre jaren leefden.

4. Russische uitvinder uit de 19e eeuw. A. M. Gamuletsky creëerde een volledige mechanische kast, die veel door hem ontworpen machines bevatte. Er was ook een pratend hoofd van een tovenaar en een cupido die harp speelde, wat tot de verbeelding van tijdgenoten sprak.

5. De eerste primitieve rekenmachine werd in 1641 ontworpen door Blaise Pascal. De aanleiding voor de ontdekking was de kwelling van zijn vader, de belastinginspecteur, inspecteur die dag en nacht bezig was met grote berekeningen. Door een rekenmachine uit te vinden, redde de achttienjarige zoon zijn vader van complexe berekeningen en gaf hij de wereld de eerste rekenmachine die getallen kon optellen en aftrekken.

6. De eerste schaakmachine werd in 1890 gebouwd door de Spaanse ingenieur Torres Quevedo. Zo'n machine kon alleen een toreneindspel spelen (heer en toren tegen de koning).

7. De eerste automatisch bestuurde computer werd in 1822 gemaakt door Charles Babbage. Hij ontwierp rekenmachine, die over opslag- en rekenapparaten beschikte. Deze apparaten werden prototypes van soortgelijke apparaten voor moderne computers.

Soorten machines.

De automaat kan worden geïnterpreteerd als een apparaat dat de processen uitvoert van het ontvangen, omzetten en verzenden van energie, materialen of informatie in overeenstemming met het daarin ingebedde programma, maar zonder directe menselijke deelname.

Elke machine heeft zijn eigen basissets, waaronder: invoeralfabet, uitvoeralfabet, reeks toestanden van de machine.

Kenmerkend voor een eindige toestandsmachine is de aanwezigheid geheugen, die afhankelijk van de tijd de toestand van de machine bepaalt. De externe manifestatie van de verschillende toestanden van de machine is de reactie op dezelfde soort invloed (signalen).

Bij de werking van eindige toestandsmachines is dit een belangrijk concept tijd.

Machines kunnen worden geclassificeerd op basis van verschillende criteria.

1. Per type activiteit - Automaten zijn onderverdeeld in: informatie, controle en computergebruik.

NAARinformatie machines omvatten een verscheidenheid aan referentietabellen, informatieborden in stadions en alarmapparatuur.

NAAR controle machines Het is gebruikelijk om te verwijzen naar apparaten voor het besturen van een bepaald proces, waaronder specifiek: een lift, een transportband, een werktuigmachine, een barrière.

NAAR computers omvatten microcalculators, computerprocessors en andere apparaten die berekeningen uitvoeren.

Strikt genomen zijn veel automaten echter zulke complexe systemen dat ze tegelijkertijd computationele, besturings- en informatie-automaten zijn.

2. Eindige toestandsmachines – vanuit het oogpunt van de informatica zijn dit automaten die discrete informatieconverters zijn. Deze omvatten converters die een eindige set ingangs- en uitgangssignalen bevatten, evenals een eindige set interne toestanden

3. Digitale machines- machines die converteren digitaal informatie. In zo'n automaat worden ingangssignalen gegeven in de vorm van een eindige reeks momentane symbolen: hun duur is zo kort dat deze kan worden verwaarloosd. In een vaste tijd worden de invoersymbolen geconverteerd en ondergaat de uitvoer een abrupte overgang van de ene toestand naar de andere.

4. Abstracte automaten - een reeks woorden van het ingevoerde alfabet weergeven Xin reeks woorden van het uitvoeralfabet Y.

Er is een abstracte automaat:

~ Wiskundig model,

~ Algoritme acties van een of andere transformatie van codereeksen,

~ Wet het transformeren van het invoeralfabet in het uitvoeralfabet.

5. Synchrone en asynchrone machines. Afhankelijk van het feit of het ingangssignaal en het statusveranderingssignaal gelijktijdig of opeenvolgend worden ontvangen, worden de machines verdeeld in synchrone en asynchrone machines.

In synchrone machines de duur van de ingangssignalen en de overgangstijden worden op elkaar afgestemd. Ze worden gebruikt in computersystemen, geautomatiseerde besturingssystemen, enz.

In asynchrone machines De duur van de ingangssignalen en de timing van de overgangen zijn niet consistent met elkaar. Ze zijn afhankelijk van externe bronnen - verschillende evenementen, en bemonsteringsinterval is variabel (bijvoorbeeld in combinatiesloten). Bij asynchrone machines kan de volgende verandering in de waarden van de ingangssignalen alleen optreden als het overgangsproces, veroorzaakt door de vorige verandering in deze signalen, is beëindigd.

6. Automaten zijn onderverdeeld in eindige en oneindige automaten. Als de classificatie is gebaseerd op geheugencapaciteit, dan ligt het verschil in de vraag of de machine dat heeft definitief of oneindig aantal interne toestanden.

Onder het eindeloze Een automaat wordt meestal opgevat als een bepaalde wiskundige idealisering van het idee van een automaat, die een oneindig aantal toestanden kent. Het geheugen van zo’n automaat kan potentieel oneindig toenemen. De beroemde abstracte automaten van Post en Turing zijn bijvoorbeeld oneindige automaten, maar de computer zelf of de afzonderlijke onderdelen ervan zijn eindige automaten.

7. Automaten zijn onderverdeeld in deterministische en probabilistische automaten. Als de classificatie is gebaseerd op willekeurig selectiemechanisme, Vervolgens wordt onderscheid gemaakt tussen deterministische en probabilistische (stochastische) automaten.

In deterministische automaten gedrag en structuur op elk moment worden op unieke wijze bepaald door de huidige invoerinformatie en de toestand van de machine zelf op het voorgaande moment.

In probabilistische automaten wordt deze afhankelijkheid ook geassocieerd met een willekeurige keuze.

Probabilistisch Een automaat is een discrete informatieomzetter, waarvan de werking op elk moment alleen afhangt van de geheugentoestanden en wordt beschreven door statistische wetten.

8. Universele automatische machine. In de automatentheorie is bewezen dat het voldoende is om informatie te construeren om verschillende transformaties van informatie uit te voeren universeel een automatische machine met behulp van een programma en de juiste codering, die elk probleem kan oplossen.

Het wiskundige model van een digitale machine met één ingang wordt gespecificeerd door vijf objecten:

X- eindige set invoersymbolen, invoeralfabet:

X= (x 1 (t), x 2 (t), ..., x n (t));

Y- eindige set uitvoersymbolen, uitvoeralfabet:

Y=(y 1 (t), y 2 (t), ..., y n (t));

Vraag~ eindige reeks automaattoestanden:

Q= (q 0 (t), q 1 (t), q 2 (t), ..., q n (t)), v 0- initiële staat;

δ(q, X) - functie van de overgang van de machine van de ene toestand naar de andere: ( Q X X)®Q;

λ(q, X) ~ machine-uitvoerfunctie: ( Q x X) ® Y.

De staatsmachine dus C= (X, Q, Y, δ, λ.) wordt bepaald door herhalingsrelaties

q(0) = q 0 , q(t + I) = δ (g(t), x(t)), y(t) = λ (g(t), x(t)),

Het is een gediscretiseerd moment in de tijd of is het een afbeelding van een monotone functie T:. T® N, en T - gewone continue tijd, N is de verzameling natuurlijke getallen.

Alle werkuren T is verdeeld in een eindig aantal intervallen, op de grens waarvan de toestand van de machine verandert. In dit geval toont t(Г 0) - het aantal veranderingen dat plaatsvond vóór het tijdstip Г 0.

Een voorbeeld van sampling is gewone cinema: de tijd wordt verdeeld in intervallen van 1/24 sec. Het menselijk oog neemt de opeenvolging van discrete frames waar als een continue beweging.

9. Synchrone automaten zijn onderverdeeld in Mealy-automaten en Moore-automaten. Afhankelijk van manier om de uitvoerfunctie te organiseren synchrone machines zijn onderverdeeld in Mili-machines ( type I automaten) en Moore automaten (type II automaten).

In Mili-machines- uitgangssignaal j(T) X(T) en conditie Q(T- 1) de machine op het vorige tijdstip (T- 1). Het wiskundige model van dergelijke automaten is het systeem van vergelijkingen:

q(t) = δ (q(t-1), x(t)) en y(t) = λ (q(t-1), x(t)),

In Moore's machines uitgangssignaal j(T) uniek bepaald door het ingangssignaal X(T) en conditie Q(T) op een gegeven moment t. Het wiskundige model van dergelijke machines is het systeem:

q(t) = δ (q(t-1), x(t)) en y(t) = λ (q(t)),

Bij dergelijke machines hangt de uitgangsfunctie alleen af ​​van de toestand van de machine op een bepaald moment en niet van het ingangssignaal. De invoerreeks van zo'n automaat wordt dus één keer van links naar rechts gelezen, waarbij de tekens één voor één worden gescand. Op een bepaald moment bevindt de eindige toestandsmachine zich in een bepaalde interne toestand, die verandert na het lezen van het volgende teken. De nieuwe status kan worden gekenmerkt door het leessymbool en de huidige status.

10. Combinatiemachines– er zijn automaten waarbij het uitvoersymbool niet afhankelijk is van de status ervan en alleen wordt bepaald door de huidige invoersymbolen, d.w.z. in deze automaat zijn alle toestanden gelijkwaardig. Bij zo'n automaat is de overgangsfunctie gedegenereerd; deze is fundamenteel onbelangrijk en blijft tijdens bedrijf onveranderd. Daarom heeft een minimale combinatorische automaat slechts één toestand.

11 Logisch automaten - er zijn automaten waarvan het invoeralfabet bestaat uit 2 t binaire lengtesets T, en de uitvoer is van 2 n binaire sets met lengte P. Voor logisch combinerend automaten heeft de uitvoerfunctie de vorm van een systeem N logische functies van T variabelen.

Het resultaat van de werking van de machine wordt bepaald door de eindtoestand ervan.

Er zijn verschillende opties voor het specificeren van een eindige toestandsmachine. Een statusmachine kan bijvoorbeeld worden gespecificeerd met behulp van vijf parameters: , waarbij:

De machine begint te werken in status q 0 en leest teken voor teken uit de invoerreeks. Het gelezen symbool brengt de machine vanuit Q over naar een nieuwe toestand in overeenstemming met de overgangsfunctie. Als de machine, na voltooiing van het lezen van het ingevoerde woord (keten van symbolen), zich in een van de acceptatietoestanden bevindt, dan wordt het woord door de machine “geaccepteerd”. In dit geval wordt gezegd dat het tot de taal van de gegeven automaat behoort. Anders wordt het woord "afgewezen".

Staatsmachines worden in de praktijk veel gebruikt, zoals in parsers, lexicale analysatoren en modelgebaseerde softwaretests.

Andere manieren van beschrijven

1. Toestandsdiagram ( of soms overgangsgrafiek) - grafische weergave van een reeks toestanden en overgangsfuncties. Het is een geladen unidirectionele grafiek, waarvan de hoekpunten de toestanden van het ruimtevaartuig zijn, de randen overgangen zijn van de ene toestand naar de andere, en de symbolen waarbij deze overgang plaatsvindt. Als de overgang van toestand q1 naar q2 kan worden uitgevoerd bij het verschijnen van een van meerdere symbolen, dan moeten ze allemaal boven de boog van het diagram (tak van de grafiek) worden ingeschreven.
2. Overgangstafel- tabelweergave van de functie δ. Normaal gesproken komt in een dergelijke tabel elke rij overeen met één status en komt elke kolom overeen met één geldig invoersymbool. In de cel op het snijpunt van de rij en kolom wordt de actie geschreven die de machine moet uitvoeren als deze, in een situatie waarin deze zich in een bepaalde staat bevond, een bepaald symbool aan de ingang ontving.

Determinisme

Eindige machines zijn onderverdeeld in deterministische en niet-deterministische.

Deterministische eindige toestandsmachine

• Een deterministische eindige automaat (DFA) is een automaat waarin voor elke reeks invoersymbolen er slechts één toestand is waarin de automaat vanuit de huidige kan gaan.
• Een niet-deterministische eindige automaat (NFA) is een generalisatie van een deterministische. Het niet-determinisme van automaten wordt op twee manieren bereikt:

Er zijn overgangen gemarkeerd met een lege keten ε	Uit één toestand komen verschillende overgangen voort, gemarkeerd met hetzelfde symbool

Als we het geval beschouwen waarin de machine als volgt wordt gespecificeerd: , waarbij:

Dan verschijnt het derde teken van niet-determinisme: de aanwezigheid van verschillende initiële (start)toestanden van de automaat.

Er is een stelling die stelt dat "Elke niet-deterministische eindige automaat kan worden omgezet in een deterministische automaat, zodat hun talen samenvallen" (dergelijke automaten worden equivalent genoemd). Omdat het aantal toestanden in een gelijkwaardige DFA in het ergste geval echter exponentieel groeit met het aantal toestanden van de oorspronkelijke DFA, is een dergelijke bepaling in de praktijk niet altijd mogelijk. Bovendien zijn eindige toestandsmachines met uitgangen over het algemeen niet bepaalbaar.

Vanwege de laatste twee opmerkingen worden NFA's, ondanks de grotere complexiteit van niet-deterministische eindige automaten, voornamelijk gebruikt voor taken die verband houden met tekstverwerking.

Automaten en reguliere talen

Voor een automaat kan men een taal (een reeks woorden) definiëren in het alfabet Σ dat het is vertegenwoordigt- dit zijn de namen van woorden, bij invoer gaat de machine van de beginstatus naar een van de staten van de set F.

Gespecialiseerde programmeertalen

• Sequential Function Chart (SFC)-taal is een grafische programmeertaal die veel wordt gebruikt voor het programmeren van industriële logische controllers (PLC's).

In SFC wordt een programma beschreven als een schematische reeks stappen die met elkaar zijn verbonden door overgangen.

Modelontwikkeling met behulp van eindige toestandsmachines

Eindige machines maken het mogelijk om modellen van parallelle verwerkingssystemen te bouwen. Om het aantal parallelle processen in een dergelijk model te veranderen, is het echter noodzakelijk om aanzienlijke wijzigingen in het model zelf aan te brengen. Bovendien zal een poging om een ​​complex model op een eindige toestandsmachine te ontwikkelen leiden tot een snelle toename van het aantal toestanden van de machine, wat de ontwikkeling van een dergelijk model uiteindelijk tot een uiterst vervelende taak zal maken. Zoals hierboven opgemerkt, kan het laatste probleem worden opgelost door een niet-deterministische automaat te gebruiken.

Opmerkingen

Zie ook

• Sequentiële logica (sequentiële logica)

Koppelingen

• Theorie van automaten / E. A. Yakubaitis, V. O. Vasyukevich, A. Yu Gobzemis, N. E. Zaznova, A. A. Kurmit, A. A. Lorenz, A. F. Petrenko, V. P. Chapenko // Waarschijnlijkheidstheorie. Wiskundige statistiek. Theoretische cybernetica. - M.: VINITI, 1976. - T. 13. - P. 109–188. - URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
• Toepassing van eindige toestandsmachines om automatiseringsproblemen op te lossen
• Een voorbeeld van een eindige toestandsmachine-implementatie in Python voor het Django-framework

Wikimedia Stichting.

• 2010.
• Keynes, John Maynard

Toestandsdiagram (automaattheorie)

Zie wat een “Finite State Machine” is in andere woordenboeken: staatsmachine

- CA Rekenmodel dat een automaat beschrijft met een eindig aantal toestanden. CA's worden veel gebruikt bij het programmeren, bijvoorbeeld in lexicale analysatoren van compilers. eindige toestandsmachine Sequentiespecificatie... ... Staatsmachine

Zie wat een “Finite State Machine” is in andere woordenboeken:- baigtinis automatas statusas T sritis automatika atitikmenys: engl. eindige automaat; eindige toestandsmachine vok. endlicher Automat, m; Finalautomat, m rus. eindige toestandsmachine, m pranc. automatiseer finale, m; automatiseer fini, m; terminal automatiseren, m;… … Automatikos terminų žodynas

EINDIGE STAATSMACHINE- een automaat, die veel toestanden heeft, evenals veel in- en uitgangssignalen, is eindig. K. een. Het kan een technisch model zijn. apparaten (computer, relaisapparaat) of biol. systemen (geïdealiseerd dierlijk zenuwstelsel). Belangrijk... ... Groot encyclopedisch polytechnisch woordenboek

modulaire staatsmachine- - [Ya.N.Luginsky, M.S.Fezi Zhilinskaya, Yu.S.Kabirov. Engels-Russisch woordenboek voor elektrotechniek en energietechniek, Moskou, 1999] Onderwerpen van elektrotechniek, basisconcepten EN eindige modulaire automaat ... Handleiding voor technische vertalers

toegankelijkheidsstatusmachine- (ITU T Y.1711). Handleiding voor technische vertalers

Onderwerpen: telecommunicatie, basisconcepten EN beschikbaarheid state machineASM... Staatsmachine met geheugen

- Een eindige toestandsmachine met geheugen is een wiskundig model van een apparaat waarvan het gedrag afhangt van zowel de invoervoorwaarden als de voorgaande toestand. Om een ​​eindige automaat met geheugen te beschrijven, worden de talen van operatorschema's, reguliere... ... Wikipedia gebruikt deterministische eindige toestandsmachine Handleiding voor technische vertalers

- - [Ya.N.Luginsky, M.S.Fezi Zhilinskaya, Yu.S.Kabirov. Engels-Russisch woordenboek voor elektrotechniek en energietechniek, Moskou, 1999] Onderwerpen van elektrotechniek, basisconcepten EN eindige deterministische automaat ... Moore-machine

- (automaat van de tweede soort) in de rekentheorie, een eindige automaat, waarvan de uitgangswaarde van het signaal alleen afhangt van de huidige toestand van de gegeven automaat, en niet direct afhankelijk is, in tegenstelling tot de Mealy-automaat, van de invoerwaarden. De automaat van Moore heet... Wikipedia Annotatie:

De twee meest gebruikelijke manieren om een ​​formele taal af te ronden zijn grammatica's en automaten. In deze context zijn automaten wiskundige modellen van bepaalde computerapparatuur. Deze lezing bespreekt eindige toestandsmachines die overeenkomen met rechtslineaire grammatica's in de Chomsky-hiërarchie. Sterker computationele modellen wordt later gedefinieerd in de hoorcolleges "10", "14" en "15". De term "automaattaal" is gereserveerd voor talen die specifiek worden herkend door eindige-toestandsmachines, en niet door een bredere familie van automaten (bijvoorbeeld winkelgeheugenautomaten of lineair begrensde automaten).

Paragraaf 2.1 definieert de concepten van een toestandsmachine (voor de duidelijkheid: zo'n machine kan een niet-deterministische toestandsmachine worden genoemd) en een taal die door de toestandsmachine wordt herkend. De volgende sectie geeft een andere, maar gelijkwaardige definitie van de taal die door een toestandsmachine wordt herkend. Het is niet nodig voor verdere presentatie, maar het is deze definitie die kan worden gegeneraliseerd naar de gevallen van automaten van andere typen.

In paragraaf 2.3 bewijzen we dat dezelfde klasse automatentalen kan worden verkregen met alleen eindige toestandsmachines van een speciaal type (ze lezen precies één symbool bij elke klokcyclus en hebben precies één begintoestand). In veel leerboeken zijn dit precies de machines die eindige automaten worden genoemd.

Een hele reeks klassieke resultaten in de theorie van formele talen bestaat uit stellingen over de exacte correspondentie van bepaalde klassen grammatica's met bepaalde klassen automaten. De eerste stelling in deze reeks, die stelt dat rechtslineaire grammatica's precies automaattalen genereren, wordt bewezen in paragraaf 2.4.

Een andere reeks resultaten houdt verband met de mogelijkheid om een ​​bepaalde klasse grammatica's te verkleinen zonder de klasse van talen die ze genereren te veranderen. Meestal worden grammatica's uit de kleinere klasse in dit geval grammatica's in normale vorm genoemd. Paragraaf 2.5 * formuleert een dergelijk resultaat voor rechtslineaire grammatica's. Deze stelling op zichzelf is niet van groot belang, maar vergelijkbare resultaten die later werden bewezen voor contextvrije grammatica's worden in veel bewijzen en algoritmen gebruikt.

Niet alle eindige toestandsmachines zijn geschikt voor het construeren van herkenningsinrichtingen die geschikt zijn voor praktische toepassingen, aangezien dit in het algemeen het geval is Zie wat een “Finite State Machine” is in andere woordenboeken: geeft geen precieze instructies over wat te doen bij de volgende stap, maar zorgt ervoor dat het rekenproces op verschillende manieren kan doorgaan. Dit nadeel is niet aanwezig bij deterministische eindige-toestandsmachines (een speciaal geval van niet-deterministische eindige-toestandsmachines) zoals gedefinieerd in paragraaf 2.6. In paragraaf 2.7 bewijzen we dat elke automaattaal wordt gegeven door een deterministische eindige automaat.

2.1. Niet-deterministische eindige-toestandsmachines

Definitie 2.1.1. - CA Rekenmodel dat een automaat beschrijft met een eindig aantal toestanden. CA's worden veel gebruikt bij het programmeren, bijvoorbeeld in lexicale analysatoren van compilers.(eindige automaat, eindige toestandsmachine) is een vijf, waar is de finale alfabet invoeren(of gewoon alfabet) van een gegeven eindige automaat, en zijn eindige verzamelingen,

, . De elementen van Q worden genoemd staten(staat), elementen I - voorletter(begin)toestanden, elementen F - definitief of toestaan(definitieve, accepterende) staten. Als , dan heet het overgang(overgang) van p naar q, en het woord x is label(label) van deze overgang.

Voorbeeld 2.1.2. Laat Q = (1,2) , , ik = (1) , F = (2) ,

Dan - eindige toestandsmachine.

Opmerking 2.1.3. Eindige toestandsmachines kunnen worden weergegeven als toestandsdiagrammen(statusdiagram) (soms genoemd overgangsdiagrammen(overgangsdiagram)). In het diagram wordt elke toestand weergegeven door een cirkel en de overgang door een pijl. De pijl van p naar q, gelabeld met het woord x, laat zien wat de overgang van een bepaalde toestandsmachine is. Elke begintoestand wordt herkend door een korte pijl die ernaartoe leidt. Elke tolerante toestand is in het diagram gemarkeerd met een dubbele cirkel.

Voorbeeld 2.1.4. Het diagram toont de eindige toestandsmachine uit voorbeeld 2.1.2.

Opmerking 2.1.5. Als een eindige automaat meerdere overgangen heeft met een gemeenschappelijk begin en een gemeenschappelijk einde, dan worden dergelijke overgangen genoemd parallel. Soms worden parallelle overgangen in het toestandsdiagram van een eindige toestandsmachine weergegeven door één pijl. In dit geval worden overgangslabels weergegeven, gescheiden door komma's.

Voorbeeld 2.1.6. Het diagram toont opnieuw de toestandsmachine uit voorbeeld 2.1.2.

Definitie 2.1.7. Pad Het (pad) van een toestandsmachine is een tupel waar en voor elke i . In dit geval q 0 - het begin van de reis qn- einde van de weg N- pad lengte w 1 ...w n - padlabel.

Opmerking 2.1.8. Voor elke staat is er een pad. Het label is , het begin en het einde zijn hetzelfde.

Definitie 2.1.9. Het pad wordt genoemd succesvol als het begin van I is en het einde van F.

Voorbeeld 2.1.10. Beschouw de eindige toestandsmachine uit voorbeeld 2.1.2. Het pad is succesvol. Zijn label is baaab. De lengte van dit pad is 4.

Definitie 2.1.11. Woord w toegestaan(wordt geaccepteerd, wordt herkend) door een toestandsmachine M als dit het label is van een succesvol pad.

Definitie 2.1.12. Taal, herkenbaar eindige automaat M is een taal L(M) die bestaat uit de labels van alle succesvolle paden (dat wil zeggen, van alle woorden die door deze automaat zijn toegestaan). We zullen ook zeggen dat de automaat M herkent(herkent, accepteert) taal L(M).

Opmerking 2.1.13. Als , en vervolgens de taal die wordt herkend door de staatsmachine , bevat.

Voorbeeld 2.1.14. Laat , waarbij Q = (1,2) , , ik = (1) , F = (1,2) ,

Definitie 2.1.15. Twee staatsmachines equivalent, als ze dezelfde taal herkennen.

Definitie 2.1.16. De taal L wordt genoemd automatisch(eindige toestandstaal) als er een eindige toestandsmachine is die deze taal herkent.

Opmerking 2.1.17. Normaal gesproken gebruiken leerboeken een engere definitie van een niet-deterministische eindige automaat, maar dit verandert niets aan de klasse van automatentalen (zie Lemma 2.3.3.).

Voorbeeld 2.1.18. Overweeg een alfabet van één letter. Voor elke vaste en taal gebeurt automatisch.

Opmerking 2.1.19. Elke eindige taal is een automaat.

Definitie 2.1.20. Staat q haalbaar(bereikbaar) vanuit toestand p als er een pad is waarvan het begin p is en het einde q.

Lemma 2.1.21. Elke automaattaal wordt herkend door een eindige toestandsmachine, waarin elke toestand bereikbaar is vanuit een begintoestand en vanuit elke toestand ten minste één eindtoestand bereikbaar is.

Voorbeeld 2.1.22. Beschouw een eindige toestandsmachine , waarbij Q = (1,2,3,4), , Ik = (1,2,4) , F = (1,3,4) ,

Lezing 5.

Deterministische eindige-toestandsmachines

Discreet-deterministische modellen ( F-schema's)

Basisrelaties. Laten we de kenmerken van de discreet-deterministische benadering bekijken aan de hand van het voorbeeld van het gebruik van de automatentheorie als wiskundig apparaat. Het systeem wordt weergegeven in de vorm van een automaat als een apparaat met invoer- en uitvoersignalen, dat discrete informatie verwerkt en de interne status ervan alleen op acceptabele tijdstippen verandert. Staatsmachine is een automaat waarvan de sets van interne toestanden, ingangs- en uitgangssignalen eindige sets zijn.

Abstract gezien kan een eindige automaat worden weergegeven als een wiskundig circuit ( F-diagram), gekenmerkt door zes elementen: een eindige verzameling X ingangssignalen (invoeralfabet); eindige verzameling Y uitgangssignalen (uitvoeralfabet); eindige verzameling Z interne toestanden (intern alfabet of alfabet van toestanden); initiële staat z 0 , z 0 Î Z; overgangsfunctie j( z, X); uitvoerfunctie y( z, X). Automaat gespecificeerd F-schema: F = á Z, X, Y, y, j, z 0 ñ, werkt in discrete tijd, waarvan de momenten klokcycli zijn, die elk overeenkomen met constante waarden van de ingangs- en uitgangssignalen en interne toestanden. Laten we de staat aangeven, evenals de ingangs- en uitgangssignalen die daarmee corresponderen T-de slag op T= 0, 1, 2, …, door z(T), X(T), j(T). Bovendien, afhankelijk van de voorwaarde z(0) = z 0, een z(T)Î Z, X(T)Î X, j(T)Î Y.

Voorbeeld. De eenvoudigste automaat van leeuwengedrag.

Invoeralfabet: "antilope", "jager".

Interne staten: “vol”, “hongerig”.

Uitvoeralfabet: "eten", "slaap", "weglopen"

Overgangstabel:

Een abstracte toestandsmachine heeft één invoer- en één uitvoerkanaal. Op elk moment T= 0, 1, 2, … discrete tijd F- de machine bevindt zich in een bepaalde staat z(T) van velen Z toestanden van de machine, en op het eerste moment T= 0, het bevindt zich altijd in de beginstatus z(0) = z 0 . Op dit moment T, kunnen z(T), kan de machine een signaal ontvangen op het ingangskanaal X(T)Î X en een signaal op het uitgangskanaal uitvoeren j(T) = jij[ z(T), X(T)], overgaand in toestand z( T+1) = J[ z(T), X(T)], z(T)Î Z, j(T)Î Y. Een abstracte eindige machine implementeert een mapping van een reeks woorden van het invoeralfabet X voor veel woorden van het uitvoeralfabet Y. Met andere woorden, als de invoer van een eindige-toestandsmachine wordt ingesteld op de begintoestand z 0 , voer letters van het invoeralfabet in een bepaalde volgorde in X(0), X(1), X(2), ..., d.w.z. invoerwoord, dan verschijnen de letters van het uitvoeralfabet opeenvolgend aan de uitgang van de machine j(0), j(1), j(2), ..., die het uitgangswoord vormt.

De werking van de eindige toestandsmachine vindt dus plaats volgens het volgende schema: in elk T e cyclus naar de ingang van de machine, die zich in de staat bevindt z(T), wordt er een signaal gegeven X(T), waarop het reageert met een overgang ( T+1)-de cyclus naar een nieuwe staat z(T+1) en produceert een uitgangssignaal. Het bovenstaande kan worden beschreven door de volgende vergelijkingen: voor F-automaat van de eerste soort, ook wel genoemd Automatische kilometers,

z(T+1) = j[ z(T), X(T)], T= 0, 1, 2, …; (2.15)

j(T) = y[ z(T), X(T)], T= 0, 1, 2, …; (2.16)

Voor F-automatische machine van het tweede type

z(T+1) = j[ z(T), X(T)], T= 0, 1, 2, …; (2.17)

j(T) = y[ z(T), X(T - 1)], T= 1, 2, 3,…. (2.18)

Automaten van de tweede soort, waarvoor

j(T) = y[ z(T)], T= 0, 1, 2, …, (2.19)

die. de uitvoerfunctie is niet afhankelijk van de invoervariabele X(T), genaamd Moore-machinegeweer.

Vergelijkingen (2.15)-(2.19) zijn dus volledig definiërend
F-automaat is een speciaal geval van vergelijkingen (2.3) en (2.4), wanneer
systeem S– deterministisch en de enige invoer ervan ontvangt een discreet signaal X.

Op basis van het aantal toestanden worden eindige toestandsmachines onderscheiden met en zonder geheugen. Automaten met geheugen hebben meer dan één status, terwijl automaten zonder geheugen (combinatie of logische circuits) slechts één status hebben. Bovendien is de werking van het combinatorische circuit volgens (2.16) dat het elk ingangssignaal toewijst X(T) gedefinieerd uitgangssignaal j(T), d.w.z. implementeert een logische functie van het formulier

j(T) = y[ X(T)], T= 0, 1, 2, … .

Deze functie wordt Boolean genoemd als het alfabet X En Y, waartoe de signaalwaarden behoren X En j, bestaat uit twee letters.

Gebaseerd op de aard van discrete tijdtelling, worden eindige toestandsmachines onderverdeeld in synchroon en asynchroon. Synchronisch F Bij automatische machines worden de momenten waarop de machine de ingangssignalen “leest” bepaald door geforceerde synchronisatiesignalen. Na het volgende synchronisatiesignaal vindt, rekening houdend met de "lees" en in overeenstemming met vergelijkingen (2.15)-(2.19), een overgang naar een nieuwe toestand plaats en wordt een signaal afgegeven aan de uitgang, waarna de machine de volgende kan waarnemen waarde van het ingangssignaal. De reactie van de machine op elke waarde van het ingangssignaal eindigt dus in één klokcyclus, waarvan de duur wordt bepaald door het interval tussen aangrenzende synchronisatiesignalen. Asynchroon F-de machine leest het ingangssignaal continu en reageert daarom op een voldoende lang ingangssignaal van constante waarde X, kan het, zoals volgt uit (2.15)-(2.19), zijn toestand verschillende keren veranderen, waarbij het overeenkomstige aantal uitgangssignalen wordt geproduceerd, totdat het stabiel wordt, wat niet langer kan worden veranderd door een gegeven ingangssignaal.

Mogelijke toepassingen F-schema's. Om het einde vast te stellen F-automaat, het is noodzakelijk om alle elementen van de set te beschrijven F= <Z, X, Y, y, j, z 0 >, d.w.z. invoer-, interne en uitvoeralfabetten, evenals functies van overgangen en uitvoer, en onder de vele staten is het noodzakelijk om de staat te selecteren z 0 waarin de machine zich in de staat bevindt T= 0. Er zijn verschillende manieren om werk te specificeren F-automaten, maar de meest gebruikte zijn tabellarische, grafische en matrixautomaten.

In de tabellarische methode worden tabellen met overgangen en uitgangen gespecificeerd, waarvan de rijen overeenkomen met de ingangssignalen van de machine, en de kolommen - de toestanden ervan. De eerste kolom aan de linkerkant komt overeen met de begintoestand z 0 . Op het kruispunt i e lijn en k de e kolom van de transitietabel bevat de corresponderende waarde j( z k, x ik) overgangsfuncties, en in de uitvoertabel - de overeenkomstige waarde y( zk,x ik) uitvoerfuncties. Voor F-Moore's automaat beide tafels kunnen gecombineerd worden.

Functieomschrijving F-Een Mealy-automaat met tabellen met overgangen j en uitgangen y wordt geïllustreerd in tabel. 2.1, en de beschrijving F-Moore-automaat – overgangstabel (tabel 2.2).

Tabel 2.1

Overgangen
	J( z 0 , X 1)	J( z 1 , X 1)		J( z k,X 1)
	J( z 0 , X 2)	J( z 1 , X 2)		J( z k,X 2)
	J( z 0 , x ik)	J( z 1 , x ik)		J( z k,x ik)
Uitgangen
	y( z 0 , X 1)	y( z 1 , X 1)		y( z k, X 1)
	y( z 0 , X 2)	y( z 1 , X 2)		y( z k, X 2)
	y( z 0 , x ik)	y( z 1 , x ik)		y( z k, x ik)

Tabel 2.2

	J( z 0 , X 1)	J( z 1 , X 1)		J( z k, X 1)
	J( z 0 , X 2)	J( z 1 , X 2)		J( z k, X 2)
	J( z 0 , x ik)	J( z 1 , x ik)		J( z k, x ik)

Voorbeelden van de toewijzingsmethode in tabelvorm F-automatische Mili F 1 zijn weergegeven in de tabel. 2.3, en voor F-Moore-machinegeweer F 2 – in tabel. 2.4.

Tabel 2.3

Overgangen
Uitgangen

Tabel 2.4

Bij het grafisch specificeren van een eindige automaat wordt het concept van een gerichte graaf gebruikt. De grafiek van een automaat is een reeks hoekpunten die overeenkomen met verschillende toestanden van de automaat en die de hoekpunten van de grafiekbogen verbinden die overeenkomen met bepaalde overgangen van de automaat. Als het ingangssignaal x k veroorzaakt een staatstransitie z ik in een staat z j, dan is er op de automaatgrafiek een boog die het hoekpunt verbindt z ik met bovenkant z j, aangegeven x k. Om de uitgangsfunctie te specificeren, moeten de bogen van de grafiek worden gemarkeerd met de overeenkomstige uitgangssignalen. Voor Mili-machines gebeurt deze markering als volgt: als het ingangssignaal x k beïnvloedt de staat z ik, dan krijgen we een boog die uitgaat van z ik en gemarkeerd x k; deze boog wordt bovendien gemarkeerd met een uitgangssignaal j= y( z ik, x k). Voor een Moore-machine is een soortgelijke grafiekindeling als volgt: als het ingangssignaal x k, die inwerkt op een bepaalde toestand van de automaat, veroorzaakt een overgang naar de staat z j, dan is de boog gericht naar z ik en gemarkeerd x k, bovendien gevierd als een vrije dag
signaal j= y( z j, x k).

In afb. 2.4. A, B worden gegeven door de eerder gespecificeerde tabellen F-Mili-machines F 1 en Moor F 2 respectievelijk.

Rijst. 2.4. Grafieken van automaten a – Mealy en b – Moore

Bij een matrixspecificatie van een eindige automaat is de verbindingsmatrix van de automaat vierkant MET=||Metij||, rijen komen overeen met begintoestanden en kolommen komen overeen met overgangstoestanden. Element Metij = x k/y s, staande op de kruising
i e lijn en J de e kolom komt in het geval van een Mili-machine overeen met het ingangssignaal x k, waardoor een overgang van de staat ontstaat z ik in een staat z j en het uitgangssignaal y s, uitgegeven tijdens deze overgang. Voor machine Mili F 1, hierboven besproken, heeft de verbindingsmatrix de vorm:

X 2 /j 1 – X 1 /j 1

C 1 = X 1 /j 1 – X 2 /j 2 .

X 1 /j 2 X 2 /j 1 –

Voor F-Moore-automaatelement Metij gelijk aan de set ingangssignalen bij de overgang ( z ik,z j), en de uitvoer wordt beschreven door de uitvoervector

= y( z k) ,

i-de component daarvan is het uitgangssignaal dat de toestand aangeeft z ik.

Voor het bovenstaande F-Moore-machinegeweer F2 verbindingsmatrices en uitvoervector hebben de vorm:

– X 1 – X 2 –bij 1

– X 2 – – X 1 bij 1

C 2 = – X 2 – – X 1 ; = j 3

X 2 – X 1 – –bij 2

X 2 – X 1 – –bij 3

Voor deterministische automaten is voldaan aan de voorwaarde van ondubbelzinnige overgangen: een automaat die zich in een bepaalde toestand bevindt, kan onder invloed van welk ingangssignaal dan ook niet naar meer dan één toestand overgaan. Met betrekking tot de grafische toewijzingsmethode F-van een automaat betekent dit dat in de grafiek van een automaat twee of meer randen gemarkeerd door hetzelfde ingangssignaal geen enkel hoekpunt kunnen verlaten. En in de matrix van verbindingen van de machine MET Op elke regel mag een ingangssignaal niet vaker dan één keer voorkomen.

Het concept in de discreet-deterministische benadering van het bestuderen van de eigenschappen van objecten met behulp van modellen is dus een wiskundige abstractie, handig voor het beschrijven van een brede klasse van processen van het functioneren van echte objecten in geautomatiseerde besturingssystemen. Door te gebruiken F- automaat is het mogelijk objecten te beschrijven die worden gekenmerkt door de aanwezigheid van discrete toestanden en de discrete aard van werk in de tijd - dit zijn computerelementen en knooppunten, besturings-, regel- en besturingsapparaten, tijd- en ruimtelijke schakelsystemen in de technologie voor informatie-uitwisseling enz.

Voorbeeld van modellering met behulp van eindige toestandsmachines

Een voorbeeld van het construeren van een eindige toestandsmachine (processor)

voor het herkennen en verwerken van de registratie van reële getallen

Aan de ingang van de machine: een tekenreeks die een niet-ondertekend reëel getal vertegenwoordigt.

Aan de uitgang van de machine: een paar gehele getallen: mantisse en exponent, of een foutmelding als het getal verkeerd is geschreven.

Voorbeeld.

1. 38,71 E-42 → (3871, -44);

2. .9 E 21 → (9, 20);

3. 4.5.6 .9→ Fout;

4. 3.E4 → (3, 4);

5. 12 → (12, 0);

6. 1.2 → (12, -1).

In dit voorbeeld laten we een voorbeeld zien voor het oplossen van het probleem van het construeren van een eindige herkenningsmachine en een verwerkingsprocessor. Laten we dit proces in verschillende fasen opsplitsen.

1.Schrijf een of meerdere voorbeelden op karakteristiek ketens op basis waarvan:

a) bepaal het invoeralfabet;

b) teken onder de symbolen van de staatsketens, die de werking van de machine simuleren;

c) schrijf verbale beschrijvingen van toestanden op.

a) Voer het alfabet inA=(t E. + -); (waarbij c het getal 0..9 is)

b) Voorbeelden.

Invoerketen: 3 8 . 7 1 E – 4 2

Machinetoestanden: Ø 1 1 2 3 3 4 5 6 6

Invoerketen: . 9 E 2 1.

Machinetoestanden: Ø7 3 4 6 6.

c) Ø begintoestand; wachtend op het mantissecijfer of de punt.

1 – het cijfer van het eerste deel van de mantisse wordt gelezen; wachten op een ander nummer of punt, of symbool E.

2 – punt lezen; wachten op een gebroken cijfer of symbool E.

3 – het cijfer van het fractionele deel van de mantisse wordt gelezen; wachten op een ander nummer of symbool E.

4 – symbool E lezen; wachten op +, - of exponentcijfers.

5 – het orderbord wordt gelezen; wachten op het bestelnummer.

6 – het ordernummer wordt gelezen; wachten op een ander nummer.

7 – de punt wordt gelezen als het eerste teken van de invoerketen; wachten op het vereiste cijfer van het fractionele deel van de mantisse.

ER- foutstatus.

2. Construeer een circuit- en overgangstabel van een eindige toestandsmachine.

Alle overgangen die niet met pijlen zijn gemarkeerd, leiden naar de Er-foutstatus.

					Ontvankelijkheid
ER

Hier komen alle lege cellen overeen met een overgang naar de Er-foutstatus.

3.Breng de resulterende automaat naar zijn minimale vorm.

Er zijn speciale wiskundige methoden waarmee u eindige toestandsmachines kunt optimaliseren, dat wil zeggen om redundante toestanden van de machine te vinden. Er zijn algoritmen om de automaat tot een minimale vorm terug te brengen. Uit de resultaten van de toepassing van een dergelijk algoritme volgt de gelijkwaardigheid van toestanden 2 ~ 3.

Het is gemakkelijk om te verifiëren dat alle toestanden bereikbaar zijn door naar het overgangsdiagram van de machine te kijken. Om dus een minimaal gereduceerde automaat te verkrijgen, moet factorisatie worden uitgevoerd door toestanden 2 en 3 te combineren.

Voor het gemak van een verdere beschrijving hernoemen we de staten als volgt:

Hieronder vindt u het nieuwe diagram en de transitietabel van de statusmachine.

Nieuwe transitietabel:
ER

Processorprocedureaanroeptabel:
	2 A		7 A
	2 B	4 A	3 A
	3 B	4 B
	6 A			5 A
	6 B
	6 C
	3 C
ER

4. Bouw een processor die het einderegelteken verwerkt.

(In de tabel komen alle lege cellen overeen met een aanroep van de “NO”-procedure, die de invoerketen verwerpt). De Ja-procedure beëindigt de werking van de machine, accepteert de invoerketen en produceert het resultaat van de verwerking ervan.

5. Vul processorovergangen aan met procedurenamen.

Voor het gemak wordt in dit geval de naam van de procedure gevormd uit het nummer van de staat waarin de machine gaat, aangevuld met een serieletter van het Latijnse alfabet (zie ook het diagram in de figuur).

Opmerking: als de processor een foutmelding moet geven, moet u aanduidingen invoeren voor de procedures voor het verwerken van elk type fout, en daarmee alle lege cellen van de tabel invullen.

6. Voer de benodigde registers in: variabelen die de machine nodig heeft om het resultaat te verkrijgen.

Nummer – register van het significante deel van een getal (geheel getal).

Volgorde– orderregister (geheel getal).

Balie– register van de teller van cijfers na (geheel getal).

Teken- (±1) – orderteken.

7. Beschrijf de procedures die zijn aangeroepen in overeenstemming met de tabel en het verwerken van de waarden van processorregisters.

2a: Nummer:= c

2c: Nummer := 10 * Nummer+ c

3a: Balie := 0

3c: Balie := Balie + 1

Nummer := 10 * Nummer+ c

3c: Nummer:= c; Balie =: 1

4a: Balie =: 0

5a: Teken:= (+1 als a=’+’ of -1 als a=’-‘) (hier is a het invoersymbool.)

6a: Teken := +1

Volgorde:= c

6c: Volgorde:= c

6s: Volgorde := 10 * Volgorde+ c

Ja1: Volgorde := 0

Ja2: Volgorde:= -Teller

Ja3: Volgorde := Teken * Volgorde - Balie

Hier geeft het symbool Æ de afwezigheid van enige actie aan - een lege procedure. In gevallen waarin aan een geheel getalregister een teken is toegewezen (bijvoorbeeld: Balie=ts), bedoelen we de impliciete conversie van een cijfersymbool naar het getal dat het aangeeft.

7. Controleer de werking van de machine (procedure) op één of meerdere kettingen, zodat elke overgang van de machine minimaal één keer wordt uitgevoerd.

Beschouw als voorbeeld de werking van de machine bij het verwerken van de volgende drie invoerketens. De verwachte waarde van de nummer- en volgorderegisters bij de processoruitgang wordt tussen haakjes aangegeven.

a) 67.89E-12┤ (6789, -14)

b) 2E3┤ (2,3)

c) .89┤ (3,-1)

Invoersymbool	Overgang naar staat, procedure	Registreer waarden
		Nummer	Volgorde	Balie	Teken
	1 (initieel)
		6
		67
		67		0
		678		1
		6789		2
					-1
		6789	-14
	1 (initieel)
		2
				0
			3		+1
		2	3
	1 (initieel)
		8		1
		89
		89	-2

Vandaag zullen we het hebben over machinegeweren, maar zeker niet over machinegeweren die in handen worden gehouden van soldaten van het Russische leger. We zullen het hebben over zo'n interessante stijl van programmeren van microcontrollers als automatisch programmeren. Om precies te zijn, dit is niet eens een programmeerstijl, maar een heel concept, waardoor een microcontroller-programmeur zijn leven veel gemakkelijker kan maken. Hierdoor worden veel taken die aan de programmeur worden gepresenteerd veel eenvoudiger en eenvoudiger opgelost, waardoor de programmeur hoofdpijn krijgt. Er wordt trouwens vaak automatisch programmeren genoemd SWITCH-technologie.

Ik zou willen opmerken dat de inspiratie voor het schrijven van dit bericht was serie artikelen over SWITCH-technologie Vladimir Tatarchevski. De serie artikelen heet “Gebruik van SWITCH-technologie bij het ontwikkelen van applicatiesoftware voor microcontrollers.” Daarom zal ik in dit artikel proberen vooral een voorbeeld te geven van werkende code en de beschrijving ervan.

Ik heb trouwens een aantal artikelen gepland die gewijd zijn aan programmeren, waarin ik de programmeertechnieken voor AVR-microcontrollers in detail zal bespreken, mis het niet…. Nou, laten we gaan!

Het programma voert consequent de opdrachten uit die door de programmeur zijn toegewezen. Voor een gewoon computerprogramma is het volkomen normaal dat het programma wordt uitgevoerd en de uitvoering ervan stopt, terwijl de resultaten van zijn werk op de monitor worden weergegeven.

Een microcontrollerprogramma kan de uitvoering ervan niet zomaar voltooien. Stel je voor dat je de speler of bandrecorder hebt aangezet. Je drukte op de aan/uit-knop, selecteerde het gewenste nummer en geniet van de muziek. Toen de muziek echter niet meer door het trommelvlies van je oor trilde, bevroor de speler en reageerde op geen enkele manier op het indrukken van knoppen, laat staan ​​op jouw dansen met een tamboerijn.

Wat is daar mis mee? Alles is in orde: de controller, die zich diep in uw speler bevindt, is zojuist klaar met het uitvoeren van zijn programma. Zie je, het is op de een of andere manier lastig.

Hieruit concluderen we dus dat het programma voor de microcontroller simpelweg niet mag stoppen. In wezen zou het een eindeloze lus moeten zijn - alleen in dit geval zou onze speler correct werken. Vervolgens zal ik je laten zien welke soorten programmacodeontwerpen er zijn voor microcontrollers; dit zijn niet eens ontwerpen, maar enkele programmeerstijlen.

Programmeerstijlen.

“Programmeerstijlen” ​​klinkt op de een of andere manier onbegrijpelijk, maar ach. Wat wil ik hiermee zeggen? Laten we ons voorstellen dat iemand nog nooit eerder heeft geprogrammeerd, dat wil zeggen dat hij een totale noob is.

Deze persoon heeft veel boeken over programmeren gelezen en alle basisconstructies van de taal bestudeerd.Hij verzamelde informatie beetje bij beetje, aangezien de toegang tot informatie nu onbeperkt is. Allemaal leuk en aardig, maar hoe zullen zijn eerste programma's eruitzien? Het lijkt mij dat hij niet zal filosoferen, maar het pad zal volgen van eenvoudig naar complex.

Deze stijlen zijn dus de stappen die leiden van een eenvoudig niveau naar een complexer, maar tegelijkertijd effectiever niveau.

In eerste instantie dacht ik niet aan de ontwerpkenmerken van het programma. Ik vormde eenvoudigweg de logica van het programma: tekende een stroomdiagram en schreef code. Daarom liep ik steeds tegen een hark aan. Maar dit was de eerste keer dat ik me geen zorgen maakte en de “eenvoudige looping”-stijl gebruikte, toen begon ik interrupts te gebruiken, toen waren er automatische machines en daar gingen we...

1. Eenvoudige lusvorming. In dit geval loopt het programma zonder enige trucjes door, en dit heeft zijn voor- en nadelen. Het enige voordeel is de eenvoud van de aanpak, je hoeft geen sluwe ontwerpen te bedenken, je schrijft zoals je denkt (geleidelijk je eigen graf graven).

Void main(void) ( initial_AL(); // initialiseren van de periferie while(1) ( Leds_BLINK(); //LED-knipperfunctie signal_on(); //functie voor het inschakelen van het signaal signal_off(); //functie voor inschakelen uit het signaal l=knop( ); //variabele verantwoordelijk voor het indrukken van de knoppen switch(l) //Afhankelijk van de waarde van de variabele wordt een of andere actie uitgevoerd ( geval 1: ( Deistvie1(); //In plaats van een functie kan een voorwaardelijke operator zijn Deistvie2(); //of anders wisselen meerdere takken van geval 2: ( Deistvie7(); Deistvie9(); . . ) ) )

Het werkpunt van het programma beweegt in volgorde. In dit geval worden alle acties, voorwaarden en cycli opeenvolgend uitgevoerd. De code begint te vertragen, je moet veel extra voorwaarden invoegen, wat de perceptie bemoeilijkt.

Dit alles brengt het programma enorm in verwarring, waardoor de code een wirwar van voorwaarden wordt. Als gevolg hiervan kan er niets aan deze code worden toegevoegd of weggenomen; het wordt een monolithisch stuk. Als het volume niet groot is, kan de code natuurlijk worden aangepast, maar hoe verder je gaat, hoe moeilijker het wordt.

Met deze aanpak heb ik verschillende programma's geschreven; ze waren niet groot en behoorlijk functioneel, maar de duidelijkheid liet veel te wensen over. Om een ​​nieuwe voorwaarde toe te voegen, moest ik de hele code doorzoeken, omdat alles vastzat. Dit zorgde voor veel fouten en kopzorgen. De compiler vloekte zo goed als hij kon, en het debuggen van zo'n programma werd een hel.

2. Lus + onderbrekingen.

De eindeloze remcyclus kun je deels oplossen door gebruik te maken van interrupts. Interrupts helpen bij het doorbreken van een vicieuze cirkel, helpen een belangrijke gebeurtenis niet te missen en voegen extra functionaliteit toe (interrupts van timers, externe interrupts).

Stel dat u een interrupt kunt gebruiken om knoppen te verwerken of een belangrijke gebeurtenis te volgen. Het resultaat is dat het programma visueler maar niet minder verwarrend wordt.

Helaas zal onderbreken u niet redden van de puinhoop waar het programma in verandert. Wat één geheel is, is onmogelijk in delen te verdelen.

3. Automatische programmering.

Hier komen we bij het hoofdonderwerp van dit artikel. Programmeren in eindige toestandsmachines elimineert de nadelen die inherent zijn aan de eerste twee voorbeelden. Het programma wordt eenvoudiger en gemakkelijk aan te passen.

Een programma dat in automatische stijl is geschreven, lijkt op een schakelaar, die, afhankelijk van de omstandigheden, naar de ene of de andere staat overschakelt. Het aantal toestanden is in eerste instantie bekend bij de programmeur.

Grofweg gesproken is het als een lichtschakelaar. Er zijn twee toestanden aan en uit, en twee toestanden aan en uit. Nou ja, de eerste dingen eerst.

Implementatie van multitasking in de schakeltechniek.

De microcontroller kan de belasting, knipperende LED's, toetsaanslagen volgen en nog veel meer. Maar hoe doe je dit allemaal tegelijkertijd? Er zijn veel oplossingen om dit probleem op te lossen. De eenvoudigste die ik al heb genoemd, is het gebruik van interrupts.

Wanneer tijdens de werking van het programma een onderbreking optreedt, wordt de controller afgeleid van het uitvoeren van de programmacode en voert hij kortstondig een ander deel van het programma uit waarvoor de onderbreking verantwoordelijk is. De onderbreking zal werken, waarna het programmawerkpunt verdergaat vanaf het punt waar de controller werd onderbroken door de onderbreking (het woord zelf geeft aan dat de controller is onderbroken).

Een andere manier om multitasking te implementeren is door besturingssystemen te gebruiken. Ja, er zijn inderdaad al kleine besturingssystemen verschenen die kunnen worden gebruikt op een controller met laag vermogen. Maar vaak blijkt deze methode enigszins overbodig. Waarom zou je tenslotte de middelen van de controller verspillen met onnodig werk als je met weinig kosten rond kunt komen?

In programma's die zijn geschreven met behulp van switchtechnologie wordt dankzij het berichtensysteem een ​​soortgelijke ‘illusie’ van multitasking verkregen. Ik schreef ‘illusie’ omdat dit feitelijk het geval is, omdat een programma fysiek niet verschillende delen van de code tegelijkertijd kan uitvoeren. Ik zal het nog wat verder hebben over het berichtensysteem.

Berichtensysteem.

Met een berichtensysteem kunt u talloze processen oplossen en de illusie van multitasking creëren.

Laten we zeggen dat we een programma nodig hebben waarin de LED wordt geschakeld. Hier hebben we twee machines, laten we ze LEDON noemen - de machine die verantwoordelijk is voor het inschakelen van de LED en de LEDOFF-machine - de machine die verantwoordelijk is voor het uitschakelen van de LED.

Elk van de machines heeft twee toestanden, dat wil zeggen dat de machine zich in een actieve of inactieve toestand kan bevinden, zoals een schakelaar aan of uit.

Wanneer de ene machine wordt geactiveerd, gaat de LED branden, en wanneer de andere wordt geactiveerd, gaat de LED uit. Laten we een klein voorbeeld bekijken:

Int main(void) ( INIT_PEREF(); //initialisatie van randapparatuur (LED's) InitGTimers(); //initialisatie van timers InitMessages(); //initialisatie van het berichtverwerkingsmechanisme InitLEDON(); //initialisatie van de LEDON-machine InitLEDOFF(); // initialisatie van de LEDOFF-machine SendMessage(MSG_LEDON_ACTIVATE); //activeer de LEDON-machine sei(); //Enable interrupts //Hoofdlus van het programma while(1) ( ProcessLEDON(); //iteratie van de LEDON-machine ProcessLEDOFF();//iteratie van de LEDOFF-machine ProcessMessages (//berichtverwerking);

In regels 3-7 komen verschillende initialisaties voor, dus daar zijn we nu niet bijzonder in geïnteresseerd. Maar dan gebeurt het volgende: voordat we de hoofdlus starten (while(1)), sturen we een bericht naar de machine

Bericht verzenden(MSG_LEDON_ACTIVATE)

verantwoordelijk voor het aansteken van de LED. Zonder deze kleine stap zal ons orgel niet werken. Vervolgens doet de hoofd-oneindige while-lus het hoofdwerk.

Een kleine uitweiding:

Het bericht heeft drie statussen. De berichtstatus kan namelijk inactief zijn, ingesteld maar inactief en de actieve status.

Het blijkt dat het bericht in eerste instantie inactief was, toen wij het bericht verzonden kreeg het de status “geïnstalleerd maar inactief”. En dit levert ons het volgende op. Wanneer het programma sequentieel wordt uitgevoerd, ontvangt de LEDON-machine het bericht niet. Er vindt een inactieve iteratie van de LEDON-machine plaats waarbij het bericht eenvoudigweg niet kan worden ontvangen. Omdat het bericht de status 'geïnstalleerd maar inactief' heeft, gaat het programma verder met de uitvoering ervan.

Nadat alle machines inactief zijn, komt de beurt aan de functie ProcessMessages(). Deze functie wordt altijd aan het einde van de lus geplaatst, nadat alle iteraties van de automaten zijn voltooid. De functie ProcessMessages() verplaatst eenvoudigweg een bericht van de status "ingesteld maar inactief" naar de status "actief".

Wanneer de oneindige lus de tweede ronde voltooit, wordt het beeld compleet anders. De iteratie van de ProcessLEDON-machine zal niet langer inactief zijn. De machine kan het bericht ontvangen, in een verlichte toestand gaan en op zijn beurt ook een bericht verzenden. Het wordt geadresseerd aan de LEDOFF-machine en de levenscyclus van het bericht herhaalt zich.

Ik zou willen opmerken dat berichten met de status "actief" worden vernietigd wanneer ze de functie ProcessMessages tegenkomen. Daarom kan een bericht slechts door één machine worden ontvangen. Er is nog een ander soort bericht: uitgezonden berichten, maar ik zal ze ook niet goed behandelen in de artikelen van Tatarchevsky;

Timers

Met behulp van de juiste organisatie van de berichtenuitwisseling kunnen we de werkingsvolgorde van eindige toestandsmachines controleren, maar met berichten alleen kunnen we dit niet doen.

Het is u waarschijnlijk opgevallen dat het vorige programmafragment dat als voorbeeld is gegeven, niet zal werken zoals bedoeld. De machines zullen berichten uitwisselen, de LED’s zullen schakelen, maar wij zullen het niet zien. We zien alleen een zwak verlichte LED.

Dit komt omdat we niet hebben nagedacht over hoe we op de juiste manier met vertragingen om kunnen gaan. Het is immers niet voldoende dat we de LED's afwisselend in- en uitschakelen; LED's moeten in elke toestand blijven hangen, bijvoorbeeld een seconde.

Het algoritme zal als volgt zijn:

Je kunt klikken om te vergroten

Ik vergat aan dit blokdiagram toe te voegen dat wanneer de timer is afgelopen, er natuurlijk een actie wordt uitgevoerd: de LED aansteken of doven.

1. We komen de staat binnen door een bericht te accepteren.

2. We controleren de timer-/tellerstanden, als de telling is bereikt, voeren we de actie uit, anders sturen we gewoon een bericht naar onszelf.

3. Stuur een bericht naar de volgende machine.

4. Afsluiten

Bij de volgende invoer wordt alles herhaald.

Programma over SWITCH-technologie. Drie stappen.

Laten we een programma schrijven in eindige toestandsmachines en hiervoor hoeven we slechts drie eenvoudige stappen te nemen. Het programma zal eenvoudig zijn, maar het is de moeite waard om met eenvoudige dingen te beginnen. Een programma met een schakelende LED past bij ons. Dit is een heel goed voorbeeld, dus laten we niets nieuws verzinnen.

Ik zal het programma in de SI-taal samenstellen, maar dit betekent helemaal niet dat je in eindige toestandsmachines alleen in C hoeft te schrijven; het is heel goed mogelijk om een ​​andere programmeertaal te gebruiken.

Ons programma zal modulair zijn en daarom in verschillende bestanden worden verdeeld. We zullen de volgende modules hebben:

• De module van de hoofdprogrammalus bevat de bestanden leds_blink.c, HAL.c, HAL.h
• Timermodule bevat bestanden timers.c, timers.h
• Berichtverwerkingsmodule bevat bestanden messages.c, messages.h
  
• Machinemodule 1 bevat bestanden ledon.c, ledon.h
• Machinemodule 2 bevat ledoff.c-bestanden, ledoff .h

Stap 1.

We maken een project en koppelen er onmiddellijk de bestanden van onze statische modules aan: timers.c, timers.h, messages.c, messages.h.

Bestand leds_blink.c van de module van de hoofdprogrammalus.

#include "hal.h" #include "messages.h" // berichtverwerkingsmodule #include "timers.h" // timers module // Timer onderbreekt //############ # ########################################## # ######################### ISR(TIMER0_OVF_vect) // spring langs de interruptvector (teller T0 timer overflow) ( ProcessTimers(); //Timer interrupt-handler) //################################### # ########################################## int main(void) ( INIT_PEREF(); //initialisatie van randapparatuur (LED's) InitGTimers(); //initialisatie van timers InitMessages(); //initialisatie van het berichtverwerkingsmechanisme InitLEDON(); //initialisatie van de LEDON-machine InitLEDOFF (); StartGTimer( TIMER_SEK); // Start de timer SendMessage (MSG_LEDON_ACTIVATE); // activeer de FSM1 sei (); // Schakel interrupts in // Hoofdlus van het programma while (1) ( ProcessLEDON (); // iteratie van de LEDON ProcessLEDOFF();

De eerste regels verbinden de overige modules met het hoofdprogramma. Hier zien we dat de timermodule en de berichtverwerkingsmodule met elkaar zijn verbonden. Het volgende in de programmatekst is de overflow-interruptvector.

Je zou kunnen zeggen dat het hoofdprogramma begint met de regel int main (void). En het begint met de initialisatie van alles. Hier initialiseren we de randapparatuur, dat wil zeggen dat we initiële waarden instellen voor de invoer-/uitvoerpoorten van de comparator en alle andere inhoud van de controller. Dit alles wordt gedaan door de INIT_PEREF-functie; we voeren het hier uit, hoewel de hoofdtekst zich in het hal.c-bestand bevindt.

Vervolgens zien we de initialisatie van timers, de berichtverwerkingsmodule en de initialisatie van automaten. Hier worden deze functies ook eenvoudigweg gestart, hoewel de functies zelf in de bestanden van hun modules zijn geschreven. Kijk hoe handig het is. De hoofdtekst van het programma blijft gemakkelijk te lezen en is niet volgestopt met overtollige code waar je benen van breken.

De hoofdinitialisaties zijn voorbij, nu moeten we de hoofdlus starten. Om dit te doen, sturen we een startbericht en winden we ook ons ​​horloge op: we starten de timer.

StartGTimer(TIMER_SEK); // Start de timer SendMessage (MSG_LEDON_ACTIVATE); // activeer machine FSM1

En de hoofdcyclus ziet er, zoals ik al zei, heel eenvoudig uit. We noteren de functies van alle machines, schrijven ze eenvoudigweg in een kolom, zonder de volgorde in acht te nemen. Deze functies zijn automatenhandlers en bevinden zich in automatenmodules. Deze automatische piramide wordt gecompleteerd door de functie van de berichtenverwerkingsmodule. Natuurlijk heb ik je dit al eerder verteld toen we het berichtenverzendsysteem behandelden. Nu kunt u zien hoe nog twee modulebestanden van de hoofdprogrammalus eruit zien

Hal.h is het headerbestand van de hoofdlusmodule van het programma.

#ifndef HAL_h #define HAL_h #include #erbij betrekken //Standaardbibliotheek inclusief interrupts #define LED1 0 #define LED2 1 #define LED3 2 #define LED4 3 #define Komparator ACSR //comparator #define ViklKomparator 1<

Zoals je misschien hebt gemerkt, bevat dit bestand inherent geen enkele regel uitvoerbare code; het zijn allemaal macrovervangingen en verbindende bibliotheken. Het hebben van dit bestand maakt het leven heel gemakkelijk, het verbetert de zichtbaarheid.

Maar het Hal.c-bestand is al een uitvoerbaar bestand en bevat, zoals ik al zei, verschillende initialisaties van randapparatuur.

#include "hal.h" void INIT_PEREF(void) ( //I/O-poorten initialiseren //######################## ### ####################################### ### ##### Komparator = ViklKomparator; // initialiseren van de comparator - DDRD uitschakelen = 1<

Nou, ik heb de module van de hoofdcyclus van het programma laten zien. Nu moeten we alleen de laatste stap zetten, we moeten de modules van de automaten zelf schrijven.

Stap 3.

Het enige wat we hoeven te doen is modules schrijven voor eindige toestandsmachines, in ons geval de LEDON-machine en de LEDOFF-machine. Om te beginnen zal ik de tekst geven van het programma voor het automatische apparaat dat de LED verlicht, bestand ledon.c.

//bestand ledon.c #include "ledon.h" #include "timers.h" #include "messages.h" unsigned char ledon_state; //state variabele void InitLEDON(void) ( ledon_state=0; //hier kunt u andere //automatische variabelen initialiseren, indien aanwezig) void ProcessLEDON(void) ( switch(ledon_state) ( case 0: //inactive state if(GetMessage ( MSG_LEDON_ACTIVATE)) //als er een bericht is, wordt het geaccepteerd ( //en de timer wordt gecontroleerd if(GetGTimer(TIMER_SEK)==one_sek) //als de timer 1 seconde heeft geklokt, voer dan uit ( StopGTimer(TIMER_SEK) ); POORTD = 1<

Hier worden, zoals altijd, in de eerste regels bibliotheken met elkaar verbonden en variabelen gedeclareerd. Vervolgens hebben we de functies die we al hebben ontmoet. Dit is de initialisatiefunctie van de InitLEDON-automaat en de functie van de ProcessLEDON-automaathandler zelf.

In de body van de handler zijn functies uit de timermodule en de berichtenmodule al verwerkt. En de logica van de machine zelf is gebaseerd op het ontwerp van de schakelkast. En hier merk je dat de machinebediener ook ingewikkeld kan zijn door het toevoegen van meerdere kastschakelaars.

Het headerbestand voor de machine zal nog eenvoudiger zijn:

//fsm1 bestand #ifndef LEDON_h #define LEDON_h #include "hal.h" void InitLEDON(void); ongeldig ProcessLEDON(nietig); #endif

Hier nemen we het koppelingsbestand hal.h op en geven we ook functieprototypes aan.

Het bestand dat verantwoordelijk is voor het uitschakelen van de LED ziet er alleen in spiegelbeeld bijna hetzelfde uit, dus ik zal het hier niet weergeven - ik ben terughoudend :)

U kunt alle projectbestanden downloaden via deze link ====>>> LINK.

Er zijn slechts drie stappen en ons programma heeft een voltooide vorm gekregen, wat betekent dat mijn missie voor vandaag voorbij is en het tijd is om het af te ronden. Het lijkt mij dat de informatie in dit artikel zeer nuttig voor u zal zijn. Maar het levert pas écht voordeel op als je deze kennis in de praktijk toepast.

Ik heb trouwens een aantal interessante projecten gepland die bijzonder interessant zullen zijn, dus zorg ervoor dat je dat doet abonneer je op nieuwe artikelen . Ik ben ook van plan om aanvullend materiaal te versturen, dus velen hebben zich al geabonneerd via de hoofdpagina van de site. U kunt zich hier ook abonneren.

Nou, nu heb ik echt alles, dus ik wens je veel geluk, een goed humeur en tot ziens.

Van n.v.t. Vladimir Vasiliev