상태 변환 표
State-transition table오토마타 이론과 순차 논리학에서 상태-변환 표는 현재 상태 및 기타 입력에 기초하여 유한 상태 기계가 어떤 상태(또는 비계수적 유한 자동화의 경우 상태)로 이동하는지 보여주는 표다.본질적으로 다른 입력과 함께 입력에 현재 상태가 포함되고, 출력에는 다른 출력물과 함께 다음 상태가 포함되는 진리표다.
상태 변환 표는 유한 상태 기계를 지정하는 여러 방법 중 하나이다.다른 방법으로는 상태 다이어그램을 들 수 있다.
공통양식
원차원
상태 변환 표는 특성 표라고도 하는 1차원 표라고도 한다.그들은 2차원적 형태라기보다는 진리표에 훨씬 가깝다.단일 치수는 상태 전환과 관련된 입력, 현재 상태, 다음 상태 및 (선택적으로) 출력을 나타낸다.
| 입력 | 현재 상태 | 다음 상태 | 출력 |
|---|---|---|---|
| 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차원 테이블이다.그것들을 배열하는 데는 두 가지 일반적인 방법이 있다.
첫 번째 방법에서 치수 중 하나는 현재 상태를 나타내고 다른 하나는 입력을 나타낸다.행/열 교차로에는 상태 전환과 관련된 다음 상태 및 (선택적으로) 출력이 표시된다.
입력 현재 상태 | I1 | I2 | … | In |
|---|---|---|---|---|
| S1 | Si/Ox | Sj/Oy | … | Sk/Oz |
| S2 | Si′/Ox′ | Sj′/Oy′ | … | Sk′/Oz′ |
| … | … | … | … | … |
| Sm | Si″/Ox″ | Sj″/Oz″ | … | Sk″/Oz″ |
두 번째 방법에서 치수 중 하나는 현재 상태를 나타내고 다른 하나는 다음 상태를 나타낸다.행/열 교차로들은 상태 전환과 관련된 입력 및 (선택적으로) 출력을 나타낸다.
다음 상태 현재 상태 | S1 | S2 | … | Sm |
|---|---|---|---|---|
| S1 | Ii/Ox | — | … | — |
| S2 | — | — | … | Ij/Oy |
| … | … | … | … | … |
| Sm | — | Ik/Oz | … | — |
기타 양식
복수의 유한 상태 기계의 동시 전환은 행 쌍이 현재 상태를 다음 상태로 매핑(세트)하는 n차원 상태 변환 표에서 효과적으로 나타낼 수 있다.[1]이것은 독립된 상호의존적인 유한 상태 기계들 사이의 통신을 나타내는 대안이다.
다른 극단에서는, 단일 유한 상태 기계 내의 각 전환에 대해 개별 테이블이 사용되어 왔다. "AND/OR 테이블"[2]은 존재하는 규칙에 대한 결정이 관련 전환의 활성화인 불완전한 결정 테이블과 유사하다.
예
유한 상태 기계에 대한 해당 상태 다이어그램과 함께 상태 변환 표의 예는 다음과 같다.
입력 현재 상태 | 0 | 1 |
|---|---|---|
| S1 | S2 | S1 |
| S2 | S1 | S2 |
 |
상태 변환 표에서 유한 상태 기계에 대한 가능한 모든 입력은 표의 열에 걸쳐 열거되며, 가능한 모든 상태는 행에 걸쳐 열거된다.만약 기계가 상태1 S (첫 번째 행)에 있고 1 (두 번째 열)의 입력을 받는다면, 기계는 상태 S에1 머무를 것이다.이제 기계가 상태 S에1 있고 0(첫 번째 열)의 입력을 수신하면 기계가 상태 S로2 전환된다.
상태 다이어그램에서 전자는 1로 표시된1 S에서1 S로 루핑하는 화살표로 표시되고, 후자는 0으로 표시된1 S에서2 S로 루핑하는 화살표로 표시된다.이 과정은 마르코프 체인을 사용하여 통계적으로 설명할 수 있다.
비결정론적 유한 상태 기계의 경우 입력은 기계를 둘 이상의 상태로 만들 수 있으므로 비결정론이다.이 값은 쌍의 곱슬 교정기 {}로 둘러싸인 모든 대상 상태 집합에 의해 상태 변환 표에 표시된다.비결정적 유한 상태 기계에 대한 해당 상태 다이어그램과 함께 상태 변환 표의 예가 아래에 제시되어 있다.
입력 현재 상태 | 0 | 1 |
|---|---|---|
| S1 | S2 | S1 |
| S2 | {S1, S2} | S2 |
 |
기계가 상태 S에2 있고 입력값 0을 수신할 경우, 기계는1 상태 S와 S의2 두 상태에 동시에 있게 된다.
상태 다이어그램 변환
상태-변환표에서 상태도를 그릴 수 있다.하기 쉬운 일련의 단계는 다음과 같다.
- 주어진 상태를 나타낼 원을 그리십시오.
- 각 상태에 대해 해당 행을 스캔하여 대상 상태로 화살표를 그리십시오.유한 상태 기계가 비결정적이라면 입력 문자에 대해 여러 개의 화살표가 있을 수 있다.
- 상태를 시작 상태로 지정하십시오.시작 상태는 유한 상태 기계의 공식적 정의로 주어진다.
- 하나 이상의 상태를 승인 상태로 지정하십시오.이것은 또한 유한 상태 기계의 공식적 정의에서도 주어진다.
참고 항목
참조
- ^ 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, CiteSeerX 10.1.1.72.8657, doi:10.1109/32.317428
추가 읽기
- 마이클 시퍼:계산 이론 소개.PWS 출판사, 보스턴 1997 ISBN 0-534-94728-X
