Mașina de stat - fluxul abstract de ieșire automat, numărul de stări posibile este finit. Rezultatul a mașinii este determinată de starea sa finală.
Există diverse variante de realizare ale unui loc de muncă automat finit. De exemplu, aparatul de stat poate fi specificată utilizând cinci parametri: în cazul în care:
- Q - o multitudine de stări ale automatului;
- q0 - inițial (start) automaton stare ();
- F - set de final (sau permite) prevede astfel încât;
- Σ - alfabetul de intrare admisibil (set finit de posibile simboluri de intrare), care sunt formate din rânduri de citire optică;
- δ - maparea predeterminată într-o multitudine de subgrupele de set Q: (uneori numită funcția tranziții δ automatului).
Automată începe în Q0 de stat. citind un caracter din șirul de intrare. Considerat un simbol al mașinii se traduce într-o nouă stare de Q în conformitate cu funcția de tranziție. Dacă la finalizarea citirii cuvântului de intrare (șir de caractere) mașină este într-unul dintre statele care acceptă, cuvântul „luat“ în mod automat. În acest caz, se spune că aparține limbajului mașinii. În caz contrar, cuvântul „respins“.
Alte modalități de a descrie
- Diagrama de stat (sau, uneori, Graficul de tranziție) - reprezentarea grafică a unui set de stări și funcția de tranziție. Este un grafic încărcat-un singur sens. noduri - SC de stat, nervurile - tranzițiile de la un stat la altul, iar sarcina - simboluri la care tranziția activă. În cazul în care tranziția de la q1 la q2 poate fi realizată cu apariția unuia mai multor personaje, pe graficul arc (ramura a graficului) trebuie să fie etichetate toate.
- Masa de tranziție - tabel funcție vizualizare δ. De obicei, în acest tabel fiecare rând corespunde unui stat, iar coloana - un simbol de intrare validă. Celula de la intersecția rândului și coloanei înregistrate de acțiune care trebuie să se efectueze automat, dacă într-o situație în care el a fost în această stare, el a luat de intrare de caractere.
determinism
Mașini de stat finite sunt împărțite în deterministe și non-determinist.
Determinist automatelor finite
- automat finit determinist (DFA) este o mașină în care există fiecare secvență de simboluri de intrare de un singur stat, la care mașina se poate deplasa în afara curentului.
- automaton finit nedeterminist (RNP) este o generalizare a deterministic. Mașini indeterminare se realizează în două moduri:
Sunt pasaje marcate cu ε lanț gol
De la un stat la câteva pasaje care sunt marcate cu același simbol
Dacă luăm în considerare cazul în care aparatul este setat după cum urmează: în cazul în care:
- S - setul de pornire automaton de stat, astfel încât;
Apoi, există este al treilea semn al nedeterminismul - prezența câtorva (de pornire) condițiile inițiale în aparat.
Există o teoremă, care prevede că „orice automat finit non-determinist poate fi transformat într-un determinist, astfel încât limba lor este aceeași“ (astfel de mașini sunt numite echivalente). Cu toate acestea, din moment ce numărul stărilor în echivalent DFA la cele mai grave crește exponențial cu creșterea cantității de ARN de plecare ale statelor, în practică, astfel de determinization nu este întotdeauna posibil. În plus, o mașină de stare finită, cu un randament general, nu determinization cedat.
În virtutea ultimelor două observații, în ciuda marea complexitate a finite automate non-determinist, pentru probleme legate de procesarea de text, este în principal aplică ANV.
Automate și regulate de limbi
Pentru a automatului poate fi determinată limba (set de cuvinte) în alfabet sigma, reprezintă - așa-numitul cuvânt, care atunci când intră în tranzițiile mașinii de la starea inițială la una dintr-o multitudine de stări F.
Teorema Kleene lui afirmă că clasa de limbi care pot fi reprezentate prin automate finite coincide cu clasa limbilor regulate. În plus, această clasă coincide cu clasa de limbi definite de gramatici regulate.
limbaje de programare specializate
- Secvențială SFC Function Chart (Sequential Function Chart) - limbaj de programare grafic este utilizat pe scară largă pentru programarea automatelor industriale (PLC).
Programul SFC este descris într-o secvență schematică a etapelor, tranzițiile combinate.
Dezvoltarea de modele folosind finite automate
Mașini de stat finite ne permit de a construi un model de sisteme de procesare paralele, cu toate acestea, pentru a modifica numărul de procese paralele într-un astfel de model este necesar pentru a face modificări semnificative în modelul în sine. În plus, o încercare de a dezvolta un model complex de pe masina tinta va conduce la o creștere rapidă a numărului de state care, eventual, va face dezvoltarea unui astfel de model este extrem de obositor. După cum sa menționat mai sus, acestea din urmă problema poate fi rezolvată prin utilizarea de mașini non-determinist.
notițe
Vezi ce „mașina de stat“ în alte dicționare:
Mașina de stat - un model matematic al dispozitivului cu memorie finită. mașină de stat procesează multitudinea de semnale binare de intrare în multitudinea de semnale de ieșire. Se face deosebirea între mașinile de stat sincrone și asincrone. În limba engleză: finita mașină de stat ... Vezi dicționar financiar
mașină de stat - baigtinis statusas T sritis Automate AUTOMATIKA atitikmenys: angl. automaton finit; mașină cu stare finită vok. endlicher Automat, m; Finalautomat, m rus. mașină de stat, m pranc. automatizarea finală, m; automatizarea Fini, m; automatizarea terminalului, m; ... ... Automatikos terminų žodynas
END AUTOMAT - automată, să se cerned set de stări și o pluralitate de semnale de intrare și de ieșire sunt finite. C. a. Acesta poate fi un model de tehnologie. dispozitive (computer, dispozitiv de releu) sau Biol. (Sistemul idealizează. Animal nervos) sistem. Important ... ... Mare Dicționarul Enciclopedic Politehnica
Memoria mașinii de stat - Modelul matematic al mașinii de stare cu dispozitive de memorie, al căror comportament depinde de condițiile de intrare și starea anterioară. Pentru o descriere a unui limbaj mașină de stat a sistemelor utilizate de operator cu memorie, regulat ... ... Wikipedia
Moore automaton - (al doilea tip automat) în teoria de calcul a mașinii de stat, valoarea semnalului de ieșire care depinde numai de starea curentă a automatului, și nu depinde în mod direct, spre deosebire de automatului Mealy, din valorile de intrare. Moore automaton numit ... Wikipedia
- Programare: limbaje formale si compilatoare. Manual pentru licee. Malyavko AA Cartea prezintă fundamentele teoretice ale limbaj de definire a aparatelor (expresii regulate) și sintaxa (gramatica formală) limbaje de programare, elemente ale teoriei automate finite ... Read More Cumpără pentru 1200 de ruble
- Mașina de stat. Dzhessi Rassel. Această carte va fi făcută în conformitate cu comanda pe tehnologia de imprimare Tehnologie-on-Demand. Conținutul de calitate înaltă prin articole wikipedia! Mașina de stat - Automatul abstracte, fără ieșire ... Citește mai mult Cumpără pentru 1147 de ruble
- Programare: limbaje formale si compilatoare. Manual pentru licee. Malyavko AA Cartea prezintă fundamentele teoretice ale limbaj de definire a aparatelor (expresii regulate) și sintaxa (gramatica formală) limbaje de programare, elemente ale teoriei automate finite ... Read More Cumpără pentru 1090 UAH (Ucraina numai)