Mașina de stat

O mașină de stat finită este un automat abstract. numărul de stări interne posibile este finit.

Există mai multe moduri de a specifica un algoritm pentru operarea unei mașini de stare finită. De exemplu, un automat finit poate fi specificat sub forma unui element comandat de câteva seturi:

• V - alfabet de intrare (un set finit de simboluri de intrare), din care se formează cuvintele de intrare. percepută de mașina finită de stat;
• Q este setul de stări interne;
• q 0> este starea inițială (q 0 ∈ Q) \ în Q)>;
• F este setul de stări finale sau finale (F ⊂ Q);
• δ este funcția de tranziție. definită ca o mapare a lui δ. Q × (V ∪ <ε> ) → Q) \ rightarrow Q>. astfel încât δ (q.a) = > \, \, r \ >>. adică, valoarea funcției de tranziție pe perechea ordonată (stare, simbolul de intrare sau un șir gol) este mulțimea tuturor statelor în care o anumită stare de tranziție pe caracterul de intrare sau șirul gol (ε).

Se presupune că automatul finit începe să funcționeze în stare q 0>. citirea secvențială a unui caracter al cuvântului de intrare (un lanț de simboluri de intrare). Un simbol citit duce automat la o stare nouă, în conformitate cu funcția de tranziție.

Citirea lanțului de intrări a simbolurilor x și efectuarea tranzițiilor de la starea la stare, automatul după citirea ultimului caracter al cuvântului de intrare va fi într-o anumită stare q '.

Dacă această stare este finală, atunci spuneți că automatul a permis cuvântul x.

Alte moduri de a descrie editarea

1. O diagramă de stare (sau uneori un grafic de tranziție) este o reprezentare grafică a setului de stări și a funcțiilor de tranziție. Este un grafic orientat marcat. ale căror vârfuri sunt state SC, arce sunt tranziții de la o stare la alta, iar semnele arcuțelor sunt simbolurile prin care are loc trecerea de la o stare la alta. Dacă tranziția de la starea q1 la q2 poate fi efectuată cu unul sau mai multe simboluri, atunci toate trebuie să fie înscrise deasupra arcului diagramei.
2. Tabelul de tranziție este o reprezentare de tabelă a funcției δ. În mod obișnuit, într-o astfel de tabelă, fiecare rând are o stare și o coloană are un simbol de intrare valabil. Într-o celulă de la intersecția unui rând și a unei coloane se introduce starea în care mașina ar trebui să meargă dacă în această stare a considerat acest simbol de intrare.

Automatele finite sunt subdivizate în deterministe și nedeterministe.

• automat finit determinist (DFA) este o mașină în care nu există nici un arc de cerc cu eticheta ε (licitată, care nu conține caractere), și de la orice stare de orice simbol nu poate schimba mai mult de un stat.
• Masina de stat finit nedeterministă (NCA) este o generalizare a automatului determinat. Nedeterminarea automatelor poate fi realizată în două moduri: fie pot exista tranziții marcate cu un lanț gol ε, fie mai multe tranziții marcate cu același simbol pot ieși dintr-o stare.

• 

  Masina deterministă de stat

  

  Automat nedeterminist cu tranziții goale

  

  Un automat nedeterminist cu tranziții de la o stare marcată cu același simbol

  Dacă luăm în considerare cazul când automatul este dat după cum urmează: M = (V. Q. S. F. δ). unde S este setul de stări inițiale ale automatului, astfel încât S ⊆ V. atunci există un al treilea semn de indeterminare - prezența mai multor stări inițiale (de pornire) pentru automatul M.

  Teorema pe determinism susține că un automat finit determinist echivalent (două automate finite sunt echivalente în cazul în care limba lor este același lucru) poate fi construit pentru orice automat finit. 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, mașinile de stare finită cu ieșire în cazul general nu se supun determinismului.

  Având în vedere ultimele două observații, în pofida marei complexități a mașinilor de stat finite nedeterministe, este în principal NFA, care este utilizat în principal pentru sarcini legate de prelucrarea textului.

  Automatele și limbile obișnuite Edit href = Edit

  Pentru un automat finit, se poate defini o limbă (un set de cuvinte) în alfabetul V. pe care îl admite - așa-numitele cuvinte, citirea cărora duce automatul de la starea inițială la una din stările finale.

  
  
  
  
  
  
  

  Teorema lui Kleene afirmă că o limbă este regulată dacă și numai dacă este permisă de un automat finit utilizat în această limbă.

  Limbi de programare specializate

  • Schema de funcții secvențiale (SFC) este un limbaj de programare grafic. Este utilizat pe scară largă pentru programarea controlerelor logice industriale (PLC-uri).

  În SFC, programul este descris sub forma unei secvențe schematice de pași combinată de tranziții.

  Dezvoltarea de modele folosind mașini de stat finite Edit

  Automatele finite permit modele de construcție ale sistemelor de procesare paralelă, cu toate acestea, pentru a schimba numărul de procese paralele într-un astfel de model, este necesar să se efectueze modificări semnificative ale modelului în sine. În plus, încercarea de a dezvolta un model complex pe un automat finit va duce la o creștere rapidă a numărului de stări ale mașinii, ceea ce va face în final dezvoltarea unui astfel de model o sarcină extrem de plictisitoare. După cum sa menționat mai sus, ultima problemă poate fi rezolvată prin utilizarea unui automat nedeterminist.

  Ce poate face o mașină finită și o mașină secvențială? regulă

  Răspunsul este dat în mai mulți termeni, în funcție de caracterul autonom al mașinii (sau al mașinii P) [1]. O mașină autonomă de stat finită, pornind de la o anumită măsură, poate genera doar o secvență periodică de stări x (respectiv, mașina P este o secvență de simboluri de ieșire y). Dacă această secvență constă dintr-un singur simbol, atunci aceasta înseamnă că într-un număr finit de cicluri automatul atinge o stare de echilibru. Dacă această secvență conține mai multe simboluri, înseamnă că mașina trece succesiv stările corespunzătoare acestor simboluri, iar apoi funcționarea mașinii pe o perioadă nedefinită de timp se repetă. Mai mult decât atât, pentru orice secvență periodică de stări de lungime finită, poate fi întotdeauna construit un automat finit autonom, care, începând cu a doua etapă, generează această secvență. Orice altceva decât repetarea periodică a aceleiași stări sau a unei secvențe finite de stări, automatul autonom "nu poate face". Cu toate acestea, având în vedere faptul că executarea succesivă a unui ciclu de operațiuni dat este tipică pentru multe domenii ale tehnologiei moderne, sistemele dinamice care pot fi considerate automate autonome în idealizări acceptabile au o aplicare largă.

  Un exemplu clasic îl reprezintă automatele de păpuși care efectuează secvențe complexe de acțiuni, de exemplu: scrierea unui anumit text pe hârtie, redarea pieselor prestabilite pe pian etc.

  Un exemplu modern sunt multe mașini automate, linii automate și sisteme automate de control pentru producția ciclică. În cazul în care aparatul nu este autonom, adică, modificările de stat de intrare de la bataie la bataie, răspunsul la întrebarea ce se poate „face“ și nu se poate „face“ aparatul de stat, pot fi date în termeni diferiți. De exemplu, răspunsul poate fi formulat în limba reprezentării evenimentului. Într-adevăr, mașinile de mașini de stat non-autonome sau secvențiale converti numai secvența de intrare de simboluri în secvența de stări sau simboluri de ieșire, și să spun ceea ce poate și nu se poate „face“ mașina de stat, apoi afla ce sunt posibile secvențele de transformare în mașina de stat, și ceea ce este posibil. Dar, pe măsură ce numărul de state (respectiv simboluri de ieșire) Desigur, această întrebare este echivalentă cu o astfel de întrebare: în ce secvențe de intrare are loc în fiecare stat posibile (sau fiecare dintre simbolurile de ieșire). Această ultimă întrebare în termenii adoptate în teoria automatelor finite este formulat după cum urmează: ce evenimente și ceea ce nu poate fi reprezentat în mașina de stat fiecare dintre stările posibile (sau fiecare dintre simbolurile de ieșire).

  Răspunsul este dat de teoremele lui Kleene. Acest răspuns este exact, deoarece teoremele Kleene stabilesc condițiile necesare și suficiente pentru reprezentabilitatea unei secvențe de evenimente într-un automat, și anume: se disting seturi speciale de secvențe de simboluri de intrare - seturi regulate. Apariția unei secvențe de intrare dintr-un astfel de set este denumită evenimentul regulat corespunzător. Teoremele lui Kleene stabilesc că evenimentele regulate pot fi reprezentate într-un automat finit și numai ele. Astfel, în limba reprezentării evenimentelor, răspunsul la întrebarea ce poate face un automat finit este dat fără echivoc: un automat finit poate reprezenta doar evenimente regulate. O serie de seturi importante de secvențe de intrare, care trebuie adesea tratate în practică, sunt cu siguranță regulate. De exemplu, este cunoscut faptul că un set format din orice număr finit de secvențe de intrare cu lungime finită există în mod regulat; setul de secvențe de intrare periodice; un set de secvențe infinite care conține secvențele finite dat peste ultimele măsuri și așa mai departe.

  În cazul general, dacă un set infinit de secvențe de intrare este dat de orice metodă arbitrară, se pune întrebarea dacă acest set este regulat. Ideea este că conceptul unui set regulat este introdus inductiv, adică este stabilit un algoritm pentru construirea oricăror seturi regulate. Cu toate acestea, nu există o modalitate suficient de eficientă de a rezolva problema inversă, adică de a determina dacă fiecare set dat este regulat.

  Deși teoremele lui Kleene răspund, de asemenea, la întrebarea ce poate face un automat finit, dar răspund ineficient la această întrebare. Au fost făcute primele încercări de a construi alte limbi, pe care răspunsul poate fi dat eficient. Problema limbii, care joacă un rol crucial în obținerea unui răspuns eficient la problema a ceea ce se poate și nu se poate „face“ aparatul de stat este critică pentru sinteza primelor etape ale mașinii, adică, să răspundă la a doua dintre întrebările de mai sus. Dacă vă extindeți clasa sistemelor dinamice, pe care le definesc „mașină de stat“ și „mașină secvențială“ termenul, includerea unei memorii infinite (modelul de memorie infinit poate fi, de exemplu, cureaua fără sfârșit pentru a stoca caractere sau un număr infinit de state), pentru sisteme dinamice ale acestui larg clasă (clasa abstractă a acestui sistem se numește mașini Turing) răspuns la întrebarea este mult mai ușor „Ce pot face ei?“ - ei pot pune în aplicare orice algoritm preasigurată. Astfel, conceptul de algoritm în sine este tratată în matematică modernă ca o realizare de calcul a valorilor unei funcții recursive. „Ce poate face o mașină Turing“ Un astfel de răspuns lipsit de ambiguitate și clar la întrebarea oferă o oportunitate de a pune conceptul de masina Turing ca bază definiția algoritmului: algoritmul este orice proces care poate fi efectuat pe mașina țintă, completată de memorie infinită, care este algoritmic mașini complet , prin mașină Turing, prin mașină Post, etc.

  1. ↑ Aizerman MA Gusev LA Rosonor LI Smirnova IM Tal O logică AA. Mașini automate. Algoritmi. Gos. ed. Sci. Literatură 1963, 556 p.
  
  
  
  
  
  
  

  Articole similare

  • Slot machines pe tema curse - 50 de nuante de galben - stiri, glume, hrean

  • Un automat autonom este

  • Variante de scheme pentru conectarea unui automat diferențial în scut

  Pagina anterioară

  Pagina următoare

  Trimiteți-le prietenilor: