Grunnleggende begreper i teorien om abstrakte automater. Automata teori Automata teori

verifisering av systemer for samvirkende prosesser;

Språk for å beskrive dokumenter og objektorienterte programmer;

Optimalisering av logikkprogrammer mv.

Dette kan bedømmes av talene til forskere og spesialister på "Software 2000..."-seminaret.

Doug Ross: "...80 eller til og med 90% av informatikk i fremtiden vil være basert på teorien om endelige tilstandsmaskiner..."

Herver Gallaire: "Jeg kjenner folk fra Boeing som jobber med flystabiliseringssystemer ved å bruke ren automatteori. Det er vanskelig å forestille seg hva de har oppnådd med denne teorien."

Brian Randell: "Mye av automatteorien har blitt brukt med hell i systemprogrammer og tekstfiltre i UNIX OS. Dette gjør at mange mennesker kan prestere på et høyt nivå og utvikle svært effektive programmer."

1.1. Grunnleggende begreper og definisjoner.

Den enkleste informasjonsomformeren (fig. 1.1, a) viser et visst sett med informasjonselementer X mottatt ved inngangen til et bestemt sett ved utgangen Y. Hvis settene X og Y er endelige og diskrete, det vil si at transformasjonen utføres ved diskrete øyeblikk i tid, kalles slike informasjonsomformere endelige omformere. Elementer av sett X og Y i dette tilfellet er forhåndskodet med binære koder og en transformasjon av ett sett til et annet er konstruert.

Resultatet av en transformasjon avhenger ofte ikke bare av hvilken informasjon som for øyeblikket vises ved inngangen, men også av hva som skjedde før, det vil si bakgrunnen for transformasjonen. For eksempel vil det samme innspillet – en nabos unnskyldning etter at han tråkket på foten din på en overfylt buss – føre til at du får én reaksjon første gang og en helt annen den femte gangen.

Ris. 1.1.

Dermed er det mer komplekse informasjonsomformere (IT), hvis reaksjon ikke bare avhenger av inngangssignalene for øyeblikket, men også av hva som skjedde før, på inngangshistorien. Slike PI-er kalles automater (kretser med minne). I dette tilfellet snakker de om automatisk transformasjon av informasjon (fig. 1.1, b). Maskinen kan reagere forskjellig på samme inngangssignal, avhengig av tilstanden den var i. Maskinen endrer tilstand med hvert inngangssignal.

La oss se på noen få eksempler.

Eksempel 1 1 Karpov Yu.G. Automateteori – St. Petersburg: Peter, 2003. Automat som beskriver oppførselen til en "smart" far.

La oss beskrive oppførselen til en far hvis sønn studerer på skolen og henter inn D-er og A-er. Faren vil ikke ta tak i beltet hver gang sønnen får dårlig karakter, og velger mer subtile foreldretaktikker. La oss definere en slik automat med en graf der toppunktene tilsvarer tilstander, og buen fra tilstand s til tilstand q, merket x/y, tegnes når automaten fra tilstand s under påvirkning av inngangssignalet x går til tilstand q med utgangsreaksjonen y. Grafen til en automat som modellerer den smarte oppførselen til en forelder er presentert i fig. 1.2. Denne maskinen har fire tilstander , to inngangssignaler - estimater og utgangssignaler, som vi vil tolke som handlingene til overordnet som følger:

Ta beltet;

Kjenner ut sønnen din;

Rolig sønnen din;

Håp;

Fryde;

Fryde.

Ris. 1.2.

En sønn som får samme karakter – en D – vil få en helt annen reaksjon fra sin far hjemme, avhengig av studiebakgrunnen. For eksempel, etter det tredje dårlige merket i historien, vil sønnen bli møtt med et belte, og i historien vil de roe ham ned osv.

En endelig tilstandsmaskin kan implementeres enten i programvare eller i maskinvare. Programvareimplementering kan gjøres på hvilken som helst språk på høyt nivå forskjellige måter. Figur 1.3 viser et blokkdiagram av et program som implementerer oppførselen til automaten i eksempel 1. Det er lett å se at topologien til programblokkdiagrammet gjentar topologien til overgangsgrafen til automaten. Tilknyttet hver tilstand er en operasjon NEXT, som utfører funksjonen å vente på neste hendelse med ankomsten av et nytt inngangssignal og lese det inn i en standard buffer x, samt påfølgende analyse av hva slags signal det er. Avhengig av hvilket signal som kom til inngangen, utføres en eller annen funksjon og en overgang til en ny tilstand skjer.

Ris. 1.3.

Vi vil vurdere maskinvareimplementeringen av maskinen i den andre delen av denne delen.

Eksempel 2. «Student»

Automaten, hvis modell er presentert i fig. 1.4, beskriver oppførselen til eleven og lærerne.

Ris. 1.4.

stater;

- inngangssignaler: "n", "2" og "5".

Utgangsreaksjoner:

Eksempel 3 1. Elektronisk klokke (fig. 1.5).

Elektroniske klokker med ulike funksjonelle evner er en av de mest brukte elektroniske enhetene i hverdagen, hvis kontroll er basert på en finite-state maskinmodell. De viser vanligvis: tid, dato; de har funksjoner som «innstilling av klokkeslett og dato», «stoppeklokke», «alarmklokke» osv. Forenklet strukturordning elektronisk klokke er vist i fig. 1.5

Ris. 1.5.

Registrene viser enten klokkeslett, dato eller stoppeklokke avhengig av "Kontroll". Kontrollenhet bygget på grunnlag av en endelig tilstandsmaskinmodell. Tilstandsmaskinen reagerer på å trykke på "a"-knappen på kroppen ved å gå over til "Set minutter"-tilstanden, der tilfellet med å trykke på "b"-knappen vil føre til at tallet øker.

automatteori
Automateteori- en gren av diskret matematikk som studerer abstrakte automater - datamaskiner presentert i form av matematiske modeller - og problemene de kan løse.

Teorien om automater er nærmest knyttet til teorien om algoritmer: en automat konverterer diskret informasjon trinn for trinn til diskrete øyeblikk av tid og genererer et resultat i henhold til trinnene til en gitt algoritme.

• 1 Terminologi
• 2 Søknad
  • 2.1 Typiske oppgaver
• 3 Se også
• 4 Litteratur
• 5 lenker

Terminologi

Symbol- enhver atomblokk med data som kan gi en effekt på en maskin. Oftest er et symbol en bokstav på vanlig språk, men det kan for eksempel være et grafisk element i et diagram.

• Ord- en streng med tegn opprettet gjennom sammenkobling (forbindelse).
• Alfabet- et begrenset sett med forskjellige symboler (mange symboler)
• Språk- et sett med ord dannet av symbolene i et gitt alfabet. Kan være endelig eller uendelig.

Spilleautomater

Automater kan være deterministiske eller ikke-deterministiske.

Deterministisk endelig automat (DFA)

• - en overgangsfunksjon slik at
• - opprinnelige tilstand

Ikke-deterministisk endelig automat (NFA)- en sekvens (tuppel) av fem elementer, der:

• - sett med tilstander til maskinen
• - alfabetet til språket som maskinen forstår
• er en overgangsrelasjon, hvor er et tomt ord. Det vil si at en NFA kan gjøre et hopp fra tilstand q til tilstand p, i motsetning til DFA, gjennom et tomt ord, og også flytte fra q til flere tilstander (noe som igjen er umulig i DFA)
• - sett med starttilstander
• - sett med slutttilstander.

Ordautomaten leser en siste streng med tegn a1,a2,…., an, hvor ai ∈ Σ, som kalles inngangsordet.. Settet med alle ord skrives som Σ*. Akseptert ord Et ord w ∈ Σ* aksepteres av automaten hvis qn ∈ F.

Et språk L sies å bli lest (akseptert) av en automat M hvis det består av ord w basert på et alfabet slik at hvis disse ordene legges inn i M, når det er ferdig med behandlingen, kommer det til en av mottakstilstandene F:

Vanligvis beveger maskinen seg fra tilstand til tilstand ved hjelp av en overgangsfunksjon, mens den leser ett tegn fra inngangen. Det er maskiner som kan gå til en ny tilstand uten å lese et symbol. Funksjonen med å hoppe uten å lese et symbol kalles -hopp (epsilon-hopp).

applikasjon

Teorien om automater ligger til grunn for all digital teknologi og programvare, for eksempel er en datamaskin et spesialtilfelle av den praktiske implementeringen av en endelig tilstandsmaskin.

En del av det matematiske apparatet til automatteori brukes direkte i utviklingen av lexere og parsere for formelle språk, inkludert programmeringsspråk, så vel som i konstruksjonen av kompilatorer og utviklingen av programmeringsspråk selv.

En annen viktig anvendelse av automatteori er den matematisk strenge bestemmelsen av problemers løsebarhet og kompleksitet.

Typiske oppgaver

• Konstruksjon og minimering av automater- konstruksjon av en abstrakt automat fra en gitt klasse som løser et gitt problem (akseptere et gitt språk), eventuelt med påfølgende minimering med antall tilstander eller antall overganger.
• Syntese av automater- konstruksjon av et system fra gitt "elementær automata", tilsvarende en gitt automat. En slik automat kalles strukturell. Det brukes for eksempel i syntesen av digitale elektriske kretser på en gitt elementbase.

se også

• Pumping Lemma
• Abstrakt automat
• Game of Life
• Minimum form for maskin
• Shannon - Lupanov teorem

Litteratur

• John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Introduksjon til automatteori, språk og beregning. - M.: Williams, 2002. - S. 528. - ISBN 0-201-44124-1.
• Kasyanov V. N. Forelesninger om teorien om formelle språk, automater og beregningskompleksitet. - Novosibirsk: NSU, 1995. - S. 112.

Linker

• Anvendelse av automatteori

automatteori

Datamaskiner presentert i form av matematiske modeller – og problemene de kan løse.

Teorien om automater er nærmest knyttet til teorien om algoritmer: en automat konverterer diskret informasjon trinn for trinn til diskrete øyeblikk av tid og genererer et resultat i henhold til trinnene til en gitt algoritme.

Encyklopedisk YouTube

1 / 3

✪ Leksjon 12. Grunnleggende om automatteori. Matematisk logikk. Informatikktimer

✪ Hvordan styre verden ved å lære bare én enkel modell!

✪ Leksjon 15. Løse anvendte problemer i automatteori. Matematisk logikk. Informatikktimer

Undertekster

Terminologi

Symbol- enhver atomblokk med data som kan gi en effekt på en maskin. Oftest er et symbol en bokstav på vanlig språk, men det kan for eksempel være et grafisk element i et diagram.

• Ord- en streng med tegn opprettet gjennom sammenkobling (forbindelse).
• Alfabet- et begrenset sett med forskjellige symboler (mange symboler)
• Språk- et sett med ord dannet av symbolene i et gitt alfabet. Kan være endelig eller uendelig.

Spilleautomater Deterministisk endelig tilstandsmaskin (DFA)- sekvens (tuppel) av fem elementer (Q , Σ , δ , S 0 , F) (\displaystyle (Q,\Sigma,\delta,S_(0),F)), Hvor: Ikke-deterministisk endelig automat (NFA)- sekvens (tuppel) av fem elementer (Q , Σ , Δ , S , F) (\displaystyle (Q,\Sigma,\Delta ,S,F)), hvor: Word Automaton leser den siste strengen med tegn a 1 ,a 2 ,…., a n , hvor a i ∈ Σ, som kalles inndataord.Sammen med alle ord skrives som Σ*. Akseptert ord Et ord w ∈ Σ* aksepteres av automaten hvis q n ∈ F.

De sier at språket er L lest (godkjent) automat M hvis den består av ord w basert på alfabetet Σ (\displaystyle \Sigma) slik at hvis disse ordene legges inn i M, kommer det på slutten av behandlingen til en av mottakstilstandene F:

L = ( w ∈ Σ ⋆ | δ ^ (S 0 , w) ∈ F ) (\displaystyle L=\(w\in \Sigma ^(\star )|(\hat (\delta ))(S_(0) ,w)\i F\))

Vanligvis flytter en automat fra tilstand til tilstand ved hjelp av en overgangsfunksjon δ (\displaystyle \delta ) mens du leser ett tegn fra inngangen. Det er maskiner som kan gå til en ny tilstand uten å lese et symbol. Funksjonen med å hoppe uten å lese et tegn kalles ϵ (\displaystyle \epsilon )-overgang(epsilon overgang). problemers kompleksitet.

Typiske oppgaver

• Konstruksjon og minimering av automater- konstruksjon av en abstrakt automat fra en gitt klasse som løser et gitt problem (akseptere et gitt språk), eventuelt med påfølgende minimering med antall tilstander eller antall overganger.
• Syntese av automater- konstruksjon av et system fra gitt "elementær automata", tilsvarende en gitt automat. En slik automat kalles strukturell. Det brukes for eksempel i syntesen av digitale elektriske kretser på en gitt elementbase.

Automateteori

Automateteori- en gren av diskret matematikk som studerer abstrakte automater - datamaskiner presentert i form av matematiske modeller - og problemene de kan løse.

Teorien om automater er nærmest beslektet med teorien om algoritmer: en automat transformerer diskret informasjon trinn for trinn til diskrete øyeblikk av tid og genererer et resultat i henhold til trinnene til en gitt algoritme.

Terminologi

Symbol- enhver atomblokk med data som kan gi en effekt på en maskin. Oftest er et symbol en bokstav på vanlig språk, men det kan for eksempel være et grafisk element i et diagram.

• Ord- en streng med tegn opprettet gjennom sammenkobling (forbindelse).
• Alfabet- et begrenset sett med forskjellige symboler (mange symboler)
• Språk- et sett med ord dannet av symbolene i et gitt alfabet. Kan være endelig eller uendelig.

Maskin Maskin- en sekvens (tuppel) av fem elementer, hvor: Word Automaton leser den siste strengen med tegn a 1,a 2,…., a n, hvor a i ∈ Σ, og kalles i et ord.Sammen med alle ord skrives som Σ*. Akseptert ord Et ord w ∈ Σ* aksepteres av automaten hvis q n ∈ F.

De sier at språket er L lest (godkjent) en automat M hvis den består av ord w basert på et alfabet slik at hvis disse ordene legges inn i M, kommer den på slutten av behandlingen til en av mottakstilstandene F:

Vanligvis flytter en automat fra tilstand til tilstand ved hjelp av en overgangsfunksjon, mens den leser ett tegn fra inngangen. Det finnes også maskiner som kan gå til en ny tilstand uten å lese et symbol. Funksjonen med å hoppe uten å lese et tegn kalles -overgang(epsilon overgang).

applikasjon

I praksis brukes automatteori i utviklingen av lexere og parsere for formelle språk (inkludert programmeringsspråk), så vel som i konstruksjonen av kompilatorer og utviklingen av programmeringsspråk selv.

En annen viktig anvendelse av automatteori er den matematisk strenge bestemmelsen av problemers løsebarhet og kompleksitet.

Typiske oppgaver

• Konstruksjon og minimering av automater- konstruksjon av en abstrakt automat fra en gitt klasse som løser et gitt problem (akseptere et gitt språk), eventuelt med påfølgende minimering med antall tilstander eller antall overganger.
• Syntese av automater- konstruksjon av et system fra gitt "elementær automata", tilsvarende en gitt automat. En slik automat kalles strukturell. Det brukes for eksempel i syntesen av digitale elektriske kretser på en gitt elementbase.

se også

Litteratur

• John Hopcroft, Rajeev Motwani, Jeffrey Ullman Introduksjon til automatteori, språk og beregning. - M.: Williams, 2002. - S. 528. - ISBN 0-201-44124-1
• Kasyanov V.N. Forelesninger om teori om formelle språk, automater og beregningsmessig kompleksitet. - Novosibirsk: NSU, 1995. - S. 112.

Linker

Wikimedia Foundation. 2010.

Se hva "Automatoma Theory" er i andre ordbøker:

Automateteori

Automateteori- en del av teoretisk kybernetikk som studerer matematiske modeller (her kalt automater eller maskiner) av reelle eller mulige enheter som behandler diskret informasjon i diskrete sykluser. Hoved... ... Økonomisk og matematisk ordbok

automatteori- En del av teoretisk kybernetikk som studerer matematiske modeller (her kalt automater eller maskiner) av reelle eller mulige enheter som behandler diskret informasjon i diskrete sykluser. De grunnleggende konseptene i denne teorien ... ... Teknisk oversetterveiledning

Substantiv, antall synonymer: 1 stram (1) ASIS Dictionary of Synonyms. V.N. Trishin. 2013… Synonymordbok

automatteori- automatų teorija statusas T sritis automatika atitikmenys: engl. automatteori vok. Automatentheorie, f rus. automatteori, f pranc. théorie des automates, f … Automatikos terminų žodynas

Dette begrepet har andre betydninger, se State Diagram. Tilstandsdiagram er en rettet graf for en endelig tilstandsmaskin, der toppunktene indikerer tilstandene til buen og indikerer overganger mellom to tilstander. I praksis... ... Wikipedia

Teorien om maskiner og mekanismer (TMM) er en vitenskapelig disiplin om de generelle metodene for forskning, konstruksjon, kinematikk og dynamikk til mekanismer og maskiner og det vitenskapelige grunnlaget for deres design. Innhold 1 Historie om utviklingen av disiplinen 2 Grunnleggende begreper ... Wikipedia

TEORI- (1) et system av vitenskapelige ideer og prinsipper som generaliserer praktisk erfaring, som gjenspeiler objektive naturlover og bestemmelser som danner (se) eller en del av enhver vitenskap, samt et sett med regler innen enhver kunnskapsfelt. .... Big Polytechnic Encyclopedia

Teori om algoritmer Økonomisk og matematisk ordbok

Teori om algoritmer- en gren av matematikk som studerer de generelle egenskapene til algoritmer. Problemet med å konstruere en algoritme med visse egenskaper kalles et algoritmisk problem, dets uløselighet betyr fravær av en tilsvarende algoritme; Hvis … … Økonomisk og matematisk ordbok

Bøker

• Automateteori. Lærebok for bachelor- og mastergrader, Kudryavtsev V.B. Læreboken inneholder omfattende materiale om teorien om automater. Den introduserer begrepet en automat, gir teorier ...