Таблица прелаза стања

Из Википедије, слободне енциклопедије

Табела прелаза стања[уреди]

У теорији аутомата и секвенцијалној логици, табела (таблица) прелаза стања представља табуларни приказ промене стања коначних аутомата у зависности од улаза. Она показује у које ће се стање (односно стања у случају недетерминистичких коначних аутомата) померити коначни аутомат у зависности од тренутног стања и улазних података. Табела стања је заправо табела истинитости у којој су неки улази тренутно стање, а излази укључују следеће стање, заједно с осталим излазима. У овој табели улази се дефинишу колонама а стања врстама.

Табела стања је један од много начина описивања коначног аутомата, поред дијаграма стања и карактеристичне једначине. Ове таблице су корисне када се скуп свих улаза може поделити у релативно мали број група и када се скуп свих могућих понашања може поделити у релативно мали број стања. У другим случајевима табела може бити превелика за рад.

Уобичајени облици[уреди]

Једнодимензионалне таблице стања[уреди]

Једнодимензионалне таблице стања се такође зову карактеристичне таблице и оне су сличније табелама истинитости од дводимензионалних. Улази се најчешће стављају са леве стране и физички се одвајају од излаза који су на десној страни. Излази заправо представљају следеће стање у којем ће се машина наћи након читања улаза. Следи једноставан пример коначног аутомата са два стања (С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 - Ayj ... -
С2 - - ... Axi
... ... ... ... ...
См Azk - ... -

(С: стање, E: догађај, A: акција, -: недозвољени прелаз)

    • У колонама (односно врстама) се налазе тренутна стања, у врстама (односно колонама) следећа стања, док се у ћелијама табеле налазе догађаји који узрокују прелаз у наредно стање (поново одређено пресеком врста и колона).
Табела прелаза стања
      следеће
тренутно
С1 С2   ...   См
С1 Ay/Ej - ... -
С2 - - ... Ax/Ei
... ... ... ... ...
Sm - Az/Ek ... -

(С: стање, E: догађај, A: акција, -: недозвољени прелаз)

Пример[уреди]

У примеру који следи дата је табела прелаза стања за аутомат М заједно са дијаграмом стања за исти аутомат.

Табела прелаза стања
  Улаз
Стање
1 0
С1 С1 С2
С2 С2 С1
  Дијаграм Стања
DFAexample.svg

У колонама ове табеле се налазе сви могући улази док се могућа стања у којима се аутомат може наћи налазе у врстама. Комбинујући стање и улаз, лако се види да ће аутомат, уколико се налази у стању С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. Ова два примера чине коначни аутомат недетерминистичким.

Трансформације из и у дијаграм стања[уреди]

Лако је из табеле стања нацртати дијаграм стања у само неколико корака.

  1. Нацртати кругове који представљају задана стања
  2. Пролазећи кроз таблицу, за свако стање нацртати могући прелаз, цртајући стрелицу у могућа стања и обечежавајући их улазом. Код НКА из једног стања може постојати више стрелица
  3. Обележити почетно сатње стрелицом која не води ни из једног стања.
  4. Обележити заврсна стања дуплим кругом

Почетна и завршна стања су задана у формалној дефиницији аутомата

Референце[уреди]