În era tehnologică de astăzi, atât domeniul hardware, cât și cel software au cunoscut o dezvoltare extraordinară. Unul dintre domeniile majore de dezvoltare a fost văzut în metodele de proiectare hardware. Cu tehnologie în creștere , conceptul de hardware - co-proiectare software a fost posibil de implementat. Sunt dezvoltate diferite metode prin care, folosind software se poate proiecta și simula pe deplin sistemele hardware. Una dintre astfel de metode este teoria automatelor. Teoria automatelor este ramura informatică care se ocupă cu proiectarea modelului abstract al dispozitivelor de calcul care urmează automat secvența predeterminată de pași. Acest articol discută informații scurte despre tutorialul automatelor.
Ce este teoria automatelor?
Cuvântul Automate este derivat din greacă, care înseamnă „acțiune de sine”. Un automat este un model matematic al mașinii. Automatul constă în stări și tranziții. Pe măsură ce intrarea este dată automatului, acesta trece la următoarea stare, în funcție de funcția de tranziție. Intrările pentru funcția de tranziție sunt simboluri de stare prezentă și recente. Dacă un automat are un număr finit de stări, acesta este cunoscut sub numele de automate finite sau Mașină de stat finit . Automatele finite sunt reprezentate de un 5-tuplu (Q, ∑, δ, qo, F)
Unde,
Q = Set finit de stări.
∑ = set finit de simboluri numit și Alfabetul automatelor.
δ = funcția de tranziție.
qo = starea inițială a intrării.
F = set de stări finale ale lui Q.
Terminologiile de bază ale teoriei automatelor
Unele dintre terminologiile de bază ale teoriei automatelor sunt:
1 . Alfabet : Orice set finit de simboluri din teoria automatelor este cunoscut sub numele de Alfabet. Reprezentată de litera∑ mulțimea {a, b, c, d, e,} se numește set Alfabet, în timp ce literele setului „a”, „b”, „c”, „d”, „e” se numesc simboluri.
Două . Şir : În automate, un șir este o secvență finită de simboluri luate din setul de alfabet ∑, De exemplu, șirul S = ‘adeaddadc’ este valid pentru setul de alfabet∑ = {a, b, c, d, e,}.
3 . Lungimea șirului : Numărul de simboluri prezente în șir este cunoscut sub numele de Lungimea șirului. Pentru șirul S = ‘adaada’ lungimea șirului este | S | = 6. Dacă lungimea șirului este 0, atunci se numește șir gol.
4 . Kleen Star : Este operatorul unar din setul de simboluri Σ, care dă setul infinit al tuturor șirurilor posibile, inclusiv λ, a tuturor lungimilor posibile peste setul Σ. Este reprezentat de. De exemplu, pentru setul Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.
5 . Kleen Closure : Este setul infinit al tuturor șirurilor posibile ale setului de alfabet, cu excepția lui λ. Se notează cu. Pentru setul Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd, ... ..}.
6 . Limba : Limba este subsetul setului de stele Kleene∑ * pentru un set de alfabet Σ. Limbajul poate fi finit sau infinit. De exemplu, dacă o limbă ia toate șirurile posibile de lungime 2 peste setul Σ = {a, d}, atunci L = {aa, ad, da, dd}.
Limbaje formale și automate
În teoria automatelor, limbajul formal este un set de șiruri, în care se află fiecare șir compus din simboluri aparținând setului alfabet finit Σ. Să luăm în considerare un limbaj de pisică, care poate conține orice șiruri din setul infinit de mai jos ...
Mew!
meww!
mewww !! ……
Setul de alfabet pentru limba pisicii este Σ = {m, e, w,!}. Lăsați acest set să fie utilizat pentru un model de automat de stat finit-m. Apoi, limbajul formal caracterizat de modelul m este notat cu
L (m)
L (m) = {‘mew!’, ‘Meww!’, ‘Mewww’, ...…}
Automatul este util pentru definirea unui limbaj, deoarece poate exprima un set infinit într-o formă închisă. Limbile formale nu sunt la fel ca limbile naturale pe care le vorbim în viața noastră de zi cu zi. Un limbaj formal poate denota diferitele stări ale mașinii, spre deosebire de limbile noastre obișnuite. Limbajul formal este folosit pentru a modela o parte a limbajului natural, cum ar fi sintaxa etc ... Limbajele formale sunt definite de automatele de stare finită. Există două perspective principale ale automatelor de stare finită - Acceptori care pot spune dacă un șir este în limbă, iar al doilea este generatorul care produce numai șirurile în limbă.
Automate finite deterministe
În tipul de automatism determinist, atunci când este dată o intrare, putem determina întotdeauna în ce stare ar fi tranziția. Deoarece acesta este un automat finit, acesta se numește Automate finite deterministe.
Reprezentare grafică
Diagrama de stare este digrafele utilizate pentru reprezentarea grafică a automatelor finite deterministe. Să înțelegem cu un exemplu. Să fie automatele finite deterministe ...
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} iar funcția de tranziție să fie
Formă tabulară de reprezentare grafică
Diagrama de stat
Diagrama de stat a automatelor de stat finite deterministe
Din diagrama de stare
- Stările sunt reprezentate de vârfuri.
- Tranzițiile sunt reprezentate de arcul etichetat cu un alfabet de intrare.
- Arcul de intrare unic gol reprezintă starea inițială.
- Starea cu cercuri duble este starea finală.
Automate finite nedeterministe
Automatele în care starea de ieșire pentru intrarea dată nu poate fi determinată se numește Automate nedeterministe. Se mai numește și Automate Finite Nedeterministe, deoarece are un număr finit de stări. Automatele finite nedeterministe sunt reprezentate ca setul de 5 –duple unde (Q, ∑, δ, qo, F)
Q = ansamblu finit de stări.
∑ = Set de alfabet.
δ = funcția de tranziție
Unde : 
qo = Stare initiala.
Reprezentare grafică
Automatele finite nedeterministe sunt reprezentate cu ajutorul diagramei de stare. Să fie automatele finite nedeterministe
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Tranzițiile sunt
Formă tabulară de reprezentare grafică
Diagrama de stat
Diagrama de stat a automatelor finite nedeterministe
Aplicații pentru teoria automatelor
Aplicațiile de teoria automatelor include următoarele.
- Teoria automatelor este foarte utilă în domeniile teoriei calculului, producțiilor de compilatoare, AI etc.
- Pentru compilatoarele de procesare a textelor și proiectările hardware, automatele finite joacă un rol major.
- Pentru aplicații în AI și în limbaje de programare , Gramatica fără context este foarte utilă.
- În domeniul biologiei, automatele celulare sunt utile.
- În teoria câmpurilor finite, de asemenea, putem găsi aplicația Automatelor.
În acest articol, am învățat o scurtă introducere în limbajele și calculul teoriei automatelor. Automatele au existat încă din perioada preistorică. Odată cu inventarea noilor tehnologii, multe noi dezvoltări se văd în acest domeniu. Cu ce tip de automate ați întâlnit?
