상태 전이 표
오토마타 이론과 순차 논리에서, 상태 전이 표(state-transition table)는 현재 상태와 다른 입력에 따라 유한 상태 기계가 어떤 상태(또는 비결정적 유한 오토마타의 경우 여러 상태)로 이동하는지를 보여주는 표이다. 이는 본질적으로 진리표와 유사한데, 입력에는 현재 상태와 다른 입력이 포함되고, 출력에는 다음 상태와 다른 출력이 포함된다.
상태 전이 표는 유한 상태 기계를 명세하는 여러 방법 중 하나이다. 다른 방법으로는 상태 다이어그램이 있다.
일반적인 형태
[편집]1차원
[편집]상태 전이 표는 때때로 1차원 표(특성표, characteristic table)로 표현된다. 이는 2차원 형식보다 훨씬 진리표에 가깝다. 단일 차원은 입력, 현재 상태, 다음 상태 및 (선택적으로) 상태 전이에 연관된 출력을 나타낸다.
상태 전이 표
(S: 상태, I: 입력, O: 출력)입력 현재 상태 다음 상태 출력 I1 S1 Si Ox I2 S1 Sj Oy … … … … In S1 Sk Oz I1 S2 Si′ Ox′ I2 S2 Sj′ Oy′ … … … … In S2 Sk′ Oz′ … … … … I1 Sm Si″ Ox″ I2 Sm Sj″ Oy″ … … … … In Sm Sk″ Oz″
2차원
[편집]상태 전이 표는 보통 2차원 표이다. 일반적으로 두 가지 배열 방식이 있다.
첫 번째 방식에서는 하나의 차원이 현재 상태를 나타내고, 다른 차원이 입력을 나타낸다. 행/열의 교차점은 상태 전이에 관련된 다음 상태 및 (선택적으로) 출력을 나타낸다.
상태 전이 표
(S: 상태, I: 입력, O: 출력)입력현재 상태I1 I2 … In S1 Si/Ox Sj/Oy … Sk/Oz S2 Si′/Ox′ Sj′/Oy′ … Sk′/Oz′ … … … … … Sm Si″/Ox″ Sj″/Oz″ … Sk″/Oz″
두 번째 방식에서는 하나의 차원이 현재 상태를 나타내고, 다른 차원이 다음 상태를 나타낸다. 행/열의 교차점은 상태 전이에 관련된 입력 및 (선택적으로) 출력을 나타낸다.
상태 전이 표
(S: 상태, I: 입력, O: 출력, —: 불가능)다음 상태현재 상태S1 S2 … Sm S1 Ii/Ox — … — S2 — — … Ij/Oy … … … … … Sm — Ik/Oz … —
다른 형태
[편집]여러 유한 상태 기계에서 동시에 발생하는 전이는 사실상 n차원 상태 전이 표로 표현될 수 있으며, 행 쌍이 현재 상태 집합을 다음 상태 집합으로 매핑한다.[1] 이는 서로 독립적이면서 상호 의존적인 유한 상태 기계 간의 통신을 표현하는 대안이다.
다른 한편으로, 단일 유한 상태 기계의 각 전이에 대해 별도의 표가 사용되기도 한다. "AND/OR 표"[2]는 불완전한 의사결정 표와 유사한데, 존재하는 규칙에 대한 결정은 암묵적으로 관련 전이의 활성화이다.
예시
[편집]짝수 개의 0을 포함하는 문자열을 받아들이는 유한 상태 기계에 대한 상태 전이 표와 해당 상태 다이어그램의 예시는 다음과 같다:
상태 전이 표 입력현재 상태0 1 S1 S2 S1 S2 S1 S2
|
상태 전이 표에서는 유한 상태 기계의 모든 가능한 입력이 열에 나열되고, 모든 가능한 상태가 행에 나열된다. 만약 기계가 상태 S1에 있고 입력 1을 받으면, 기계는 S1에 머문다. 반면, 상태 S1에서 입력 0을 받으면, 기계는 S2로 전이한다.
상태 다이어그램에서는 전자가 S1에서 S1로 루프하는 화살표(1로 라벨)로 표시되고, 후자는 S1에서 S2로 가는 화살표(0으로 라벨)로 표시된다. 이 과정은 마르코프 연쇄를 사용하여 통계적으로 설명할 수 있다.
비결정적 유한 오토마타의 경우, 하나의 입력이 기계를 둘 이상의 상태에 놓을 수 있으며, 이것이 비결정적 프로그래밍의 비결정성이다. 이는 상태 전이 표에서 대상 상태 집합을 중괄호 {}로 묶어 표시한다. 다음은 비결정적 유한 상태 기계의 상태 전이 표와 해당 상태 다이어그램의 예시이다:
상태 전이 표 입력현재 상태0 1 S1 S2 S1 S2 {S1, S2} S2
|
예를 들어, 기계가 상태 S2에 있고 입력 0을 받으면, 기계는 S1과 S2 두 상태에 동시에 있게 된다.
상태 다이어그램으로의 변환
[편집]상태 전이 표로부터 상태 다이어그램을 그릴 수 있다. 단계는 다음과 같다:
- 주어진 상태를 나타내는 원을 그린다.
- 각 상태에 대해 해당 행을 스캔하여 대상 상태로 향하는 화살표를 그린다. 기계가 비결정적일 경우, 하나의 입력에 대해 여러 개의 화살표가 있을 수 있다.
- 하나의 상태를 시작 상태로 지정한다. 시작 상태는 유한 상태 기계의 형식적 정의에 주어진다.
- 하나 이상의 상태를 수용 상태로 지정한다. 이것 또한 형식적 정의에 주어진다.
같이 보기
[편집]각주
[편집]- ↑ Breen, Michael (2005), “Experience of using a lightweight formal specification method for a commercial embedded system product line” (PDF), 《Requirements Engineering Journal》 10 (2): 161–172, CiteSeerX 10.1.1.60.5228, doi:10.1007/s00766-004-0209-1, S2CID 16928695
- ↑ Leveson, Nancy; Heimdahl, Mats Per Erik; Hildreth, Holly; Reese, Jon Damon (1994), “Requirements Specification for Process-Control Systems” (PDF), 《IEEE Transactions on Software Engineering》 20 (9): 684–707, Bibcode:1994ITSEn..20..684L, CiteSeerX 10.1.1.72.8657, doi:10.1109/32.317428
추가 읽을거리
[편집]- Michael Sipser: Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X