Toggle menu
310,1 tis.
50
18
525,6 tis.
Hrvatska internetska enciklopedija
Toggle preferences menu
Toggle personal menu
Niste prijavljeni
Your IP address will be publicly visible if you make any edits.

Konačni automat: razlika između inačica

Izvor: Hrvatska internetska enciklopedija
Bot: Automatski unos stranica
 
m Bot: Automatska zamjena teksta (-{{cite book +{{Citiranje knjige)
Redak 130: Redak 130:
=== Konačni automati (teorija automata) u teoretskom računarstvu ===
=== Konačni automati (teorija automata) u teoretskom računarstvu ===


*{{cite book | last = Arbib | first = Michael A. | coauthors = | title = Theories of Abstract Automata  | edition = 1st ed. | publisher = Prentice-Hall, Inc. | location = Englewood Cliffs, N.J. | year = 1969| isbn = 0-13-913368-2}}
*{{Citiranje knjige | last = Arbib | first = Michael A. | coauthors = | title = Theories of Abstract Automata  | edition = 1st ed. | publisher = Prentice-Hall, Inc. | location = Englewood Cliffs, N.J. | year = 1969| isbn = 0-13-913368-2}}
*{{cite book | last =Bobrow | first = Leonard S. | coauthors = Michael A. Arbib| title = Discrete Mathematics: Applied Algebra for Computer and Information Science  | edition = 1st ed. | publisher = W. B. Saunders Company, Inc. | location = Philadelphia  | year = 1974| isbn = 0-7216-1768-9}}
*{{Citiranje knjige | last =Bobrow | first = Leonard S. | coauthors = Michael A. Arbib| title = Discrete Mathematics: Applied Algebra for Computer and Information Science  | edition = 1st ed. | publisher = W. B. Saunders Company, Inc. | location = Philadelphia  | year = 1974| isbn = 0-7216-1768-9}}
*{{cite book | last = Booth| first = Taylor L. | coauthors = | title = Sequential Machines and Automata Theory | edition = 1st | publisher = John Wiley and Sons, Inc. | location = New York | year = 1967| id = Library of Congress Card Catalog Number 67-25924}} Opširna knjiga namijenjena specijalistima, napisana i za teoretske računalne znanstvenike i za električne inženjere. Uključuje detaljna objašnjenja tehnika minimizacije stanja, KA, Turingovih strojeva, Markovljevih procesa i neodlučivosti. Izvrstan tretman Markovljevih procesa.
*{{Citiranje knjige | last = Booth| first = Taylor L. | coauthors = | title = Sequential Machines and Automata Theory | edition = 1st | publisher = John Wiley and Sons, Inc. | location = New York | year = 1967| id = Library of Congress Card Catalog Number 67-25924}} Opširna knjiga namijenjena specijalistima, napisana i za teoretske računalne znanstvenike i za električne inženjere. Uključuje detaljna objašnjenja tehnika minimizacije stanja, KA, Turingovih strojeva, Markovljevih procesa i neodlučivosti. Izvrstan tretman Markovljevih procesa.
*{{cite book | last = Boolos | first = George | coauthors = Richard Jeffrey | title = Computability and Logic | edition = 3rd ed. | publisher = Cambridge University Press | location = Cambridge, England | year = 1989, 1999| isbn = 0-521-20402-X}} Izvrsna knjiga. Izdaje se opetovano u različitim edicijama od 1974. (1974., 1980., 1989., 1999.).
*{{Citiranje knjige | last = Boolos | first = George | coauthors = Richard Jeffrey | title = Computability and Logic | edition = 3rd ed. | publisher = Cambridge University Press | location = Cambridge, England | year = 1989, 1999| isbn = 0-521-20402-X}} Izvrsna knjiga. Izdaje se opetovano u različitim edicijama od 1974. (1974., 1980., 1989., 1999.).
*{{cite book | last = Brookshear | first = J. Glenn | title = Theory of Computation: Formal Languages, Automata, and Complexity | year = 1989 | publisher = Benjamin/Cummings Publish Company, Inc. | location = Redwood City, California | isbn = 0-8053-0143-7}} Pristupa [[Church-Turingova teza|Church-Turingovoj tezi]] iz tri kuta: razine konačnih automata kao prihvatitelja formalnih jezika, teorije primitivne i paricijalne rekurzije, te moći običnih programskih jezika u svrhu ostvarenja algoritama, sve u jednom debelom svesku.
*{{Citiranje knjige | last = Brookshear | first = J. Glenn | title = Theory of Computation: Formal Languages, Automata, and Complexity | year = 1989 | publisher = Benjamin/Cummings Publish Company, Inc. | location = Redwood City, California | isbn = 0-8053-0143-7}} Pristupa [[Church-Turingova teza|Church-Turingovoj tezi]] iz tri kuta: razine konačnih automata kao prihvatitelja formalnih jezika, teorije primitivne i paricijalne rekurzije, te moći običnih programskih jezika u svrhu ostvarenja algoritama, sve u jednom debelom svesku.
*{{cite book | last = Davis| first = Martin | coauthors = Ron Sigal, Elaine J. Weyuker| title = Second Edition: Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science | edition = 2nd ed. | publisher = Academic Press, Harcourt, Brace & Company| location = San Diego | year = 1994| isbn = 0-12-206382-1}}
*{{Citiranje knjige | last = Davis| first = Martin | coauthors = Ron Sigal, Elaine J. Weyuker| title = Second Edition: Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science | edition = 2nd ed. | publisher = Academic Press, Harcourt, Brace & Company| location = San Diego | year = 1994| isbn = 0-12-206382-1}}
*{{cite book | last = Hopcroft | first = John | coauthors = Jeffrey Ullman| title = Introduction to Automata Theory, Languages and Computation | edition = 1st ed. | publisher = Addison-Wesley | location =  Reading Mass | year = 1979| | isbn = 0-201-02988-X }} Teška knjiga usredotočena na probleme strojnog tumačenja formalnih jezika, NP-potpunosti itd.
*{{Citiranje knjige | last = Hopcroft | first = John | coauthors = Jeffrey Ullman| title = Introduction to Automata Theory, Languages and Computation | edition = 1st ed. | publisher = Addison-Wesley | location =  Reading Mass | year = 1979| | isbn = 0-201-02988-X }} Teška knjiga usredotočena na probleme strojnog tumačenja formalnih jezika, NP-potpunosti itd.
*{{cite book | last = Hopcroft | first = John E.| coauthors = Rajeev Motwani, Jeffrey D. Ullman| title = Introduction to Automata Theory, Languages, and Computation| edition = 2nd ed. | publisher = Addison-Wesley | location =  Reading Mass | year = 2001| isbn = 0-201-44124-1}} Različita i nešto manje zastrašujuća od prvog izdanja.
*{{Citiranje knjige | last = Hopcroft | first = John E.| coauthors = Rajeev Motwani, Jeffrey D. Ullman| title = Introduction to Automata Theory, Languages, and Computation| edition = 2nd ed. | publisher = Addison-Wesley | location =  Reading Mass | year = 2001| isbn = 0-201-44124-1}} Različita i nešto manje zastrašujuća od prvog izdanja.
*{{cite book | last = Hopkin | first = David | coauthors = Barbara Moss| title = Automata | edition = | publisher = Elsevier North-Holland | location = New York | year = 1976| isbn = 0-444-00249-9 }}
*{{Citiranje knjige | last = Hopkin | first = David | coauthors = Barbara Moss| title = Automata | edition = | publisher = Elsevier North-Holland | location = New York | year = 1976| isbn = 0-444-00249-9 }}
*{{cite book | last = Kozen | first = Dexter C. | coauthors = | title = Automata and Computability  | edition = 1st ed. | publisher = Springer-Verlag | location = New York | year = 1997| isbn = 0-387-94907-0}}
*{{Citiranje knjige | last = Kozen | first = Dexter C. | coauthors = | title = Automata and Computability  | edition = 1st ed. | publisher = Springer-Verlag | location = New York | year = 1997| isbn = 0-387-94907-0}}
*{{cite book | last = Lewis| first = Harry R.| coauthors = Christos H. Papadimitriou| title = Elements of the Theory of Computation | edition = 2nd | publisher = Prentice-Hall | location = Upper Saddle River, New Jersey | year = 1998| isbn = 0-13-262478-8 }}
*{{Citiranje knjige | last = Lewis| first = Harry R.| coauthors = Christos H. Papadimitriou| title = Elements of the Theory of Computation | edition = 2nd | publisher = Prentice-Hall | location = Upper Saddle River, New Jersey | year = 1998| isbn = 0-13-262478-8 }}
*{{cite book | last = Linz| first = Peter| coauthors = | title = Formal Languages and Automata | edition = 4th | publisher = Jones and Bartlett | location = Sudbury, MA | year = 2006| isbn = 978-0-7637-3798-6 }}
*{{Citiranje knjige | last = Linz| first = Peter| coauthors = | title = Formal Languages and Automata | edition = 4th | publisher = Jones and Bartlett | location = Sudbury, MA | year = 2006| isbn = 978-0-7637-3798-6 }}
*{{cite book | last = Minsky| first = Marvin| coauthors = | title = Computation: Finite and Infinite Machines| edition = 1st | publisher = Prentice-Hall | location = New Jersey | year = 1967| isbn = }} Minsky na stranicama 11-20 definira što je "stanje" u kontekstu konačnih automata. Njegov dijagram stanja je nekonvencijalan, Izvrsno, iako relativno čitljivo, ponekad čak i smiješno.
*{{Citiranje knjige | last = Minsky| first = Marvin| coauthors = | title = Computation: Finite and Infinite Machines| edition = 1st | publisher = Prentice-Hall | location = New Jersey | year = 1967| isbn = }} Minsky na stranicama 11-20 definira što je "stanje" u kontekstu konačnih automata. Njegov dijagram stanja je nekonvencijalan, Izvrsno, iako relativno čitljivo, ponekad čak i smiješno.
* {{cite book|author = [[Christos Papadimitriou]] | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st edition | isbn = 0-201-53082-1}}
* {{Citiranje knjige|author = [[Christos Papadimitriou]] | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st edition | isbn = 0-201-53082-1}}
*{{cite book | last = Pippenger| first = Nicholas| coauthors = | title = Theories of Computability| edition = 1st | publisher = Cambridge University Press| location = Cambridge, England | year = 1997| isbn = 0-521-55380-6 (hc)}} Srž ovog teksta je apstraktna algebra, što je čini naprednijom i nešto manje pristušačnom od ostalih.
*{{Citiranje knjige | last = Pippenger| first = Nicholas| coauthors = | title = Theories of Computability| edition = 1st | publisher = Cambridge University Press| location = Cambridge, England | year = 1997| isbn = 0-521-55380-6 (hc)}} Srž ovog teksta je apstraktna algebra, što je čini naprednijom i nešto manje pristušačnom od ostalih.
*{{cite book | last = Rodger| first = Susan| coauthors = Thomas Finley| title = JFLAP: An Interactive Formal Languages and Automata Package | edition = 1st | publisher = Jones and Bartlett | location = Sudbury, MA | year = 2006| isbn = 0763738344 }}
*{{Citiranje knjige | last = Rodger| first = Susan| coauthors = Thomas Finley| title = JFLAP: An Interactive Formal Languages and Automata Package | edition = 1st | publisher = Jones and Bartlett | location = Sudbury, MA | year = 2006| isbn = 0763738344 }}
*{{cite book | last = Sipser| first = Michael | coauthors = | title = Introduction to the Theory of Computation, Second Edition | edition = 2nd | publisher = Thomson Course Technology | location = Boston Mass | year = 2006| isbn = 0-534-95097-3 }} cf. Konačni automati u poglavlju 29.
*{{Citiranje knjige | last = Sipser| first = Michael | coauthors = | title = Introduction to the Theory of Computation, Second Edition | edition = 2nd | publisher = Thomson Course Technology | location = Boston Mass | year = 2006| isbn = 0-534-95097-3 }} cf. Konačni automati u poglavlju 29.
*{{cite book | last = Wood| first = Derick | coauthors = | title = Theory of Computation | edition = 1st | publisher = Harper & Row, Publishers, Inc.| location = New York | year = 1987| isbn = 0-06-047208-1 }}
*{{Citiranje knjige | last = Wood| first = Derick | coauthors = | title = Theory of Computation | edition = 1st | publisher = Harper & Row, Publishers, Inc.| location = New York | year = 1987| isbn = 0-06-047208-1 }}


=== Apstraktni strojevi stanja u teoretskom računarstvu ===
=== Apstraktni strojevi stanja u teoretskom računarstvu ===
Redak 155: Redak 155:
=== Strojno učenje koristeći algoritme zasnovane na konačnim automatima ===
=== Strojno učenje koristeći algoritme zasnovane na konačnim automatima ===


*{{cite book | last = Mitchell| first = Tom M. | coauthors = | title = Machine Learning | edition = 1st | publisher = WCB/McGraw-Hill Corporation | location = New York | year = 1997| isbn = 0-07-042807-7}} Širok prikaz iako temeljit i ponekad težak, namijenjen računalnim znanstvenicima i inženjerima. Poglavlje 13 ''Reinforcement Learning'' barata sa robotskim učenjem koje uključuje algoritme poput onih zasnovanih na strojevima stanja.
*{{Citiranje knjige | last = Mitchell| first = Tom M. | coauthors = | title = Machine Learning | edition = 1st | publisher = WCB/McGraw-Hill Corporation | location = New York | year = 1997| isbn = 0-07-042807-7}} Širok prikaz iako temeljit i ponekad težak, namijenjen računalnim znanstvenicima i inženjerima. Poglavlje 13 ''Reinforcement Learning'' barata sa robotskim učenjem koje uključuje algoritme poput onih zasnovanih na strojevima stanja.


=== Sklopovsko inženjerstvo: minimizacija stanja i sinteza sekvencijalnih sklopova ===
=== Sklopovsko inženjerstvo: minimizacija stanja i sinteza sekvencijalnih sklopova ===


*{{cite book | last = Booth| first = Taylor L. | coauthors = | title = Sequential Machines and Automata Theory | edition = 1st | publisher = John Wiley and Sons, Inc. | location = New York | year = 1967| id = Library of Congress Card Catalog Number 67-25924}} Opširna knjiga namijenjena specijalistima, napisana i za teoretske računalne znanstvenike i za električne inženjere. Uključuje detaljna objašnjenja tehnika minimizacije stanja, KA, Turingovih strojeva, Markovljevih procesa i neodlučivosti. Izvrstan tretman Markovljevih procesa.
*{{Citiranje knjige | last = Booth| first = Taylor L. | coauthors = | title = Sequential Machines and Automata Theory | edition = 1st | publisher = John Wiley and Sons, Inc. | location = New York | year = 1967| id = Library of Congress Card Catalog Number 67-25924}} Opširna knjiga namijenjena specijalistima, napisana i za teoretske računalne znanstvenike i za električne inženjere. Uključuje detaljna objašnjenja tehnika minimizacije stanja, KA, Turingovih strojeva, Markovljevih procesa i neodlučivosti. Izvrstan tretman Markovljevih procesa.
*{{cite book | last = Booth| first = Taylor L. | coauthors = | title = Digital Networks and Computer Systems| edition = 1st | publisher = John Wiley and Sons, Inc. | location = New York | year = 1971| isbn = 0-471-08840-4}} Namijenjeno električnim inženjerima. Fokusiranije, manje zahtijevno od prethodne knjige. Njegov tretman računala je zastario. Zanimljiv pokušaj definiranja "algoritma".
*{{Citiranje knjige | last = Booth| first = Taylor L. | coauthors = | title = Digital Networks and Computer Systems| edition = 1st | publisher = John Wiley and Sons, Inc. | location = New York | year = 1971| isbn = 0-471-08840-4}} Namijenjeno električnim inženjerima. Fokusiranije, manje zahtijevno od prethodne knjige. Njegov tretman računala je zastario. Zanimljiv pokušaj definiranja "algoritma".
*{{cite book | last = McCluskey| first = E. J. | coauthors = | title = Introduction to the Theory of Switching Circuits | edition = 1st | publisher = McGraw-Hill Book Company,Inc. | location = New York | year = 1965| id = Library of Congress Card Catalog Number 65-17394}} Namijenjeno sklopovskim električnim inženjerima. Uključuje detaljna objašnjenja tehnika minimizacije stanja i tehnikama sinteze kombinatornih logičkih sklopova.
*{{Citiranje knjige | last = McCluskey| first = E. J. | coauthors = | title = Introduction to the Theory of Switching Circuits | edition = 1st | publisher = McGraw-Hill Book Company,Inc. | location = New York | year = 1965| id = Library of Congress Card Catalog Number 65-17394}} Namijenjeno sklopovskim električnim inženjerima. Uključuje detaljna objašnjenja tehnika minimizacije stanja i tehnikama sinteze kombinatornih logičkih sklopova.
*{{cite book | last = Hill| first = Fredrick J. | coauthors =Gerald R. Peterson | title = Introduction to the Theory of Switching Circuits | edition = 1st | publisher = McGraw-Hill Book Company | location = New York | year = 1965| id = Library of Congress Card Catalog Number 65-17394}} Namijenjeno sklopovskim električnim inženjerima. Izvrsna objašnjenja tehnika minimizacije stanja i tehnika sinteze kombinatornih i sekvencijalnih logičkih sklopova.
*{{Citiranje knjige | last = Hill| first = Fredrick J. | coauthors =Gerald R. Peterson | title = Introduction to the Theory of Switching Circuits | edition = 1st | publisher = McGraw-Hill Book Company | location = New York | year = 1965| id = Library of Congress Card Catalog Number 65-17394}} Namijenjeno sklopovskim električnim inženjerima. Izvrsna objašnjenja tehnika minimizacije stanja i tehnika sinteze kombinatornih i sekvencijalnih logičkih sklopova.


=== Konačni Markovljevi ulančani procesi ===
=== Konačni Markovljevi ulančani procesi ===
Redak 168: Redak 168:
Konačni procesi Markovljevih lanaca su poznati i kao [[podposmak konačnog tipa|podposmaci konačnog tipa]].
Konačni procesi Markovljevih lanaca su poznati i kao [[podposmak konačnog tipa|podposmaci konačnog tipa]].


*{{cite book | last = Booth| first = Taylor L. | coauthors = | title = Sequential Machines and Automata Theory | edition = 1st | publisher = John Wiley and Sons, Inc. | location = New York | year = 1967| id = Library of Congress Card Catalog Number 67-25924}} Opširna knjiga namijenjena specijalistima, napisana i za teoretske računalne znanstvenike i za električne inženjere. Uključuje detaljna objašnjenja tehnika minimizacije stanja, KA, Turingovih strojeva, Markovljevih procesa i neodlučivosti. Izvrstan tretman Markovljevih procesa.
*{{Citiranje knjige | last = Booth| first = Taylor L. | coauthors = | title = Sequential Machines and Automata Theory | edition = 1st | publisher = John Wiley and Sons, Inc. | location = New York | year = 1967| id = Library of Congress Card Catalog Number 67-25924}} Opširna knjiga namijenjena specijalistima, napisana i za teoretske računalne znanstvenike i za električne inženjere. Uključuje detaljna objašnjenja tehnika minimizacije stanja, KA, Turingovih strojeva, Markovljevih procesa i neodlučivosti. Izvrstan tretman Markovljevih procesa.
*{{cite book | last = Kemeny| first = John G. | coauthors = Hazleton Mirkil, J. Laurie Snell, Gerald L. Thompson | title = Finite Mathematical Structures| edition = 1st | publisher = Prentice-Hall, Inc. | location = Englewood Cliffs, N.J. | year = 1959| id = Library of Congress Card Catalog Number 59-12841}} Klasik. cf. poglavlje 6 "Finite Markov Chains"
*{{Citiranje knjige | last = Kemeny| first = John G. | coauthors = Hazleton Mirkil, J. Laurie Snell, Gerald L. Thompson | title = Finite Mathematical Structures| edition = 1st | publisher = Prentice-Hall, Inc. | location = Englewood Cliffs, N.J. | year = 1959| id = Library of Congress Card Catalog Number 59-12841}} Klasik. cf. poglavlje 6 "Finite Markov Chains"


{{Formalni jezici i gramatike}}
{{Formalni jezici i gramatike}}

Inačica od 17. studeni 2021. u 05:18

Konačni automat (još i konačni stroj, automat konačnih stanja[1]) je diskretni matematički model koji se sastoji od konačnog broja stanja, prijelaza između tih stanja, i akcija koje obavlja.

Koncepti i vokabular

Stanje sprema informacije o prošlosti, tj. odražava promjene na ulazu od početka sustava do sadašnjosti. Prijelaz indicira promjenu stanja i opisan je uvjetom koji treba biti zadovoljen da bi se prijelaz omogućio. Akcija je opis aktivnosti koja treba biti obavljena u danom trenutku. Postoji nekoliko tipova akcija, ovisno o tipu automata:

Akcija ulaska
izvrši akciju za vrijeme ulaska u stanje
Akcija izlaska
izvrši akciju za vrijeme izlaska iz stanja
Ulazna akcija
izvrši akciju ovisno o trenutnom stanju i ulaznim uvjetima
Prijelazna akcija
izvrši akciju dok se obavlja određeni prijelaz

Konačni automati su najčešće predstavljeni dijagramom stanja ili tablicom prijelaza. Najuobičajenija reprezentacija prikazana je u nastavku odlomka: kombinacija trenutnog stanja (B) i uvjeta (Y) uzrokuje prijelaz u sljedeće stanje (C). Potpune informacije o akcijama mogu biti dodane samo preko fusnota. Definicija konačnog automata koja uključuje potpune informacije o akcijama je moguća koristeći tablice prijelaza.

   Trenutno stanje/
Uvjet
Stanje A Stanje B Stanje C
Uvjet X ... ... ...
Uvjet Y ... Stanje C ...
Uvjet Z ... ... ...
Tablica prijelaza

Pored uporabe u modeliranju reaktivnih sustava poput onih ovdje predstavljenih, uporaba konačnih automata je značajna u mnogim različitim područjima, uključujući elektrotehniku, lingvistiku, računarstvo, filozofiju, biologiju, matematiku i logiku. Konačni automati su klasa automata proučavana u teoriji automata i teoriji računanja

U računarstvu, konačni automati se koriste za modeliranje ponašanja aplikacije, dizajn digitalnih sustava, programsko inženjerstvo, jezične procesore, mrežne protokole te proučavanje računanja i jezika.

Razredba

Postoje dvije različite skupine: prihvatitelji/priznavatelji i transduktori.

Prihvatitelji i prepoznavatelji

Slika 2, konačni automat prihvatitelj: parsiranje riječi nice

Prihvatitelji i prepoznavatelji (također i slijedni detektori) stvaraju binarni izlaz, govoreći da ili ne kao odgovor na pitanje prihvaća li stroj ulaz ili ne. Za sva stanja konačnog automata kažemo da su ili prihvatljiva ili neprihvatljiva. U trenutku kad je sav ulaz obrađen, ukoliko je trenutno stanje prihvatljivo, ulaz je prihvaćen; inače je odbijen. U pravilu su ulazi simboli (karakteri); akcije se ne koriste. Primjer na slici 2 prikazuje konačni automat koji prihvaća engl. riječ nice - u ovom konačnom automatu jedino prihvatljivo stanje je pod brojem 7.

Stroj može biti opisan i definiranjem jezika koji bi sadržavao sve riječi koje stroj prihvaća i nijednu od onih koje odbija; kažemo da tada taj jezik stroj prihvaća. Prema definiciji, jezik koji prihvaća neki konačni automat je regularni jezik, odnosno jezik je regularan ako postoji neki konačni automat koji ga prihvaća (usp. Kleenejev teorem).

Početno stanje

Početno je stanje obično naznačeno strelicom koja "pokazuje ni od kuda" (Sipser (2006.) str. 34)

Prihvatljivo stanje

Prihvatljivo stanje (ponekad se naziva i prihvaćajuće stanje) je stanje u kojem je stroj uspješno obavio svoj namjenski postupak. Obično je predstavljen dvostruko koncentričnim krugom.

Primjer prihvatljivog stanja se pojavljuje na lijevoj strani ovog dijagrama determinističkog konačnog automata koji odlučuje sadrži li binarni ulaz paran broj znamenki 0.

S1 (koji je također i početno stanje) indicira stanje u kojem je pročitan paran broj znamenki 0 te je stoga definiran i kao prihvatljivo stanje.

Transduktori

Transduktori generiraju izlaz na osnovu danog ulaza i/ili stanja koristeći akcije. Koriste se za upravljačke primjene. Ovdje razlikujemo dvije vrste:

Mooreov automat
Konačni automat koristi samo akcije ulaska, tj. izlaz ovisi samo o stanju. Prednost Mooreovog modela jest pojednostavljenje ponašanja. Primjer na slici 3 prikazuje Mooreov konačni automat vrata lifta. Stroj stanja prepoznaje dvije naredbe: command_open i command_close koje okidaju promjene stanja. Akcija ulaska (E:) u stanju Opening pokreće motor koji otvara vrata, akcija ulaska u stanju Closing pokreće motor u drugom smjeru zatvarajući vrata. Stanja Opened i Closed ne obavljanju nikakve akcije, već samo služe za signalizaciju vanjskom svijetu (npr. ostalim strojevima stanja) situacije: "vrata su zatvorena" ili "vrata su otvorena".
Slika 4, transduktorski konačni automat: primjer Mealyjevog modela
Mealyev automat
Konačni automat koristi samo ulazne akcije, tj. izlaz ovisi o ulazu i stanju. Uporaba Mealyjevog automata često vodi ka redukciji broja stanja. Primjer na slici 4 pokazuje Mealyjev konačni automat koji ostvaruje isto ponašanje kao i onaj u primjeru Mooreovog automata (ponašanje ovisi o izvršnom modelu ostvarenog konačnog automata i radit će za npr. virtualni KA ali ne i za događajem upravljani KA). Dvije su ulazne akcije (I:): "pokreni motor za zatvoriti vrata ako dođe naredba command_close" i "pokreni motor u drugom smjeru za otvoriti vrata ako dođe naredba command_open".

U praksi se koriste miješani modeli

Više se detalja o razlikama i uporabi Mooreovih i Mealyjevih modela, uključujući izvodivi primjer, može naći u vanjskoj tehničkoj bilješki "Mooreov ili Mealyjev model?"

Daljnja je razlika između determinističkih (DKA) i nedeterminističkih (NKA, PNKA) automata. U determinističkim automatima, za svako stanje postoji točno jedan prijelaz za svaki mogući ulaz. U nedeterminističkim automatima može postojati više od jednog prijelaza za dani ulaz. Ova je razlika važna u praksi, ali ne i u teoriji, jer postoji algoritam koji može pretvoriti svaki NKA u istovjetni DKA, iako ova pretvorba obično znatno poveća složenost automata.

Konačni se automat sa samo jednim stanjem zove kombinatorni konačni automat i koristi samo ulazne akcije. Ovaj koncept je koristan u slučajevima kada se zahtijeva da više konačnih automata rade zajednički, te kad je zgodno razmatrati samo čisto kombinatorni dio kao oblik konačnog automata kako bi se prilagodilo alatima za dizajniranje.

Logika konačnog automata

Slika 5, logika konačnog automata

Sljedeće stanje i izlaz konačnog automata je funkcija ulaza i trenutnog stanja. Logika konačnog automata je prikazana na slici 5.

Matematički model

Ovisno o tipu postoji nekoliko definicija. Konačni automat prihvatitelj je petorka , gdje:

  • je ulazna abeceda (konačan neprazan skup simbola).
  • je konačan neprazan skup stanja.
  • je početno stanje, element skupa . U nedeterminističkom konačnom automatu, je skup početnih stanja.
  • je funkcija prijelaza: .
  • je skup konačnih stanja, (potencijalno prazan) podskup od .

Transduktorski konačni automat je šestorka , gdje:

  • je ulazna abeceda (konačan neprazan skup simbola).
  • je izlazna abeceda (konačan neprazan skup simbola).
  • je konačan neprazan skup stanja.
  • je početno stanje, element skupa . U nedeterminističkom konačnom automatu, je skup početnih stanja.
  • je funkcija prijelaza: .
  • je izlazna funkcija.

Ako je izlazna funkcija funkcija stanja i ulazne abecede(), tad ta definicija odgovora Mealyjevom modelu. Ako izlazna funkcija ovisi samo o stanju (), tad ta definicija odgovora Mooreovom moelu. Konačni automat bez izlazne funkcije je poznat kao poluautomat ili prijelazni sustav.

Optimizacija

Optimiziranje konačnog automata znači pronalaženje stroja s minimalnim brojem stanja koji obavlja istu funkciju. Jedna je mogućnost korištenja implikacijske tablice ili Mooreova redukcijskog postupka. Druga je mogućnost odozdorni algoritam za acikličke konačne automate.

Implementacija

Sklopovske primjene

Slika 6, dijagram sklopa za 4-bitni TTL brojač, vrstu stroja stanja

U digitalnim krugovima, konačni automat može biti načinjen koristeći programibilni logički uređaj, programibilni logički kontroler, logička vrata i bistabile ili releje. Konkretnije, sklopovsko ostvarenje zahtijeva registar za pohranjivanje varijabli stanja, blok kombinatorne logike koji određuje prijelaz stanja i drugi blok kombinatorne logike koji određuje izlaz konačnog automata. Jedan od klasičnih sklopovskih ostvarenja jest Richardov kontroler.

Programske primjene

Sljedeći su koncepti često rabljeni za razvoj programske podrške konačnim automatima:

Vidi još

Vanjske poveznice

Izvori

  1. Kiš Miroslav, Englesko-hrvatski i hrvatsko-engleski informatički rječnik, Zagreb, Naklada Ljevak, 2000., str. 389

Općenito

  • Wagner, F., "Modeling Software with Finite State Machines: A Practical Approach", Auerbach Publications, 2006, ISBN 0-8493-8086-3.
  • Cassandras, C., Lafortune, S., "Introduction to Discrete Event Systems". Kluwer, 1999, ISBN 0-7923-8609-4.
  • Timothy Kam, Synthesis of Finite State Machines: Functional Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9842-4
  • Tiziano Villa, Synthesis of Finite State Machines: Logic Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9892-0
  • Carroll, J., Long, D., Theory of Finite Automata with an Introduction to Formal Languages. Prentice Hall, Englewood Cliffs, 1989.
  • Kohavi, Z., Switching and Finite Automata Theory. McGraw-Hill, 1978.
  • Gill, A., Introduction to the Theory of Finite-state Machines. McGraw-Hill, 1962.
  • Ginsburg, S., An Introduction to Mathematical Machine Theory. Addison-Wesley, 1962.

Konačni automati (teorija automata) u teoretskom računarstvu

  • Arbib, Michael A. (1969). Theories of Abstract Automata (1st ed. ed.). Englewood Cliffs, N.J.: Prentice-Hall, Inc.. ISBN 0-13-913368-2 
  • Bobrow, Leonard S.; Michael A. Arbib (1974). Discrete Mathematics: Applied Algebra for Computer and Information Science (1st ed. ed.). Philadelphia: W. B. Saunders Company, Inc.. ISBN 0-7216-1768-9 
  • Booth, Taylor L. (1967). Sequential Machines and Automata Theory (1st ed.). New York: John Wiley and Sons, Inc.. Library of Congress Card Catalog Number 67-25924  Opširna knjiga namijenjena specijalistima, napisana i za teoretske računalne znanstvenike i za električne inženjere. Uključuje detaljna objašnjenja tehnika minimizacije stanja, KA, Turingovih strojeva, Markovljevih procesa i neodlučivosti. Izvrstan tretman Markovljevih procesa.
  • Boolos, George; Richard Jeffrey (24. prosinac 1999.). Computability and Logic (3rd ed. ed.). Cambridge, England: Cambridge University Press. ISBN 0-521-20402-X  Izvrsna knjiga. Izdaje se opetovano u različitim edicijama od 1974. (1974., 1980., 1989., 1999.).
  • Brookshear, J. Glenn (1989). Theory of Computation: Formal Languages, Automata, and Complexity. Redwood City, California: Benjamin/Cummings Publish Company, Inc.. ISBN 0-8053-0143-7  Pristupa Church-Turingovoj tezi iz tri kuta: razine konačnih automata kao prihvatitelja formalnih jezika, teorije primitivne i paricijalne rekurzije, te moći običnih programskih jezika u svrhu ostvarenja algoritama, sve u jednom debelom svesku.
  • Davis, Martin; Ron Sigal, Elaine J. Weyuker (1994). Second Edition: Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science (2nd ed. ed.). San Diego: Academic Press, Harcourt, Brace & Company. ISBN 0-12-206382-1 
  • Hopcroft, John; Jeffrey Ullman (1979). Introduction to Automata Theory, Languages and Computation (1st ed. ed.). Reading Mass: Addison-Wesley. ISBN 0-201-02988-X  Teška knjiga usredotočena na probleme strojnog tumačenja formalnih jezika, NP-potpunosti itd.
  • Hopcroft, John E.; Rajeev Motwani, Jeffrey D. Ullman (2001). Introduction to Automata Theory, Languages, and Computation (2nd ed. ed.). Reading Mass: Addison-Wesley. ISBN 0-201-44124-1  Različita i nešto manje zastrašujuća od prvog izdanja.
  • Hopkin, David; Barbara Moss (1976). Automata. New York: Elsevier North-Holland. ISBN 0-444-00249-9 
  • Kozen, Dexter C. (1997). Automata and Computability (1st ed. ed.). New York: Springer-Verlag. ISBN 0-387-94907-0 
  • Lewis, Harry R.; Christos H. Papadimitriou (1998). Elements of the Theory of Computation (2nd ed.). Upper Saddle River, New Jersey: Prentice-Hall. ISBN 0-13-262478-8 
  • Linz, Peter (2006). Formal Languages and Automata (4th ed.). Sudbury, MA: Jones and Bartlett. ISBN 978-0-7637-3798-6 
  • Minsky, Marvin (1967). Computation: Finite and Infinite Machines (1st ed.). New Jersey: Prentice-Hall  Minsky na stranicama 11-20 definira što je "stanje" u kontekstu konačnih automata. Njegov dijagram stanja je nekonvencijalan, Izvrsno, iako relativno čitljivo, ponekad čak i smiješno.
  • Christos Papadimitriou (1993). Computational Complexity (1st edition ed.). Addison Wesley. ISBN 0-201-53082-1 
  • Pippenger, Nicholas (1997). Theories of Computability (1st ed.). Cambridge, England: Cambridge University Press. ISBN 0-521-55380-6 (hc) nevaljani ISBN  Srž ovog teksta je apstraktna algebra, što je čini naprednijom i nešto manje pristušačnom od ostalih.
  • Rodger, Susan; Thomas Finley (2006). JFLAP: An Interactive Formal Languages and Automata Package (1st ed.). Sudbury, MA: Jones and Bartlett. ISBN 0763738344 
  • Sipser, Michael (2006). Introduction to the Theory of Computation, Second Edition (2nd ed.). Boston Mass: Thomson Course Technology. ISBN 0-534-95097-3  cf. Konačni automati u poglavlju 29.
  • Wood, Derick (1987). Theory of Computation (1st ed.). New York: Harper & Row, Publishers, Inc.. ISBN 0-06-047208-1 

Apstraktni strojevi stanja u teoretskom računarstvu

Strojno učenje koristeći algoritme zasnovane na konačnim automatima

  • Mitchell, Tom M. (1997). Machine Learning (1st ed.). New York: WCB/McGraw-Hill Corporation. ISBN 0-07-042807-7  Širok prikaz iako temeljit i ponekad težak, namijenjen računalnim znanstvenicima i inženjerima. Poglavlje 13 Reinforcement Learning barata sa robotskim učenjem koje uključuje algoritme poput onih zasnovanih na strojevima stanja.

Sklopovsko inženjerstvo: minimizacija stanja i sinteza sekvencijalnih sklopova

  • Booth, Taylor L. (1967). Sequential Machines and Automata Theory (1st ed.). New York: John Wiley and Sons, Inc.. Library of Congress Card Catalog Number 67-25924  Opširna knjiga namijenjena specijalistima, napisana i za teoretske računalne znanstvenike i za električne inženjere. Uključuje detaljna objašnjenja tehnika minimizacije stanja, KA, Turingovih strojeva, Markovljevih procesa i neodlučivosti. Izvrstan tretman Markovljevih procesa.
  • Booth, Taylor L. (1971). Digital Networks and Computer Systems (1st ed.). New York: John Wiley and Sons, Inc.. ISBN 0-471-08840-4  Namijenjeno električnim inženjerima. Fokusiranije, manje zahtijevno od prethodne knjige. Njegov tretman računala je zastario. Zanimljiv pokušaj definiranja "algoritma".
  • McCluskey, E. J. (1965). Introduction to the Theory of Switching Circuits (1st ed.). New York: McGraw-Hill Book Company,Inc.. Library of Congress Card Catalog Number 65-17394  Namijenjeno sklopovskim električnim inženjerima. Uključuje detaljna objašnjenja tehnika minimizacije stanja i tehnikama sinteze kombinatornih logičkih sklopova.
  • Hill, Fredrick J.; Gerald R. Peterson (1965). Introduction to the Theory of Switching Circuits (1st ed.). New York: McGraw-Hill Book Company. Library of Congress Card Catalog Number 65-17394  Namijenjeno sklopovskim električnim inženjerima. Izvrsna objašnjenja tehnika minimizacije stanja i tehnika sinteze kombinatornih i sekvencijalnih logičkih sklopova.

Konačni Markovljevi ulančani procesi

"Možemo zamisliti Markovljeve lance kao proces koji se sukcesivno pomiču kroz slijed stanja s1, s2, ..., sr. ... ako je u stanju si tada se pomiče na sljedeće stanje sj sa vjerojatnošću pij. Ove se vjerojatnosti mogu prikazati u obliku matrice prijelaza" (Kemeny (1959), str. 384)

Konačni procesi Markovljevih lanaca su poznati i kao podposmaci konačnog tipa.

  • Booth, Taylor L. (1967). Sequential Machines and Automata Theory (1st ed.). New York: John Wiley and Sons, Inc.. Library of Congress Card Catalog Number 67-25924  Opširna knjiga namijenjena specijalistima, napisana i za teoretske računalne znanstvenike i za električne inženjere. Uključuje detaljna objašnjenja tehnika minimizacije stanja, KA, Turingovih strojeva, Markovljevih procesa i neodlučivosti. Izvrstan tretman Markovljevih procesa.
  • Kemeny, John G.; Hazleton Mirkil, J. Laurie Snell, Gerald L. Thompson (1959). Finite Mathematical Structures (1st ed.). Englewood Cliffs, N.J.: Prentice-Hall, Inc.. Library of Congress Card Catalog Number 59-12841  Klasik. cf. poglavlje 6 "Finite Markov Chains"
Teorija automata: formalni jezici i formalne gramatike
Chomskyjeva
hijerarhija
Gramatike Jezici Minimalni
automat
Tip 0 Neograničenih produkcija Rekurzivno prebrojiv Turingov stroj
n/a (nema uobičajenog imena) Rekurzivni Odlučitelj
Tip 1 Kontekstno ovisna Kontekstno ovisni Linearno ograničen
n/a Indeksirana Indeksirani Ugniježđenog stoga
Tip 2 Kontekstno neovisna Kontekstno neovisni Nedeterministički potisni
n/a Deterministička kontekstno neovisna Deterministički kontekstno neovisni Deterministički potisni
Tip 3 Regularna Regularni Konačni
Svaka kategorija jezika ili gramatika je pravi podskup nadređene kategorije.