Automat cu stare finită

O mașină cu stare finită (ASF sau FSA, de la „ automat finit în engleză , la plural: automata fs) sau mașină cu stare finită (FSM, mașină cu stare finită în engleză ) este un model de calcul matematic, este un fel de automat care permite descrierea cu precizie și într-un mod formal comportamentul multor sisteme. Datorită simplității și clarității sale, acest model este foarte popular în inginerie și știință , în special în domeniul informaticii și al cercetării operaționale .

Un automat cu stare finită poate fi utilizat atât pentru modelarea unui sistem existent, cât și pentru modelarea unui nou sistem formal capabil să rezolve unele probleme existente. Așa-numiții recunoscători de limbă și traducători aparțin acestei din urmă categorii. Reprezentarea grafică obișnuită a unui automat cu stare finită este graficul direcționat .

Descriere

În mod specific, cu automatele de stare finită, este posibil să se modeleze toate sistemele care posedă următoarele caracteristici:

Dinamism : caracteristic evoluției în timp trecând de la o stare la alta.
Discreție: caracteristică care indică faptul că variabilele de intrare și stările sistemului de modelat pot fi exprimate cu valori discrete.
Simboluri finite: caracteristică care determină faptul că numărul simbolurilor și stărilor de intrare poate fi reprezentat printr-un număr finit.

Din punct de vedere practic, conceptul de automat cu stare finită este echivalent cu construirea unui dispozitiv mic care, folosind un cap, citește un șir de intrare pe o bandă și îl procesează, folosind un mecanism de calcul foarte simplu și o memorie limitată. Examinarea șirului are loc câte un caracter odată prin etape de calcul precise care implică avansarea capului. Practic un ASF este un caz particular al unei mașini Turing , utilizat pentru elaborarea acelor limbaje care în gramaticile Chomsky sunt definite ca „tip 3” sau obișnuite . Distingem două tipuri de automate cu stare finită: automatele finite deterministe (ASFD) și automatele finite nedeterministe (ASFND).

Tipuri

Automat de stare finită determinist

Același subiect în detaliu: automat determinat cu stări finite .

Un ASF determinist este definit ca un sistem $M=(I,U,S,f,g)$ ${\ displaystyle M = (I, U, S, f, g)}$ ${\ displaystyle M = (I, U, S, f, g)}$ , unde este

$I=\{i_{1},i_{2},\ldots ,i_{n}\}$ ${\ displaystyle I = \ {i_ {1}, i_ {2}, \ ldots, i_ {n} \}}$ ${\ displaystyle I = \ {i_ {1}, i_ {2}, \ ldots, i_ {n} \}}$ set finit de posibile simboluri de intrare
$U=\{u_{1},u_{2},\ldots ,u_{m}\}$ ${\ displaystyle U = \ {u_ {1}, u_ {2}, \ ldots, u_ {m} \}}$ ${\ displaystyle U = \ {u_ {1}, u_ {2}, \ ldots, u_ {m} \}}$ set finit de simboluri de ieșire posibile
$S=\{s_{1},s_{2},\ldots ,s_{h}\}$ ${\ displaystyle S = \ {s_ {1}, s_ {2}, \ ldots, s_ {h} \}}$ ${\ displaystyle S = \ {s_ {1}, s_ {2}, \ ldots, s_ {h} \}}$ ansamblu finit de stări
$f:I\times S\rightarrow S$ ${\ displaystyle f: I \ times S \ rightarrow S}$ ${\ displaystyle f: I \ times S \ rightarrow S}$ funcția de tranziție a stărilor interne succesive, care leagă starea în următoarea instanță de valoarea curentă a intrării și a stării, $S(t+1)=f(I(t),S(t))$ ${\ displaystyle S (t + 1) = f (I (t), S (t))}$ ${\ displaystyle S (t + 1) = f (I (t), S (t))}$
$g:I\times S\rightarrow U$ ${\ displaystyle g: I \ times S \ rightarrow U}$ ${\ displaystyle g: I \ times S \ rightarrow U}$ funcția ieșirilor (posibil parțială), care conectează ieșirea la valoarea curentă a intrării și a stării, $U(t)=g(I(t),S(t))$ ${\ displaystyle U (t) = g (I (t), S (t))}$ ${\ displaystyle U (t) = g (I (t), S (t))}$

Automat cu stare finită nedeterminist

Același subiect în detaliu: automat finit nedeterminist .

Un ASF nedeterminist este definit ca un sistem $M=(I,U,S,f,g)$ ${\ displaystyle M = (I, U, S, f, g)}$ ${\ displaystyle M = (I, U, S, f, g)}$ , unde este

$I=\{i_{1},i_{2},\ldots ,i_{n}\}$ ${\ displaystyle I = \ {i_ {1}, i_ {2}, \ ldots, i_ {n} \}}$ ${\ displaystyle I = \ {i_ {1}, i_ {2}, \ ldots, i_ {n} \}}$ set finit de posibile simboluri de intrare
$U=\{u_{1},u_{2},\ldots ,u_{m}\}$ ${\ displaystyle U = \ {u_ {1}, u_ {2}, \ ldots, u_ {m} \}}$ ${\ displaystyle U = \ {u_ {1}, u_ {2}, \ ldots, u_ {m} \}}$ set finit de simboluri de ieșire posibile
$S=\{s_{1},s_{2},\ldots ,s_{h}\}$ ${\ displaystyle S = \ {s_ {1}, s_ {2}, \ ldots, s_ {h} \}}$ ${\ displaystyle S = \ {s_ {1}, s_ {2}, \ ldots, s_ {h} \}}$ ansamblu finit de stări
$f:I\times S\rightarrow {\mathcal {P}}(S)$ ${\ displaystyle f: I \ times S \ rightarrow {\ mathcal {P}} (S)}$ ${\ displaystyle f: I \ times S \ rightarrow {\ mathcal {P}} (S)}$ funcție de tranziție parțială a stărilor interne succesive, care conectează un subset de S la valoarea curentă a intrării și a stării (deci la un subset de stări posibile în S).
$g:I\times S\rightarrow U$ ${\ displaystyle g: I \ times S \ rightarrow U}$ ${\ displaystyle g: I \ times S \ rightarrow U}$ funcția ieșirilor (posibil parțială), care conectează ieșirea la valoarea curentă a intrării și a stării, $U(t)=f(S(t),I(t))$ ${\ displaystyle U (t) = f (S (t), I (t))}$ ${\ displaystyle U (t) = f (S (t), I (t))}$

Diferența dintre ASFD și ASFND

Diferența dintre cele două tipuri de automate (deja exprimate prin definițiile formale) constă în faptul că în prima, în orice stare este, pentru orice intrare, va exista o singură tranziție, în timp ce în cea de-a doua cel puțin o stare are mai multe calcule posibile pentru anumite caractere de intrare. Rețineți că determinismul este un caz particular de nedeterminism; cu toate acestea, în cazul automatelor cu stare finită, este posibil să treceți cu ușurință de la una la alta. Ideea este de a uni într-o singură stare colectivă [s ₁ , s ₂ , ..., s _k ] stările s ₁ , s ₂ , ..., s _k accesibile cu aceeași intrare, adică cele care determină indeterminarea a automatului.

Reprezentarea funcției de tranziție a unui ASFD

Diagrama de stare a unei mașini Mealy

Diagrama de stare a unei mașini Moore

Putem reprezenta automatele de stare finită cu un tabel ( tabel de tranziție ) sau echivalent cu o matrice (matricea de tranziție). Asociem stările la rânduri și simbolurile de intrare coloanelor. Elementele matricei reprezintă rezultatul aplicării funcției de tranziție.

\	0	1
s ₀	s ₂	s ₁
s ₁	s ₂	s ₁
s ₂	s ₂	s ₁

O altă reprezentare larg utilizată este constituită de diagrama de stare, sau graficul de tranziție, care constă în reprezentarea automatului prin intermediul unui grafic orientat : nodurile reprezintă stările, iar arcele reprezintă tranzițiile, etichetate cu simbolul de intrare care generează tranziția. Puteți marca starea inițială cu un arc care intră din nimic și stările finale cu un cerc dublu.

La aceste reprezentări trebuie adăugată funcția de ieșire corespunzătoare. Diagramele de stare vor fi apoi modificate, așa cum se poate vedea pentru mașinile Mealy și Moore.

Relații cu alte tipuri de mașini

Plase Petri

Un ASF poate fi considerat un anumit tip de rețea Petri .

Automa lui Mealy și Automa lui Moore

În automatul lui Moore , funcția f depinde doar de starea: f = S → U și deci U (t) = f (S (t)). Prin urmare, mașina lui Moore poate fi văzută ca o simplificare a cazului mai generic, în care ieșirea depinde de stare și de intrări. Acest ultim tip de automat se numește automatul lui Mealy .

Variat

Automatele finite, sau chiar automatele cu număr finit, sunt deseori denumite incorect „automate de stat finit” datorită traducerii engleză-italiană a FSA, dar nu statul este finit, ci numărul de state. Conceptul de stare finită reapare în mecanica cuantică și nu are nimic de-a face cu noțiunea de automat finit.

Elemente conexe

Aplicații software

SMCube - un instrument gratuit pentru modelarea, simularea și generarea de cod pentru mașini cu stare finită.

Alte proiecte

Wikiversitatea conține resurse pe automatele cu stare finită
Wikimedia Commons conține imagini sau alte fișiere pe automatele cu stare finită

Teoria automatelor : limbaje formale și gramatici formale
Ierarhia Chomsky	Gramatica formală	Limba	Automat minim
Tipul-0	(nelimitat)	Recursiv enumerabil	Mașină Turing
	(nelimitat)	Recursiv	Decider
Tipul 1	Context dependent	Context dependent	Automat liniar
Tipul 2	Fără context	Fără context	Automat cu baterie ND
Tipul 3	Regulat	Regulat	Stări finite
Fiecare categorie de limbă sau gramatică este un subset adecvat al categoriei imediat deasupra acesteia.

Portal electronic

Portal IT

V · D · M Electronică digitală
Componente	Circuit combinator · Circuit integrat · Poartă logică · Circuit secvențial
Teorie	Semnal discret · boolean algebra · Logic Sinteza · Computational Logic · logica de optimizare · calculatoare Arhitectura · procesare a semnalului digital
Proiecta	Nivelul transferului de înregistrare · Verificarea formală a echivalenței · Circuite sincrone · Circuite asincrone · stare finită automată
Aplicații	Hardware · Digital Audio · Fotografie digitala · Digital Video · Literatură electronice · Telecomunicații