Таблица прелаза стањаТабела прелаза стањаУ теорији аутомата и секвенцијалној логици, табела (таблица) прелаза стања представља табуларни приказ промене стања коначних аутомата у зависности од улаза. Она показује у које ће се стање (односно стања у случају недетерминистичких коначних аутомата) померити коначни аутомат у зависности од тренутног стања и улазних података. Табела стања је заправо табела истинитости у којој су неки улази тренутно стање, а излази укључују следеће стање, заједно с осталим излазима. У овој табели улази се дефинишу колонама а стања врстама. Табела стања је један од много начина описивања коначног аутомата, поред дијаграма стања и карактеристичне једначине. Ове таблице су корисне када се скуп свих улаза може поделити у релативно мали број група и када се скуп свих могућих понашања може поделити у релативно мали број стања. У другим случајевима табела може бити превелика за рад. Уобичајени облициЈеднодимензионалне таблице стањаЈеднодимензионалне таблице стања се такође зову карактеристичне таблице и оне су сличније табелама истинитости од дводимензионалних. Улази се најчешће стављају са леве стране и физички се одвајају од излаза који су на десној страни. Излази заправо представљају следеће стање у којем ће се машина наћи након читања улаза. Следи једноставан пример коначног аутомата са два стања (С1 и С2 који највероватније представљају 0 или 1 како један бит може имати само једну од те две вредности) и комбинаторним улазима.
Дводимензионалне таблицеТабеле стање су, међутим, чешће мало компликованије, и представљају се дводимензионално уз два различита начина за њихово уређивање.
(С: стање, E: догађај, A: акција, -: недозвољени прелаз)
(С: стање, E: догађај, A: акција, -: недозвољени прелаз) ПримерУ примеру који следи дата је табела прелаза стања за аутомат М заједно са дијаграмом стања за исти аутомат.
У колонама ове табеле се налазе сви могући улази док се могућа стања у којима се аутомат може наћи налазе у врстама. Комбинујући стање и улаз, лако се види да ће аутомат, уколико се налази у стању С1 (прва врста) а на улазу се налази 1 остати у истом стању С1. Уколико се на улазу појави 0 аутомат прелази у стање С2 што се види у пресеку прве врсте и друге колоне. На дијаграму то се представља стрелицом која спаја С1 и С2 означеном са 0. Код недетерминистичких коначних аутомата (НКА), аутомат из једног стања читањем улаза може да пређе у више различизих стања (одатле и потиче назив недетерминистички). Ово се у табелама стања представља витичастим заградама унутар којих се налазе сва стања у које се прелази. Следи пример.
Сада недетерминистички аутомат у стању С1 читајући улаз 0 може да пређе у два стања С2 или С3. Последња колона дефинише дозвољене прелазе стања читањем специјалног знака ε (празне речи). Овај специјални карактер дозвољава НКА да пређе у друго стање без читања улаза. Као што се види у трећој врсти, НКА се из стања С3 без читања улаза може пребацити у стање С1. Ова два примера чине коначни аутомат недетерминистичким. Трансформације из и у дијаграм стањаЛако је из табеле стања нацртати дијаграм стања у само неколико корака.
Почетна и завршна стања су задана у формалној дефиницији аутомата Референце
|
Portal di Ensiklopedia Dunia
