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

Из Википедије, слободне енциклопедије
Info non-talk.svg Овом чланку или једном његовом делу је потребно прерађивање.

видети како се референце могу стварно уклопити у текст. можда као литература

Чланак је означен овим шаблоном 21.01.2012. и налази се у категорији Рачунарство и информатика.
Погледајте како се мења страница или страницу за разговор за помоћ. Уклоните ову поруку када завршите.

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

Finite state machine example with comments.svg

Преглед[уреди]

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

Дијаграм стања се може употребити да графички представи аутомате коначних стања. Ово је представљено од стране Тејлора Бута(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“ где је ј улаз а к излаз

Mealymachine jaredwf.png

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

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

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

UML дијаграм стања[уреди]

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

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

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

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

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

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

Видети такође[уреди]

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

1. ^ State Diagrams., Приступљено 11. 8. 2008.

2. ^ a b Taylor Booth (1967) Sequential Machines and Automata Theory, John Wiley and Sons, New York.

  1. ^ a b John Hopcroft and Jeffrey Ullman (1979) Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing Company, Reading Mass, ISBN 0-201-02988-X
  2. ^ Edward J. McClusky, Introduction to the Theory of Switching Circuits, McGraw-Hill, 1965
  3. ^ David Harel, Statecharts: A visual formalism for complex systems. Science of Computer Programming, 8(3):231–274, June 1987.
  4. ^ D. Drusinsky, Modelling and verification using UML statecharts, Elsevier, 2006
  5. ^ Dan Pilone, UML 2.0 Pocket Reference, O'Reilly, 2006

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