Theorie van automaten, eindige automaten
De structuur, het ontwerp en het werkingsprincipe van verschillende machines worden grotendeels bepaald door het functionele doel. Maak onderscheid tussen technologische, transport-, computer-, militaire en andere machines. Volledige automatische complexen die zijn ontworpen om complexe technologische processen uit te voeren, worden op grote schaal geïntroduceerd in verschillende industrieën. Automaten zijn ontworpen en gebouwd die verschillende logische functies uitvoeren (logische machines).
Theorie van automaten — sectie cybernetica, die is ontstaan onder invloed van de eisen van de technologie van digitale computers en besturingsmachines. Discrete automaten die in de automatentheorie worden bestudeerd, zijn abstracte modellen van echte systemen (zowel technisch als biologisch) die discrete (digitale) informatie verwerken in discrete tijdstappen.
Automatentheorie is gebaseerd op precieze wiskundige concepten die intuïtieve ideeën over het functioneren (gedrag) van de automaat en over zijn structuur (interne structuur) formaliseren.
In dit geval wordt informatietransformatie altijd opgevat als een bewerking die invoerreeksen die zijn samengesteld uit letters van het invoeralfabet omzet in uitvoerreeksen die zijn samengesteld uit letters van het uitvoeralfabet.
Het apparaat van wiskundige logica, algebra, kansrekening, combinatoriek en grafentheorie wordt veel gebruikt.
Het probleem met de theorie van automaten in sommige delen ervan (structurele theorie van automaten) groeide uit de theorie van relaiscontactcircuits, die eind jaren dertig vorm begon te krijgen. inclusief methoden van logische algebra.
In de structurele theorie van automaten worden verschillende soorten schema's bestudeerd, ontworpen om te beschrijven hoe een complexe automaat wordt gemaakt van eenvoudigere componenten (elementen) die correct zijn verbonden in een systeem.
Een andere richting, de abstracte theorie van automaten genaamd, bestudeert het gedrag van automaten (dat wil zeggen, de aard van de transformatie van informatie die door hen wordt uitgevoerd), terwijl ze abstraheert van de specifieke kenmerken van hun interne structuur, en ontstond in de jaren vijftig.
Binnen het kader van de abstracte theorie van automaten wordt de inhoud van de begrippen "automaat" en "machine" in wezen uitgeput door de standaardbeschrijving van de transformatie van informatie die door een automaat wordt uitgevoerd. Zo'n transformatie kan deterministisch, maar ook probabilistisch van aard zijn.
De meest bestudeerde zijn deterministische machines (automaten), waaronder eindige automaten - het belangrijkste studieobject in de theorie van automaten.
Een eindige-toestandsmachine wordt gekenmerkt door een beperkte hoeveelheid geheugen (het aantal interne toestanden) en wordt gedefinieerd met behulp van een overgangsfunctie.Met enige redelijke idealisering kunnen alle moderne wiskundige machines en zelfs de hersenen, vanuit het oogpunt van hun functioneren, worden beschouwd als eindige automaten.
De termen "sequentiële machine", "Milly-automaat", "Moore-automaat" worden in de literatuur (en niet uniform door alle auteurs) gebruikt als synoniemen van de term "eindige automaat" of om bepaalde kenmerken in de overgangsfuncties van een eindige te benadrukken automaat.
Automata met onbeperkt geheugen is een Turing-machine die in staat is om (potentieel) elke efficiënte informatietransformatie uit te voeren. Het concept van "Turingmachine" is eerder ontstaan dan het concept van "finite state machine" en wordt vooral bestudeerd in de theorie van algoritmen.
De abstracte automatentheorie is nauw verwant aan bekende algebraïsche theorieën, bijvoorbeeld de semigroepentheorie. Vanuit een toegepast oogpunt zijn de resultaten die kenmerkend zijn voor de transformatie van informatie in een automaat in termen van geheugengrootte van belang.
Dit is bijvoorbeeld het geval bij problemen met experimenten op automaten (werken van E.F. Moore, enz.), Waar een of andere informatie over de overgangsfuncties van de automaat of over de capaciteit van zijn geheugen wordt verkregen uit de resultaten van de experimenten.
Een andere taak is het berekenen van de perioden van de uitvoerreeksen, gebaseerd op de beschikbare informatie over de geheugengrootte van de automaat en de perioden van de invoerreeksen.
Van groot belang is de ontwikkeling van methoden om het geheugen van eindige-toestandsmachines te minimaliseren en hun gedrag in willekeurige omgevingen te bestuderen.
In de abstracte automatentheorie is het syntheseprobleem het volgende.In termen van duidelijk geformaliseerde taal zijn de voorwaarden geschreven voor het gedrag van de ontworpen automaat (voor de gebeurtenis die in de automaat wordt weergegeven). In dit geval is het noodzakelijk om methoden te ontwikkelen die volgens elke schriftelijke voorwaarde:
1) nagaan of er zo'n toestandsmachine bestaat dat de daardoor getransformeerde informatie aan deze voorwaarde voldoet;
2) zo ja, dan worden de overgangsfuncties van zo'n eindige-toestandsmachine geconstrueerd of wordt de geheugengrootte geschat.
De oplossing van de synthesetaak in een dergelijke formulering veronderstelt de voorlopige creatie van een handige taal voor het vastleggen van de bedrijfsomstandigheden van een automaat met handige algoritmen voor de overgang van opname naar transitieve functies.
In de structurele theorie van automaten bestaat het syntheseprobleem uit het construeren van een keten van elementen van een bepaald type die een eindige automaat realiseert die wordt gegeven door zijn overgangsfuncties. In dit geval vermelden ze meestal een of ander optimaliteitscriterium (bijvoorbeeld het minimum aantal elementen) en proberen ze een optimaal schema te verkrijgen.
Zoals later bleek, betekent dit dat sommige methoden en concepten die eerder zijn ontwikkeld met betrekking tot relaiscontactcircuits van toepassing zijn op circuits van een ander type.
In verband met de ontwikkeling van elektronische technologieën zijn de meest voorkomende schema's van functionele elementen (logische netwerken). Een speciaal geval van logische netwerken zijn abstracte neurale netwerken, waarvan de elementen neuronen worden genoemd.
Er zijn veel synthesemethoden ontwikkeld, afhankelijk van het type circuits en de transformatie van informatie waarvoor ze bedoeld zijn (synthese van relaisapparaten).
Kijk -Minimalisering van combinatorische circuits, Carnot-kaarten, circuitsynthese
Eindigetoestandsautomaat — een wiskundig model van een besturingssysteem met een vaste (niet in staat om tijdens bedrijf te vergroten) geheugengrootte.
Het concept van een eindige-toestandsmachine is een wiskundige abstractie die de algemene kenmerken kenmerkt van een reeks besturingssystemen (bijvoorbeeld een relaisapparaat met meerdere lussen). Al dergelijke systemen hebben gemeenschappelijke kenmerken die normaal zijn om te accepteren als de definitie van een eindige automaat.
Elke voltooide automaat heeft een ingang die is blootgesteld aan invloeden van buitenaf en interne elementen. Voor zowel invoer- als interne elementen is er een vast aantal discrete toestanden die ze kunnen aannemen.
De verandering in de status van de invoer en interne elementen vindt plaats op discrete momenten in de tijd, de intervallen waartussen tikken worden genoemd. De interne toestand (de toestand van het inwendige) aan het einde van de tape wordt volledig bepaald door de interne toestand en de toestand van de invoer aan het begin van de band.
Alle andere definities van een eindige automaat kunnen tot dit kenmerk worden herleid, in het bijzonder definities die ervan uitgaan dat een eindige automaat een output heeft die afhangt van de interne toestand van de automaat op een bepaald moment.
In termen van een dergelijk kenmerk is de aard van de invoer en interne toestanden niet relevant voor de beschrijving van een volledige automaat. In plaats van invoer en statussen, kunt u gewoon naar hun nummers kijken in een willekeurige nummering.
De statusmachine wordt ingesteld als de afhankelijkheid van het interne statusnummer van het vorige interne statusnummer en het vorige invoerstatusnummer is gespecificeerd. Zo'n taak kan de vorm hebben van een finaletafel.
Een andere veelgebruikte manier om een complete automaat te definiëren, is de constructie van de zogenaamde overgangsdiagrammen. Inputstatussen worden vaak gewoon inputs genoemd, en interne statussen zijn gewoon statussen.
Een eindige-toestandsmachine kan een model zijn van zowel technische apparaten als sommige biologische systemen. Automaten van het eerste type zijn bijvoorbeeld relaisinrichtingen en diverse elektronische computers, incl. programmeerbare logische controllers.
In het geval van een relaisapparaat wordt de rol van ingangstoestanden gespeeld door combinaties van toestanden van de gevoelige elementen van het relaisapparaat (elke combinatie van dergelijke toestanden is een «complexe toestand», gekenmerkt door een indicatie van alle gevoelige elementen van deze discrete toestanden die ze op een bepaald moment hebben). Evenzo fungeren combinaties van toestanden van tussenliggende elementen van een relaisapparaat als interne toestanden.
Een programmeerbare logische controller (PLC) is een voorbeeld van een relaisactie-apparaat dat een stand-alone toestandsmachine kan worden genoemd.
Als het programma eenmaal in de PLC is ingevoerd en de controller is begonnen met rekenen, is deze namelijk niet meer blootgesteld aan invloeden van buitenaf en wordt elke volgende status volledig bepaald door de vorige status. We kunnen aannemen dat de ingang in elke klokcyclus dezelfde toestand heeft.
Omgekeerd wordt elke eindige-toestandsmachine die de enige mogelijke invoerstatus heeft, van nature autonoom genoemd, aangezien in dit geval de externe omgeving geen informatie bevat die zijn gedrag bepaalt.
Zie ook: