상태도

상태 다이어그램은 시스템 동작을 설명하기 위해 컴퓨터 과학 및 관련 분야에서 사용되는 다이어그램의 한 종류입니다.상태 다이어그램은 설명된 시스템이 유한한 수의 상태로 구성되어야 한다고 요구합니다. 때로는 이것이 사실인 반면, 다른 때에는 합리적인 추상화입니다.상태 다이어그램에는 여러 가지 형태가 있으며, 이 다이어그램은 약간씩 다르며 의미론도 다릅니다.

개요

상태 다이어그램은 시스템의 동작을 추상적으로 설명하는 데 사용됩니다.이 동작은 하나 이상의 가능한 상태에서 발생할 수 있는 일련의 이벤트로 분석 및 나타납니다.이에 따라 "각 다이어그램은 일반적으로 단일 클래스의 객체를 나타내며 시스템을 통해 객체의 다양한 상태를 추적합니다."^[1]

상태 다이어그램을 사용하여 유한 상태 머신(유한 오토마타라고도 함)을 그래픽으로 나타낼 수 있습니다.이것은 Claude Shannon과 Warren Weaver에 의해 1949년 책 The Mathemical Theory of Communication에서 소개되었다.또 다른 출처는 테일러 부스입니다. 1967년 그의 책 "시퀀셜 머신과 오토마타 이론"에서요.또 다른 가능한 표현은 상태 전이 테이블입니다.

유향 그래프

유한 오토마톤(FA)에 대한 상태 다이어그램의 고전적인 형식은 다음 요소(Q, δ, Z, δ₀, q,^[2][3] F)를 가진 유향 그래프입니다.

• 꼭지점 Q: 보통 원으로 표현되고 고유한 지시자 기호 또는 그 안에 쓰여진 단어로 라벨이 지정된 유한한 상태 집합
• 입력 기호 σ : 입력 기호 또는 지정자의 유한 집합
• 출력 기호 Z: 출력 기호 또는 지정자의 유한 집합

출력 함수 repres는 순서 있는 입력 기호 및 상태 쌍을 출력 기호로 매핑하는 것을 나타내며, 수학적으로 σ : q × Q → Z로 표시됩니다.

• 에지 :: 입력에 의해 발생한 한 상태에서 다른 상태로의 전환을 나타냅니다(에지에 그려진 기호로 식별됨).엣지는 보통 현재 상태에서 다음 상태로 향하는 화살표로 그려집니다.이 매핑은 특정 기호 입력 시 발생하는 상태 천이를 설명합니다.이는 수학적으로 θ : Q × δ → Q로 표기되므로 FA 정의에서의 θ(전이함수)는 엣지로 연결된 정점 쌍과 이 FA를 나타내는 다이어그램의 엣지 상에 있는 심볼로 주어진다.FA의 정의에서 항목 δ(q, a) = p는 입력 기호 a 아래의 q라는 이름의 상태에서 이 기계에서 상태 p로의 전환이 발생함을 의미한다.이 FA를 나타내는 그림에서 이것은 q로 라벨이 붙은 정점에서 p로 라벨이 붙은 정점으로 라벨이 붙은 에지로 나타난다.
• 시작 상태₀ q:(아래 예에서는 표시되지 않습니다).시작 상태₀ q qQ는 보통 발신기지 없는 화살표로 표시됩니다.이전 ^[2][4]텍스트에서는 시작 상태가 표시되지 않으므로 텍스트에서 유추해야 합니다.
• 수용상태 F: 예를 들어 오토마타를 수용하기 위해 사용되는 경우 F q Q는 수용상태입니다.그것은 보통 이중 동그라미로 그려진다.수용 상태는 "최종"(halt, traped) ^[3]상태로 기능하는 경우가 있습니다.

결정론적 유한 오토마톤(DFA), 비결정론적 유한 오토마톤(NFA), 일반화된 비결정론적 유한 오토마톤(GNFA) 또는 무어 머신의 경우 입력은 각 에지에 표시됩니다.Maley 기계에서는 입력과 출력이 각 에지에서 슬래시 "/"로 구분되어 표시됩니다. "1/0"은 기호 "0"이 출력되는 원인이 되는 기호 "1"을 만났을 때 상태 변화를 나타냅니다.무어 머신의 경우, 주의 출력은 보통 주의 원 안에 쓰여지며, 또한 슬래시 "/"로 주의 지정자와 구분됩니다.이 두 가지 표기를 조합한 변형도 있습니다.

예를 들어, 상태에 다수의 출력이 있는 경우("a= 모터 시계 반대=1, b= 주의등 비활성=0") 다이어그램은 다음을 반영해야 합니다. 예를 들어, "q5/1,0"은 출력 a=1, b=0인 상태 q5를 나타냅니다.이 지시자는 주의 서클 안에 쓰여질 것입니다.

예: DFA, NFA, GNFA 또는 Moore 머신

S와₁₂ S는 상태이고₁ S는 수용 상태 또는 최종 상태입니다.각 모서리에는 입력으로 라벨이 지정됩니다.다음 예제에서는 짝수 0을 포함하는 이진수 수용기를 보여 줍니다.

예: Maly 머신

S₀, S₁ 및₂ S는 상태입니다.각 에지에는 "j / k"로 라벨이 지정됩니다. 여기서 j는 입력이고 k는 출력입니다.

Harel 상태 차트

컴퓨터 과학자인 David Harel에 의해 발명된 Harel 상태 ^[5]차트는 변종이 UML(Unified ^{[non-primary source needed]}Modeling Language)의 일부가 되면서 널리 사용되고 있습니다.다이어그램 유형을 사용하면 상태의 일부로 수퍼스테이트, 직교 영역 및 활동을 모델링할 수 있습니다.

기존 상태 다이어그램에서는 상태를 정의하는 모든 파라미터의 유효한 조합에 대해 개별 노드를 생성해야 합니다.이로 인해 가장 단순한 시스템을 제외한 모든 시스템에서 노드 수가 매우 많아지고 노드 간에 전환이 발생할 수 있습니다(상태 및 전환 폭발).이 복잡성으로 인해 상태 다이어그램의 가독성이 저하됩니다.Harel 상태 차트를 사용하면 상태 차트 내에서 여러 기능 간 상태 다이어그램을 모델링할 수 있습니다.이러한 교차 기능 상태의 각 머신은 상태 차트의 다른 상태 머신에 영향을 주지 않고 내부적으로 이행할 수 있습니다.상태 차트에서 각 교차 기능 상태 기계의 현재 상태가 시스템 상태를 정의합니다.Harel 상태 차트는 상태 다이어그램과 동일하지만 결과 다이어그램의 가독성을 향상시킵니다.

대체 의미론

상태 다이어그램을 나타내기 위해 사용할 수 있는 다른 일련의 의미론들이 있습니다.예를 들어 임베디드 컨트롤러의 ^[6]로직을 모델링 및 설계하기 위한 툴이 있습니다.이러한 다이어그램은 Harel의 원래 상태 ^[7]시스템과 마찬가지로 계층적으로 중첩된 상태, 직교 영역, 상태 작업 및 전환 ^[8]작업을 지원합니다.

상태 다이어그램과 흐름도

국가 기계 형식주의의 초보자들은 종종 국가 도표와 흐름도를 혼동한다.다음 그림은 상태 다이어그램과 흐름도를 비교한 것입니다.상태 기계(패널 a)는 명시적 이벤트에 응답하여 액션을 수행합니다.이와는 대조적으로 흐름도(패널 (b))는 명시적 이벤트가 필요하지 않고 활동 ^[9]완료 시 그래프에서 노드 간에 자동으로 전환됩니다.

흐름도의 노드는 상태의 유도 그래프에서 가장자리입니다.그 이유는 흐름도 내의 각 노드가 프로그램명령어를 나타내기 때문입니다.프로그램 명령은 실행되는 작업입니다.즉, 상태가 아니라 프로그램 상태에 적용하면 다른 상태로 이행합니다.

자세한 내용은 소스 코드 목록이 프로그램 그래프를 나타냅니다.프로그램 그래프(파싱 및 해석)를 실행하면 상태 그래프가 생성됩니다.따라서 각 프로그램 그래프는 상태 그래프를 유도합니다.프로그램 그래프를 관련 상태 그래프로 변환하는 것을 프로그램 그래프의 "폴딩 해제"라고 합니다.

프로그램 그래프는 일련의 명령어입니다.변수가 존재하지 않는 경우 상태는 프로그램카운터만으로 구성됩니다.이 카운터는 프로그램 실행 중 프로그램 내의 위치(다음으로 적용할 명령어)를 추적합니다.

이 경우 명령을 실행하기 전에 프로그램 카운터가 특정 위치(명령 실행 전 상태)에 있습니다.명령을 실행하면 프로그램 카운터가 다음 명령으로 이동합니다.프로그램 카운터가 전체 상태이기 때문에 명령어를 실행하면 상태가 변경됩니다.따라서 명령어 자체는 두 상태 간의 전환에 해당합니다.

이제 변수가 존재하고 실행 중인 프로그램 명령에 의해 영향을 받는 경우 전체 대소문자를 살펴보겠습니다.그러면 서로 다른 프로그램 카운터 위치 간에 프로그램 카운터가 변경될 뿐만 아니라 실행된 명령으로 인해 변수 값도 변경될 수 있습니다.따라서 (루프 등) 일부 프로그램 명령어를 다시 사용하더라도 프로그램이 동일한 상태에 있음을 의미하지는 않습니다.

앞의 경우 전체 상태가 프로그램카운터이기 때문에 프로그램이 같은 위치(다음 명령어)를 카운터로 가리키면 같은 상태임을 나타내는 것으로 충분합니다.단, 상태가 변수를 포함하면 변수 값이 변경되면 프로그램 상태 공간의 다른 상태, 즉 변수 값이 다른 동일한 프로그램 위치에 있을 수 있습니다."언폴딩"이라는 용어는 프로그램 그래프에서 상태 그래프를 생성할 때 이러한 위치의 곱셈에서 유래합니다.

자기 전이란 초기 상태와 최종 상태가 동일한 전이입니다.

대표적인 예로는 오버플로가 되어 다시0이 될 때까지 카운터를 증가시키는 do 루프가 있습니다.do loop은 동일한 증분 명령을 반복적으로 실행하므로 프로그램 그래프는 사이클을 실행합니다.그 상태 공간에서는 사이클이 아니라 라인입니다.이는 프로그램 위치(여기서는 사이클링)와 카운터 값이 완전히 증가하므로(오버플로우가 발생할 때까지) 다른 상태가 순서대로 방문됩니다.오버플로우 후 카운터가 다시0이 되므로 상태 공간에서 초기 상태가 다시 표시되며 상태 공간의 사이클이 닫힙니다(카운터가 0으로 초기화되었다고 가정).

위의 그림은 상태 다이어그램의 호를 흐름도의 처리 단계에 맞추어 역할 반전을 나타내려고 합니다.

흐름도는 일부 태스크의 진행 상황을 처음부터 끝까지 기술하기 때문에 흐름도를 제조 라인과 비교할 수 있습니다(예를 들어 컴파일러에 의한 소스 코드 입력의 객체 코드로 변환).스테이트 머신은 일반적으로 이러한 진행에 대한 개념이 없습니다.예를 들어, 이 문서의 맨 위에 표시된 도어 상태 기계는 "개방" 상태보다 "닫힘" 상태일 때 더 발전된 단계가 아닙니다. 단순히 열기/닫기 이벤트에 대해 다르게 반응할 뿐입니다.스테이트 머신의 상태는 처리 단계가 아니라 특정 동작을 지정하는 효율적인 방법입니다.

기타 내선번호

흥미로운 확장기능은 임의의 수의 스테이트에서 임의의 수의 스테이트로 아크를 흐를 수 있도록 하는 것입니다.이는 시스템이 동시에 여러 상태가 될 수 있는 경우에만 의미가 있습니다.즉, 개별 상태는 전체적인 글로벌 상태의 상태 또는 기타 부분적인 측면만을 나타냅니다.그 결과로 생긴 형식주의는 페트리 네트로 알려져 있다.

또 다른 확장을 통해 Harel 상태 차트 내에 흐름도를 통합할 수 있습니다.이 확장 기능은 이벤트 기반 및 워크플로우 기반 소프트웨어 개발을 지원합니다.

「 」를 참조해 주세요.

• 데이비드 해럴
• DRACKON
• SCXML은 Harel 상태 차트를 기반으로 일반적인 상태 머신 기반 실행 환경을 제공하는 XML 언어입니다.
• UML 상태 기계
• YAKINDU 상태 차트 도구는 상태 다이어그램(Harel 상태 차트, Miley 시스템, Moore 시스템), 시뮬레이션 및 소스 코드 생성을 모델링하기 위한 소프트웨어입니다.

레퍼런스

외부 링크

• Scott W. Ambler의 UML 2 스테이트 머신 다이어그램 소개
• Scott W. Ambler의 UML 2 스테이트 머신 다이어그램 가이드라인
• Intelli Wizard - UML StateWizard - 오픈 소스 라이센스로 널리 사용되는 IDE에서 실행되는 단종된 라운드 트립 UML 동적 모델링/개발 프레임워크 및 도구입니다.
• YAKINDU Statechart Tools - 스테이트 머신의 도움을 받아 사후 대응적인 이벤트 주도 시스템을 지정 및 개발하기 위한 오픈 소스 도구입니다.
• 스테이트 머신에 관한 MATLAB Tech Talks의 설명과 사용
• FSM: Alexander Sakharov FSM에 의한 자바에서의 오픈 소스 유한 상태 머신 생성
• scxmlcc C++ 컴파일러에 대한 효율적인 scxml 상태 머신.
• SMC: C, Python, Lua, Scala, PHP, Java, VB 등의 여러 언어에 대해 FSM을 생성하는 오픈 소스 상태 머신 컴파일러입니다.