상태도 (오토마타 이론)

3. 유향 그래프

유한 오토마타(FA)의 상태도는 유향 그래프로 표현되며, 다음과 같은 요소(Q, Σ, Z, δ, q₀, F)를 갖는다.^[2][3]

• '''정점 Q''': 유한한 상태 집합으로, 원으로 표시하고 안에는 고유한 식별 기호나 단어를 쓴다.
• '''입력 기호 Σ''': 유한한 입력 기호 또는 식별자 모음이다.
• '''출력 기호 Z''': 유한한 출력 기호 또는 식별자 모음이다.

• '''간선 δ''': 입력에 의해 한 상태에서 다른 상태로 전이되는 것을 나타낸다. 간선은 보통 현재 상태에서 다음 상태로 향하는 화살표로 그린다. 이 매핑은 입력에 의해 발생하는 상태 전이를 설명하며, '''δ''' : '''Q''' × '''Σ''' → '''Q'''로 표기한다. FA 정의에서 δ(전이 함수)는 다이어그램에서 간선으로 연결된 정점 쌍과 간선에 있는 기호로 나타낸다. δ(q, a) = p는 입력 기호 'a'에 의해 상태 'q'에서 상태 'p'로 전이됨을 의미한다.
• '''시작 상태 q₀''': 시작 상태 q₀ ∈ Q는 일반적으로 상태를 가리키는 출처가 없는 화살표로 표시된다.^[2][4]
• '''수용 상태(들) F''': 수용 오토마타에서 F ∈ Q는 수용 상태를 의미하며, 보통 이중 원으로 그린다. 때때로 수용 상태는 "'''F'''inal" (정지, 트랩) 상태로 기능한다.^[3]

3. 1. 무어 머신 (Moore Machine)

3. 2. 밀리 머신 (Mealy Machine)

• 각 변(에지)은 두 상태 사이의 전이를 나타낸다.
• 각 에지에는 입력과 출력이 함께 표시된다.
• 각 꼭짓점(노드)은 상태를 나타낸다.

4. 하렐 상태도 (Harel Statechart)

하렐 상태도(Harel statechart)는 컴퓨터 과학자 데이비드 하렐이 발명했으며, 변형된 형태가 통합 모델링 언어(UML)의 일부가 되면서 널리 사용되고 있다.^[1] 이 다이어그램 유형은 슈퍼 상태, 직교 영역, 그리고 상태의 일부로서의 활동 모델링을 허용한다.

전통적인 상태도는 상태를 정의하는 모든 유효한 파라미터 조합에 대해 별도의 노드를 생성해야 한다. 단순한 시스템을 제외하고는 이로 인해 매우 많은 수의 노드와 노드 간의 전이(상태 및 전이 폭발)가 발생하여 상태 다이어그램의 가독성을 떨어뜨릴 수 있다. 하렐 상태도를 사용하면 상태도 내에서 여러 교차 기능 상태 다이어그램을 모델링할 수 있다. 이러한 각 교차 기능 상태 머신은 다른 상태 머신에 영향을 주지 않고 내부적으로 전이할 수 있다. 각 교차 기능 상태 머신의 현재 상태는 시스템의 상태를 정의한다. 하렐 상태도는 상태 다이어그램과 동일하지만 가독성을 향상시킨다.

하렐의 상태 전이도(데이비드 하렐이 1987년에 개발)는 하렐 차트라고도 불리며 널리 사용된다. "상위 상태"를 표현하거나, 병렬 상태를 표현할 수 있으며, 상태 내부의 활동을 모델링할 수 있다.

5. UML 상태 머신 (UML State Machine)

UML 상태 머신 다이어그램은 객체 지향 모델링에서 시스템의 동적 동작을 표현하는 데 사용된다. UML 상태 머신은 데이비드 하렐이 발명한 하렐 상태도(Harel statechart)의 변형된 형태로, 슈퍼 상태, 직교 영역, 그리고 상태의 일부로서의 활동 모델링을 허용한다.^[1] 이를 통해 복잡한 시스템도 가독성 좋게 표현할 수 있다.

• 채워진 원은 시작(START)을 나타낸다. (필수적이지 않음)
• 속이 빈 원은 정지(STOP)를 나타낸다. (필수적이지 않음)
• 모서리가 둥근 사각형은 상태를 나타낸다. 사각형 상단에는 상태 이름을, 중간 수평선 아래에는 해당 상태에서 수행될 활동을 기술한다.
• 화살표는 전이를 나타내며, 괄호([ ]) 안의 식이 참일 때 전이가 발생한다.
• 굵은 수평선은 여러 개의 전이 화살표를 묶거나 나누는 join/fork를 나타내며, 병렬 상태의 시작과 종료를 의미한다.

6. 확장

흥미로운 확장으로, 여러 상태에서 여러 상태로 화살표(아크)가 흐르도록 허용하는 것이 있다. 이는 시스템이 동시에 여러 상태에 있을 수 있을 때만 의미가 있으며, 이는 개별 상태가 전체적인, 전역 상태의 조건 또는 기타 부분적인 측면만을 설명함을 의미한다. 결과적인 형식은 페트리 망으로 알려져 있다.

또 다른 확장은 하렐 상태도 내에 순서도를 통합하는 것을 허용한다. 이 확장은 이벤트 기반 및 워크플로우 기반 소프트웨어의 개발을 모두 지원한다.

7. 순서도(Flowchart)와의 비교

상태 다이어그램은 순서도와 혼동되기도 한다. 상태 기계는 명시적인 이벤트에 대한 응답으로 작업을 수행하는 반면, 순서도는 작업 완료 시 자동으로 노드에서 노드로 전환된다.^[9]

순서도의 노드는 유도된 상태 그래프의 간선에 해당한다.^[9] 각 노드가 프로그램 명령을 나타내기 때문이다. 프로그램 명령은 실행될 작업으로, 상태는 아니지만 프로그램의 상태에 적용되면 다른 상태로 전환된다.

소스 코드 목록은 프로그램 그래프를 나타내며, 프로그램 그래프를 실행(구문 분석 및 해석)하면 상태 그래프가 생성된다. 각 프로그램 그래프는 상태 그래프를 유도하며, 프로그램 그래프를 관련 상태 그래프로 변환하는 것을 "펼침"이라고 한다.

프로그램 그래프는 일련의 명령이다. 변수가 없으면 상태는 프로그램 카운터만으로 구성된다. 명령 실행 전 프로그램 카운터 위치는 명령 실행 전 상태이고, 명령 실행 후 프로그램 카운터는 다음 명령으로 이동하여 상태가 변경된다. 따라서 명령 자체는 두 상태 간의 전환이다.

변수가 존재하고 실행되는 프로그램 명령의 영향을 받는 경우, 프로그램 카운터 위치 변경뿐만 아니라 변수 값도 변경될 수 있다. 따라서 같은 프로그램 명령을 다시 방문해도(예: 루프) 프로그램이 동일한 상태에 있다는 의미는 아니다.

전체 상태가 프로그램 카운터인 경우, 프로그램 카운터가 동일한 위치를 가리키면 동일한 상태에 있다. 그러나 상태에 값 변경되는 변수가 포함된 경우, 다른 변수 값으로 동일한 프로그램 위치에 있을 수 있으며, 이는 프로그램의 상태 공간에서 다른 상태를 의미한다. "펼침"이라는 용어는 프로그램 그래프에서 상태 그래프를 생성할 때 이러한 위치의 곱셈에서 유래한다.

자체 전환은 초기 상태와 최종 상태가 동일한 전환이다.

do 루프는 자체 전환의 대표적인 예이다. do 루프는 동일한 증가 명령을 반복 실행하지만, 상태 공간은 사이클이 아닌 선이다. 상태는 프로그램 위치와 증가하는 카운터 값의 조합이기 때문이다. 오버플로가 발생하여 카운터가 다시 0이 되면 초기 상태가 상태 공간에서 다시 방문되어 사이클을 닫는다.

순서도는 어떤 작업의 시작부터 끝까지 진행을 설명하기 때문에 제조업의 조립 라인과 비교할 수 있다. 반면 상태 기계는 일반적으로 이러한 진행에 대한 개념이 없다. 상태 기계의 상태는 처리 단계가 아닌 동작을 지정하는 효율적인 방법이다.

참조

_[1] 웹사이트 https://web.archive.[...] "*"
_[2] 서적 Sequential Machines and Automata Theory John Wiley and Sons 1967
_[3] 서적 Introduction to Automata Theory, Languages, and Computation Addison-Wesley Publishing Company 1979
_[4] 서적 Introduction to the Theory of Switching Circuits McGraw-Hill 1965
_[5] 논문 Statecharts: A visual formalism for complex systems http://www.wisdom.we[...] 1987-06
_[6] 논문 Formal Semantics and Analysis Methods for Simulink Stateflow http://www.csl.sri.c[...] 2002
_[7] 논문 A Visual Formalism for Complex Systems http://www.fceia.unr[...] 1987
_[8] 논문 Symbolic analysis for improving simulation coverage of Simulink/Stateflow models http://drona.csa.iis[...] ACM 2008
_[9] 서적 Practical UML Statecharts in C/C++, Second Edition: Event-Driven Programming for Embedded Systems Newnes