Дијаграм стања

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

Дијаграм стања је дијаграм који се користи на пољу компјутерских наука, који представља понашање система који је састављен од коначног броја стања. Постоје многи облици дијаграма стања, који се незнатно разликују и имају различиту семантику.

Преглед[уреди | уреди извор]

Дијаграми стања се користе за описивање понашања система. Они могу да опишу могућа стања објекта како се догађаји појављују. Сваки дијаграм обично представља објекте једне класе и прати различита стања тих објеката кроз систем.

Дијаграм стања се може употребити да графички представи аутомате коначних стања. Ово је представљено од стране Тејлора Бута(Taylor Booth) у његовој књизи из 1967. године “ Sequential Machines and Automata Theory”. Други могући начин представљања је преко табеле промене стања.

Усмерени граф[уреди | уреди извор]

Усмерени граф

Класична форма дијаграма стања за представљање коначних аутомата је усмерени граф са следећим елементима:

  • Стања Q: коначан скуп vertices нормално представљених круговима и означених симболима или речима написаним унутар њих;
  • Улазни симболи S: коначна колекција улазних симбола или designators;
  • Излазни симболи Z: коначна колекција излазних симбола или designators;

Излазна функција ω представља мапирање улазних симбола у излазне, представљену математички као ω : Σ × Q → Z.

  • Ивице δ: представља прелазе између два стања настале уносом (идентификоване преко својих симбола нацртаних на ивицама). Ивица се обично црта као стрелица усмерена од садашњег стања према наредном стању. Ово мапирање описује промене стања које би требало да настану при уносу одређеног симбола. Ово се математички записује као δ : Σ × Q → Z
  • Почетно стање q0: (није приказано у примерима који следе). Почетно стање q0 ∈ Q је обично приказано као стрелица којој не претходи стање усмерена на неко стање. У старијим текстовима, почетно стање није приказано и мора се закључити из текста.
  • Завршно стање(стања) F: ако се користи нпр. за завршавање аутомата, F ∈ Q је завршно стање. Обично се црта као два круга. Понекад завршно стање(стања) функционишу као коначна стања.

За детерминистичке коначне аутомате (ДКА), недетерминистичке аутомате(НКА), генерализоване недетерминистичке коначне аутомате (ГНКА) или Мурове аутомате, улаз је обележен на свакој ивици. За Милијев аутомат, улаз и излаз су означени на свакој ивици, раздвојени косом цртицом “/” : ”1/0”. За Муров аутомат излаз из стања је обично написан унутар круга којим је стање представљено и такође је одвојено од designator стања косом цртом. Постоје такође и варијанте које комбинују ове две нотације.


На пример, ако стање има одређен број излаза(e.g. a = motor counter-clockwise = 1, b = caution light inactive = 0) дијаграм би трбао да прикаже следеће: e.g. „q5 / 1,0“ стање q5 са излазима а=1, b=0. Овај designator ће бити написан унутар круга стања.

Пример: ДКА, НКА, ГДКА, или Муров аутомат[уреди | уреди извор]

S1 и S2 су стања и S1 је завршно стање. Свака ивица је означена уносом. Овај пример показује затворење за стринг преко {0, 1} која садржи чак и одређен број нула.

Дијаграм стања
Дијаграм стања

Пример Милијев аутомат[уреди | уреди извор]

S0, S1, S2 су стања. Свака ивица је означен са „j / k“ где је ј улаз а к излаз

Харелов дијаграм стања[уреди | уреди извор]

Харелови дијаграми су ушли у широку употребу откад је ова варијанта постала део Unified modeling Langauge. Овај тип дијаграма омогућава моделовање суперстања, конкурентних стања, и активности као дела стања.

Класични дијаграми стања су „or“ (дисјункција) дијаграми, зато што аутомат може бити само у једном од свих могућих стања. Са Хареловим дијаграмима је могуће моделовати „and“ аутомате, где аутомат може бити у два или више стања конкурентно. Ово је могуће захваљујући делом моделовања суперстања и делом моделовању конкурентних аутомата.

UML дијаграм стања[уреди | уреди извор]

Примар UML дијаграм стања

The Unifide Modeling Language(UML) дијаграм стања је у основи Харелов дијаграм са стандардизованоим нотацијама, који може описати многе системе, од компјутерских програма до бизнис процеса. Оно што следи су основни нотациони елементи који се могу користити да се направи дијаграм:

  • Испуњен круг који показује иницијално стање
  • Празан круг који садржи мањи испуњен круг, показујући завршно стање(ако га има)
  • Заобљени правоугаоник означава стање. Врх правоугаоника садржи име стања. Може садржати хоризонталну линију у средини, испод које су приказане активности које су урађени у том стању.
  • Стрелица која означава прелаз. Име догађаја(ако постоји) који узрокује ову промену написан је дуж стрелице. Гард изрази могу да се додају испред “/” (eventName[guardExpression]) означавајући да ова израз мора бити истинит да би се прелаз одиграо. Ако се током овог прелаза дешава нека радња, то се додаје ознаци иза косе црте (eventName[guardExpression]/action).
  • Танка хоризонтална линија са или x>1 улазних линија и 1 излазна, или 1 улазна и више излазних линија.

Према Пилону (Pilone) једино предефинисан гард услов је ELSE. Ни један други пример није приказан у тој публикацији.

Остале екстензије[уреди | уреди извор]

Интересантна екстензија је дозволити луковима да крену из било ког броја стања до било ког броја стања. Ово има смисла само ако је систему дозвољено да одједном буде у више стања што наговештава да индивидуално стање описује услов или други делимични аспект целокупног стања. Резултујући формализам је познат као Петријева мрежа (Petri net).

Друга екстензија дозвољава интеграцију дијаграма унутар Хареловог дијаграма стања.

Види још[уреди | уреди извор]

Литература[уреди | уреди извор]

Спољашње везе[уреди | уреди извор]

Дијаграм стања на Викимедијиној остави.
Преузето из „https://sr.wikipedia.org/w/index.php?title=Дијаграм_стања&oldid=26868331”