Таблица прелаза стања
Табела прелаза стања
[уреди | уреди извор]У теорији аутомата и секвенцијалној логици, табела (таблица) прелаза стања представља табуларни приказ промене стања коначних аутомата у зависности од улаза. Она показује у које ће се стање (односно стања у случају недетерминистичких коначних аутомата) померити коначни аутомат у зависности од тренутног стања и улазних података. Табела стања је заправо табела истинитости у којој су неки улази тренутно стање, а излази укључују следеће стање, заједно с осталим излазима. У овој табели улази се дефинишу колонама а стања врстама.
Табела стања је један од много начина описивања коначног аутомата, поред дијаграма стања и карактеристичне једначине. Ове таблице су корисне када се скуп свих улаза може поделити у релативно мали број група и када се скуп свих могућих понашања може поделити у релативно мали број стања. У другим случајевима табела може бити превелика за рад.
Уобичајени облици
[уреди | уреди извор]Једнодимензионалне таблице стања
[уреди | уреди извор]Једнодимензионалне таблице стања се такође зову карактеристичне таблице и оне су сличније табелама истинитости од дводимензионалних. Улази се најчешће стављају са леве стране и физички се одвајају од излаза који су на десној страни. Излази заправо представљају следеће стање у којем ће се машина наћи након читања улаза. Следи једноставан пример коначног аутомата са два стања (С1 и С2 који највероватније представљају 0 или 1 како један бит може имати само једну од те две вредности) и комбинаторним улазима.
| A | Б | Тренутно стање | Следеће стање | Излаз |
|---|---|---|---|---|
| 0 | 0 | С1 | С2 | 1 |
| 0 | 0 | С2 | С1 | 0 |
| 0 | 1 | С1 | С2 | 0 |
| 0 | 1 | С2 | С2 | 1 |
| 1 | 0 | С1 | С1 | 1 |
| 1 | 0 | С2 | С1 | 1 |
| 1 | 1 | С1 | С1 | 1 |
| 1 | 1 | С2 | С2 | 0 |
Дводимензионалне таблице
[уреди | уреди извор]Табеле стање су, међутим, чешће мало компликованије, и представљају се дводимензионално уз два различита начина за њихово уређивање.
- У колонама (односно врстама) се налазе тренутна стања, у врстама (односно колонама) догађаји, док се у ћелијама табеле (у пресеку врста и колона) налазе следећа стање у које ће аутомат прећи уколико се оствари догађај. (по могућству може садржати и акцију повезану са овим прелазом)
| Догађаји Стање |
E1 | E2 | ... | En |
| С1 | - | Ay/Сj | ... | - |
| С2 | - | - | ... | Ax/Сi |
| ... | ... | ... | ... | ... |
| См | Az/Сk | - | ... | - |
(С: стање, E: догађај, A: акција, -: недозвољени прелаз)
- У колонама (односно врстама) се налазе тренутна стања, у врстама (односно колонама) следећа стања, док се у ћелијама табеле налазе догађаји који узрокују прелаз у наредно стање (поново одређено пресеком врста и колона).
| следеће тренутно |
С1 | С2 | ... | См |
| С1 | Ay/Ej | - | ... | - |
| С2 | - | - | ... | Ax/Ei |
| ... | ... | ... | ... | ... |
| Sm | - | Az/Ek | ... | - |
(С: стање, E: догађај, A: акција, -: недозвољени прелаз)
Пример
[уреди | уреди извор]У примеру који следи дата је табела прелаза стања за аутомат М заједно са дијаграмом стања за исти аутомат.
|
Дијаграм Стања |
У колонама ове табеле се налазе сви могући улази док се могућа стања у којима се аутомат може наћи налазе у врстама. Комбинујући стање и улаз, лако се види да ће аутомат, уколико се налази у стању С1 (прва врста) а на улазу се налази 1 остати у истом стању С1. Уколико се на улазу појави 0 аутомат прелази у стање С2 што се види у пресеку прве врсте и друге колоне. На дијаграму то се представља стрелицом која спаја С1 и С2 означеном са 0. Код недетерминистичких коначних аутомата (НКА), аутомат из једног стања читањем улаза може да пређе у више различизих стања (одатле и потиче назив недетерминистички). Ово се у табелама стања представља витичастим заградама унутар којих се налазе сва стања у које се прелази. Следи пример.
| Улаз Стање |
1 | 0 | ε |
| С1 | С1 | { С2, С3 } | Φ |
| С2 | С2 | С1 | Φ |
| С3 | С2 | С1 | С1 |
Сада недетерминистички аутомат у стању С1 читајући улаз 0 може да пређе у два стања С2 или С3. Последња колона дефинише дозвољене прелазе стања читањем специјалног знака ε (празне речи). Овај специјални карактер дозвољава НКА да пређе у друго стање без читања улаза. Као што се види у трећој врсти, НКА се из стања С3 без читања улаза може пребацити у стање С1. Ова два примера чине коначни аутомат недетерминистичким.
Трансформације из и у дијаграм стања
[уреди | уреди извор]Лако је из табеле стања нацртати дијаграм стања у само неколико корака.
- Нацртати кругове који представљају задана стања
- Пролазећи кроз таблицу, за свако стање нацртати могући прелаз, цртајући стрелицу у могућа стања и обечежавајући их улазом. Код НКА из једног стања може постојати више стрелица
- Обележити почетно сатње стрелицом која не води ни из једног стања.
- Обележити заврсна стања дуплим кругом
Почетна и завршна стања су задана у формалној дефиницији аутомата
Референце
[уреди | уреди извор]- Michael Sipser: Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X
- https://web.archive.org/web/20100331170515/http://sunset.usc.edu/classes/cs665_99/readings/week10/statetables.pdf