Parțial automat
Un automat parțial este un automat abstract al cărui funcție de tranziție sau funcție de ieșire (normală sau deplasată) sau ambele, nu este definită pentru toate perechile de valori ale argumentelor lor și ale lor. [1]
Luând automat automat parțial. unde aceste tranziții și ieșiri nu sunt definite deloc, prin aceasta ne rezervăm dreptul de a le defini ulterior în modul care ne-ar conveni. [2]
Pentru automatele parțiale, aceleași metode de atribuire sunt utilizate ca și pentru automatele complet definite. În acele locuri din tabela de tranziție sau din tabela de ieșire (normală sau deplasată), în care funcțiile pe care le reprezintă nu sunt definite, vom desena linii. Graficul grafic al unui automat parțial poate avea noduri, din care săgețile indicate de aceste sau de alte semnale de intrare nu ies la ieșire. [3]
Pentru automatele Moore parțiale, este normal să se considere interzise toate stările pentru care funcția de ieșire mutată nu este definită. Este ușor de înțeles că tranziția de la starea inițială la interzisă sub influența unui cuvânt automat Moore nu poate fi făcută decât în cazul în care acest cuvânt este interzis. [4]
Pentru automatele Miley și Moore parțiale, o placă este plasată în tabelele respective în locul stărilor nedeterminate și a semnalelor de ieșire. [5]
În cazul automatelor parțiale, pe lângă echivalența și izomorfismul automatelor, se folosesc adesea conceptele de extindere echivalentă și izomorfă a automatelor. [6]
Esența problemei minimizării mașinilor parțiale este următoarea: având în vedere parțială automată (Moore sau Mealy) A, inducerea de cartografiere automaton parțială f definită pe un set de cuvinte alfabet de intrare M. Necesar pentru a construi un automat parțială (Moore sau Mealy, respectiv), în care induce cartografiere parțială automat pentru a se potrivi setul de M cu cartografiere f, și are cel mai mic număr de stări interne ale tuturor automatelor (Moore sau Mealy) îndeplinesc această condiție. [7]
Spre deosebire de automatele parțiale. Automatele considerate mai sus se numesc complet definite. [8]
În cazul automatelor parțiale, proprietatea de tranziție pentru relația / compatibilitate, în general, nu este deținută. [9]
În cazul automatelor parțiale, situația este mult mai complicată: prin construirea clasei os și a formei normale, procesul de minimizare nu se termină, în general. [10]
În cazul în care o funcție arbitrară de tranziție parțială a automatului Mealy A nu luată în considerare, în toate punctele în care este specificat că funcția de ieșire a apărut astfel noi parțială Mealy B va induce aceeași cartografiere parțială că A. automată [11]
Fără a schimba harta parțială indusă de automatul Moore parțial, putem presupune că funcția de tranziție a acestui automat este nedefinită ori de câte ori își asumă o valoare interzisă. [12]
La fel ca mașinile automate parțiale bine definite sunt împărțite în mașini de la primul si al doilea fel, a automatelor Mealy și Moore. Izomorfism automatelor parțială oferă o mapare izomorfă corespunzătoare hartă setul de valori în care funcția de tranziție nu este definită sau ieșiri (normale sau decalate) o mașină la o multitudine de valori, care nu sunt definite funcțiile corespunzătoare ale unei alte mașini. [13]
Menționăm că sinteza automatelor parțiale nu diferă de cea descrisă mai sus. Cu acele combinații de semnale de intrare și stări interne ale automatului parțial care nu sunt incluse în tabelele de tranziție și de ieșire codificate, valorile funcțiilor de excitație pot fi alese arbitrar. [15]
Pagini: 1 2 3 4