Automatteori

Automatateorin  är en gren av diskret matematik som studerar abstrakta automater  – datorer representerade som matematiska modeller – och de problem de kan lösa.

Teorin om automater är närmast besläktad med teorin om algoritmer : automaten omvandlar diskret information i steg till diskreta ögonblick och genererar resultatet i steg av en given algoritm .

Det finns en algebraisk behandling av automatteori med hjälp av semirings , formella potensserier , formella serier över träd, fixpunktsteori och matristeori [ 1] .

Terminologi

En symbol  är vilket atomärt (det vill säga inte längre odelbart utan betydelseförlust) datablock som kan ha en effekt på en maskin. Oftast är en symbol en bokstav i något formellt språk. Till exempel inkluderar symbolerna som används i många programmeringsspråk vanliga bokstäver, avgränsare och några ytterligare tecken. Men en symbol kan till exempel vara ett helt nyckelord för ett visst programmeringsspråk (if, for, while, etc.), ett grafiskt element i ett diagram, etc.

Syftet med formella automater

I automatteorin förstås detta ord som en formell (matematisk) konstruktion som definierar en algoritm vars syfte är att avgöra om ett givet ord tillhör det inmatningsspråk som beskrivs av en given formell automat. Ordet "formell" understryker skillnaden mellan en sådan automat och automatiska verktygsmaskiner, automatiska växellådor och andra liknande enheter förkroppsligade i metall. För korthetens skull utelämnas ofta adjektivet "formell" eller "matematisk" i de relevanta manualerna (börjar med teorins namn - det skulle vara mer exakt "teorin om formella automater") när det är tydligt vad som står på spel.

Ordningen för maskinens drift

För att uppfylla sitt syfte är alla (formella) automater utrustade med egenskapen att vara i något tillåtet tillstånd och automatövergångsfunktioner, i det enklaste fallet (finita automater) specificerar endast möjligheten för övergång från ett tillstånd till ett annat vid läsning av nästa tecken från ingångskedjan. Efter nästa övergång förskjuts maskinens läshuvud med ett tecken (det är "läst"). Detta händer tills slutet av ordet som läses nås, eller en lämplig övergångsfunktion inte hittas.

Uppsättningen av alla tillåtna tillstånd för automaten är ändlig och bildar alfabetet av tillstånd för automaten. Från hela uppsättningen tillstånd särskiljs en delmängd av automatens initiala tillstånd (i en av vilka tolkning av ordet kan börja) och en delmängd av slutliga (eller slutliga ) tillstånd där automaten (om ordet läses ) fullständigt) kan dra slutsatsen att det analyserade (inmatade) ordet tillhör maskinspråket. De initiala och slutliga tillstånden för automaten kan skära varandra. Om automaten går in i det slutliga (eller slutliga) tillståndet, indikerar det bara möjligheten att slutföra analysen, det vill säga att automaten kan gå igenom ett eller annat sluttillstånd många gånger under drift medan läsningen av ordet fortsätter.

Starta och stoppa maskinen

Starten av automatens drift bestäms helt av dess "initialkonfiguration", som inkluderar det analyserade ordet och det tillstånd i vilket automaten är belägen. Om automaten är i ett av initialtillstånden och det finns en övergångsfunktion för detta tillstånd och den första symbolen för den läsbara strängen, gör automaten motsvarande övergång, flyttar läshuvudet på inmatningsordet och (i det enklaste fallet) ändliga automater) fortsätter för att undersöka nästa inmatningssymbol.

För att acceptera (eller, som de säger, erkänna) ett inmatningsord av en automat, måste två villkor vara uppfyllda:

  1. Inmatningsordet måste läsas i sin helhet
  2. Efter att ha läst ordet är automaten (eller kan ta sig igenom tomma övergångar, om sådana tillåts för motsvarande typ av automater) till ett av sluttillstånden. För vissa typer av automater kan detta kriterium formuleras något annorlunda, och i automatateorin bevisas ekvivalensen (ekvivalensen) för sådana formuleringar av stoppet.

Med "tom övergång" eller "passage av tom symbol" menar vi här en övergång från ett tillstånd till ett annat, när nästa tecken inte läses från inmatningsordet, eller, med andra ord, ett tomt tecken "läses". Se nedan för beteckningar.

Observera att automaten måste acceptera alla tillåtna ord på det språk den beskriver och samtidigt inte acceptera ett enda ord som inte ingår i detta språk.

Om inmatningsordet inte tillhör språket, då automaten heller

  1. kommer att stanna i ett ändligt antal steg utan att ha läst till slutet av ordet och utan att ha en lämplig övergångsfunktion för att fortsätta läsa
  2. kommer att läsa hela ordet, men kommer inte att vara i ett av sluttillstånden (eller något annat likvärdigt kriterium kommer inte att uppfyllas för vissa typer av automater)
  3. går in i en oändlig cykel av ändrade tillåtna tillstånd, där dock båda kriterierna för att ta emot (tillåta) ett ord inte kommer att uppfyllas samtidigt.

Huvudtyperna av automater

Genom komplexiteten hos språken som analyseras

Formella automater är vanligtvis uppdelade efter egenskaperna hos deras övergångsfunktioner, som bestämmer graden av komplexitet hos språket som det beskriver.

Enligt klassificeringen av N. Chomsky är fyra huvudtyper (efter variation, efter komplexitet) av formella språk kända:

  1. Regelbunden
  2. Kontextfri
  3. Kontextkänslig
  4. Allmänna språk (inga ytterligare begränsningar)

För att tolka ord från vanliga språk, formella automater för den enklaste enheten, den så kallade. ändliga automater . Deras övergångsfunktion specificerar endast en förändring av tillstånd och, möjligen, en förskjutning (läsning) av inmatningssymbolen.

För att tolka ett ord från sammanhangsfria språk måste man lägga till ett "shoppingband" eller "stack" till automaten, i vilken en kedja skrivs in vid varje övergång baserat på motsvarande butiksalfabet. Sådana maskiner kallas " butiksmaskiner ".

För sammanhangskänsliga språk har ännu mer komplexa linjärt avgränsade automater utvecklats och för allmänna språk en Turing-maskin [2] .

Med en närmare bekantskap med teorin blir det tydligt att ju mer komplex automaten är, desto större är dess igenkänningsförmåga, men samtidigt blir det svårare och mer tidskrävande att arbeta med den. Därför försöker en kompetent matematiker och en mjukvaruingenjör att välja den enklaste typen av automat som löser igenkänningsproblemet med rätt kvalitet.

Observera att många uppgifter för att söka efter information på World Wide Web är skrivna i termer av vanliga språk (det vill säga med de strängaste begränsningarna), och de flesta av de universella programmeringsspråken som används är ganska framgångsrikt implementerade på basis av av sammanhangsfria grammatiker (men med vissa förbättringar, se . "attribut grammatik"). Bland de få och mycket säregna undantagen finns programmeringsspråket LISP (LISP), utvecklat på basis av sammanhangskänsliga språk. Och Turing-maskinen, trots all sin (i teorin) universalitet och kraft, visar sig vara så komplex och obekväm för användning i applikationer att den endast används för teoretisk analys.

Genom att övergångsfunktionen är unik

För samma aktuella konfiguration (automatens tillstånd, den läsbara ingångssymbolen och eventuellt några ytterligare parametrar för komplexa typer av automater, till exempel innehållet i stacken i en nedskjutbar automat), fungerar övergångsfunktionerna för en formell automaton kan specificera som en enda (definitiv, deterministisk) övergång, så och några olika. Med andra ord, för samma konfiguration av en automat, generellt sett, är förekomsten av flera övergångsfunktioner möjlig.

Osäkerhet (icke-determinism) hos automaten kan också uppstå när var och en av dess konfigurationer motsvarar endast en övergångsfunktion, men övergångar längs den "tomma kedjan" (tom symbol) är också tillåtna. Det är tydligt att tvetydigheten i övergången här inte kan uppstå i en, utan i flera klockcykler hos automaten.

På grundval av detta delas även automater in i deterministiska (definitiva) och icke-deterministiska. Vikten av denna uppdelning förklaras också av hur egenskapen determinism påverkar tolkningen av ett ords tolerans av en automat.

Så om vi har en deterministisk automat, om ovanstående villkor för att tillåta ett ord inte är uppfyllda, kan vi omedelbart säga att detta ord inte tillhör språket. Om vi ​​har en icke-deterministisk automat, så drar vi i ett sådant fall denna slutsats endast för en av de möjliga grenarna av att analysera ordet. I själva verket måste programmeraren på något sätt komma ihåg alla möjliga gafflar i analysen av ett ord och, om en av grenarna misslyckas, gå tillbaka till nästa gaffel och utforska en annan analysgren. Och först efter att ha undersökt alla möjliga analysalternativ (om ingen av de mellanliggande grenarna uppfyllde toleransvillkoren), kan vi med säkerhet dra slutsatsen att det givna ordet inte tillhör språket.

Det är tydligt att spårning och redovisning av möjliga returer vid analys av ett ord avsevärt komplicerar programmerarens arbete. Därför uppstår frågan om det är möjligt att transformera automaten på ett sådant sätt att den blir deterministisk från icke-deterministisk och, i ett antal fall, därför mer bekväm att arbeta med den. Det har bevisats i automatteorin att detta alltid kan göras för vanliga språk och deras motsvarande finita automater. Och för andra typer av språk (enligt N. Chomsky), börjar med kontextfri och deras motsvarande automater, i det allmänna fallet - inte längre.

Å andra sidan noteras det att icke-deterministiska automater vanligtvis har en märkbart mindre volym, deras operationslogik är lättare för en person att förstå. Observera att när man använder datorer med flera processorer (flerkärniga) är själva möjligheten till parallellisering ofta nära relaterad till algoritmens icke-determinism. Ett program, vars alla delar måste köras i en strikt definierad sekvens, kan inte parallelliseras ... [2] .

Exempel på formella definitioner för finita automater

Automater kan vara deterministiska eller icke-deterministiska .

En deterministisk finit automat  (DFA)  är en sekvens ( tuppel ) av fem element, där: En icke-deterministisk finit automat  (NFA)  är en sekvens (tuppel) av fem element, där: Ord Automaten läser den sista teckensträngen a 1 , a 2 , …., a n , där a i   Σ, som kallas inmatningsordet . Mängden av alla ord skrivs som Σ*. Accepterat ord Ordet w   Σ* accepteras av automaten om q n  F. 

Ett språk L sägs vara läsbart (accepterat) av en automat M om det består av ord w baserat på alfabetet så att om dessa ord skrivs in i M, kommer det efter avslutad bearbetning till ett av de accepterande tillstånden F:

Vanligtvis övergår en automat från tillstånd till tillstånd med hjälp av en övergångsfunktion , medan den läser ett tecken från inmatningen. Det finns automater som kan övergå till ett nytt tillstånd utan att läsa ett tecken. Övergångsfunktionen utan att läsa ett tecken kallas -jump (epsilon-jump).

Applikation

Teorin om automater ligger till grund för all digital teknologi och programvara, till exempel är en dator ett specialfall av den praktiska implementeringen av en finita tillståndsmaskin.

En del av automatteorins matematiska apparat används direkt i utvecklingen av lexikaliska och syntaktiska analysatorer för formella språk , inklusive programmeringsspråk , såväl som i konstruktionen av kompilatorer och utvecklingen av själva programmeringsspråken, hårdvarubeskrivningar och uppmärkning. .

En annan viktig tillämpning av automatateorin är den matematiskt rigorösa bestämningen av problems lösbarhet och komplexitet .

Typiska uppgifter

Se även

Anteckningar

  1. ↑ Modern automata theory , 2013 , sid. 5.
  2. ↑ 1 2 Serebryakov V. A. , Galochkin M. P., Gonchar D. R., Furugyan M. G. Teori och implementering av programmeringsspråk Arkivkopia daterad 3 januari 2022 på Wayback Machine  - M .: MZ-Press, 2006 ., 2nd ed.. — ISBN 5-94073-094-9

Litteratur

Länkar

  Gå till Wikidata-objektet  Ordböcker och uppslagsverk