상태 전이표

상태 전이표에서 상태는 유한 상태 기계가 취할 수 있는 모든 가능한 상황이나 조건을 나타낸다. 이는 시스템의 과거 역사를 요약하여 현재의 동작을 결정하는 데 필요한 정보를 담고 있다. 예를 들어, 자동판매기의 경우 '대기 중', '금액 투입 중', '상품 선택 중', '거스름돈 반환 중' 등이 상태에 해당한다. 각 상태는 시스템이 특정 시점에 존재하는 고유한 모드 또는 단계로, 시스템의 메모리 역할을 한다.

상태는 유한하며 명확하게 정의되어야 한다. 즉, 시스템이 가질 수 있는 상태의 총 개수는 제한적이며, 각 상태는 다른 상태와 명확히 구분되는 고유한 의미를 가져야 한다. 이는 상태 전이표의 행이나 열, 또는 상태 전이도의 원으로 표현된다. 상태의 집합은 시스템이 처리할 수 있는 모든 내부 조건을 포괄해야 하며, 설계 단계에서 상태를 올바르게 식별하는 것이 유한 상태 기계의 정확한 동작을 보장하는 핵심이다.

상태 간의 이동은 입력에 의해 발생하며, 이 전이는 상태 전이표에 명시된 규칙에 따라 결정된다. 시스템은 항상 정확히 하나의 현재 상태에 머물며, 입력이 들어오면 표에 정의된 대로 다음 상태로 전이한다. 이 과정에서 출력이 발생할 수 있으며, 출력은 현재 상태와 입력(밀리 기계) 또는 오직 현재 상태(무어 기계)에 의해 결정된다. 따라서 상태는 시스템의 제어 흐름과 논리의 중심 축을 이룬다.

입력은 유한 상태 기계가 현재 상태에서 다음 상태로 전이를 일으키게 하는 외부 신호 또는 사건이다. 상태 전이표에서 입력은 일반적으로 표의 열 헤더나 행 헤더로 나타나며, 각 입력 값과 현재 상태의 조합에 대해 정의된 다음 상태와 출력을 찾을 수 있도록 구성된다. 입력은 이산적인 값을 가지며, 시스템이 인식할 수 있는 모든 가능한 외부 자극의 집합을 형성한다.

입력의 종류는 시스템의 복잡성에 따라 단일 이진 신호부터 복합적인 심볼이나 문자열까지 다양할 수 있다. 예를 들어, 간단한 자동판매기에서는 '동전 투입'이나 '버튼 누름'과 같은 이벤트가 입력에 해당하며, 프로토콜 설계에서는 특정 패킷 헤더나 명령어가 입력의 역할을 한다. 입력은 시스템이 외부 환경과 상호작용하는 핵심 매개체이다.

상태 전이표에서 입력은 현재 상태와 함께 고유한 전이를 결정하는 키 역할을 한다. 동일한 현재 상태라도 다른 입력이 주어지면 서로 다른 다음 상태로 전이하거나 다른 출력을 생성할 수 있다. 이는 시스템의 동작 논리를 명확하고 체계적으로 정의하는 데 기여하며, 특히 디지털 논리 회로나 프로그램 제어 흐름 설계에서 필수적인 요소로 작용한다.

전이는 유한 상태 기계에서 특정 입력이 주어졌을 때 현재 상태에서 다음 상태로의 변화를 의미한다. 상태 전이표의 핵심 구성 요소 중 하나로, 시스템의 동적 행동을 규정한다. 이 전이 규칙은 시스템이 외부 자극에 어떻게 반응하고 내부 상태를 업데이트할지를 결정하며, 이를 통해 복잡한 제어 흐름을 명확하고 체계적으로 모델링할 수 있다.

전이는 일반적으로 조건부로 발생한다. 즉, 시스템이 특정 상태에 있을 때만 정의된 입력에 반응하여 전이가 활성화된다. 상태 전이표에서는 이 관계를 표의 셀 하나로 명시적으로 나타낸다. 예를 들어, 표에서 '현재 상태'가 행(row)으로, '입력'이 열(column)으로 사용되면, 두 요소가 교차하는 셀의 값이 '다음 상태'를 지정하는 방식이다. 이는 모든 가능한 상태-입력 조합에 대한 시스템의 반응을 완전하게 정의하는 데 필수적이다.

전이의 결과는 기계의 유형에 따라 달라진다. 밀리 기계에서는 전이가 발생할 때 출력이 생성되며, 이 출력은 현재 상태와 입력의 조합에 의존한다. 반면 무어 기계에서는 출력이 오직 현재 상태에만 의존하므로, 전이는 주로 다음 상태를 결정하는 역할을 한다. 이러한 차이는 상태 전이표를 작성할 때 '출력' 정보를 어디에 배치할지를 결정하는 기준이 된다.

전이 규칙을 명확히 정의하는 것은 디지털 논리 회로나 프로그램의 제어 유닛을 설계할 때 논리 게이트나 조건문으로 구현하는 토대가 된다. 또한 프로토콜 설계에서 통신 세션의 단계별 진행이나 오류 처리 흐름을 기술하는 데에도 널리 활용된다.

출력은 유한 상태 기계가 특정 상태에서 입력을 받았을 때 생성하는 결과 또는 동작을 의미한다. 상태 전이표에서는 일반적으로 '다음 상태'와 함께 표시되며, 기계의 외부적 행동을 정의하는 핵심 요소이다. 출력의 존재 여부와 표현 방식에 따라 밀리 기계와 무어 기계로 구분된다.

밀리 기계에서는 출력이 현재 상태와 입력의 조합에 의해 결정된다. 따라서 상태 전이표에서 출력은 전이(즉, 현재 상태와 입력이 교차하는 셀)와 연관되어 표시되는 경우가 많다. 반면, 무어 기계에서는 출력이 오직 현재 상태에만 의존한다. 이 경우 상태 전이표에서는 각 상태 자체에 출력 값을 할당하여 표현하거나, 별도의 출력 열을 추가하여 정의한다.

출력은 기계의 목적에 따라 다양한 형태를 가질 수 있다. 디지털 논리 회로에서는 특정 신호(예: HIGH/LOW)를 발생시키고, 프로그래밍 언어 파싱에서는 토큰을 생성하거나 오류를 보고하며, 프로토콜 설계에서는 특정 메시지를 전송하거나 응답을 하는 동작이 될 수 있다. 출력을 명확히 정의함으로써 추상적인 상태 모델이 실제 시스템에서 구체적인 기능을 수행할 수 있게 된다.

상태 전이표의 가장 일반적인 표현 방식은 표 형식이다. 이는 행과 열로 구성된 표를 사용하여 유한 상태 기계의 동작을 명확하고 체계적으로 기술한다. 주로 현재 상태, 입력, 다음 상태, 출력이라는 네 가지 핵심 구성 요소를 열로 나열하고, 각 행은 하나의 특정 전이 규칙을 나타낸다.

표의 구조는 기계의 유형에 따라 약간 다르다. 밀리 기계의 경우, 출력이 전이(즉, 현재 상태와 입력의 조합)에 의해 결정되므로, 표는 보통 '현재 상태', '입력', '다음 상태', '출력'의 네 열로 구성된다. 반면, 무어 기계는 출력이 오직 현재 상태에만 의존하므로, 별도의 출력 표를 사용하거나 상태 자체에 출력 값을 할당하는 방식으로 표현하기도 한다. 이 표 형식은 모든 가능한 상태와 입력 조합에 대한 동작을 한눈에 파악할 수 있어, 디지털 논리 회로나 프로토콜 설계와 같은 분야에서 설계 명세서로 널리 활용된다.

표 형식의 상태 전이표는 특히 디지털 시스템 설계에서 논리 회로로의 직접적인 변환이 용이하다는 장점이 있다. 설계자는 표의 각 행을 조건문(예: if-else 또는 case 문)으로 매핑하거나, 진리표를 통해 조합 논리 회로를 도출할 수 있다. 또한, 표는 모든 가능한 경우를 빠짐없이 나열해야 하므로 설계의 완전성과 명확성을 보장하는 데 도움이 된다.

그러나 상태와 입력의 종류가 매우 많아지면 표가 비대해져 가독성이 떨어질 수 있다는 단점도 있다. 이러한 경우에는 상태 전이도와 같은 그래픽 표현을 병행하거나, 계층적 상태 기계 개념을 도입하여 복잡성을 관리하는 것이 일반적이다.

상태 전이도는 유한 상태 기계의 동작을 시각적으로 표현하는 방법이다. 상태 전이표가 표 형태로 정보를 나열한다면, 상태 전이도는 그래프 이론의 개념을 차용하여 상태와 전이를 노드와 간선으로 나타낸다. 각 상태는 원이나 타원 등의 노드로 표시되며, 노드 안에는 상태의 이름이나 식별자가 기재된다. 상태 간의 전이는 노드를 연결하는 화살표(간선)로 표현되며, 화살표에는 해당 전이를 유발하는 입력 조건과 발생하는 출력이 함께 라벨로 표기된다. 이는 시스템의 전체적인 흐름과 조건부 동작을 직관적으로 이해하는 데 매우 유용하다.

표현 방식은 크게 두 가지로 구분된다. 밀리 기계의 상태 전이도에서는 전이를 나타내는 화살표의 라벨에 "입력/출력" 형식으로 표기하는 것이 일반적이다. 반면, 무어 기계의 경우 출력이 상태 자체에 종속되므로, 출력 정보는 상태를 나타내는 노드 안에 함께 표시하고, 화살표의 라벨에는 입력 조건만 명시한다. 이러한 그래픽 표현은 복잡한 제어 흐름을 설계하거나 프로토콜의 메시지 교환 순서를 분석할 때 특히 효과적이다.

상태 전이도는 소프트웨어 공학과 하드웨어 설계 분야에서 널리 활용된다. 예를 들어, 사용자 인터페이스의 화면 전환 로직, 통신 프로토콜의 상태 관리, 또는 게임 AI의 행동 패턴 설계 시에 상태 전이도를 그려보며 논리를 검증한다. 또한, 자동화 테스트 케이스를 생성하거나 시스템 명세서를 작성하는 문서화 도구로서도 가치가 있다. 시각적 표현의 강점 덕분에 설계 단계에서 팀원 간 의사소통과 논리적 오류의 조기 발견을 용이하게 한다.

밀리 기계는 유한 상태 기계의 한 유형으로, 그 출력이 현재 상태와 입력의 조합에 의해 결정되는 기계이다. 이는 출력이 오직 현재 상태에만 의존하는 무어 기계와 구분되는 핵심적인 특징이다. 밀리 기계는 미국의 전기공학자 조지 H. 밀리의 이름을 따서 명명되었다.

밀리 기계의 동작은 상태 전이표를 통해 명확히 정의할 수 있다. 표의 각 행은 현재 상태와 입력을 조합한 조건을 나타내며, 이에 대응하는 다음 상태와 출력 값을 함께 명시한다. 예를 들어, 시퀀스 검출기나 통신 프로토콜의 상태를 설계할 때, 특정 입력 신호가 들어왔을 때 어떤 상태로 전이하고 동시에 어떤 응답(출력)을 내보낼지를 이 표를 통해 설계한다. 이는 디지털 논리 회로 설계에서 조합 논리와 순차 논리를 함께 활용하여 구현된다.

밀리 기계는 출력이 입력 변화에 즉시 반응할 수 있어, 특정 이벤트에 대한 즉각적인 응답이 필요한 시스템에 적합하다. 예를 들어, 자동판매기에서 동전이 투입되는 입력이 발생하면, 현재 상태(예: '대기 중')와 관계없이 즉시 '금액 누적'이라는 출력 신호를 발생시키는 동작을 모델링할 수 있다. 그러나 출력이 입력과 상태에 동시에 의존하기 때문에, 무어 기계에 비해 회로가 다소 복잡해질 수 있으며, 입력 신호의 불안정한 변화(글리치)가 출력에 직접 영향을 줄 수 있는 단점도 있다.

무어 기계는 유한 상태 기계의 주요 유형 중 하나이다. 무어 기계의 핵심 특징은 출력이 오직 현재 상태에만 의존한다는 점이다. 이는 출력이 상태 전이와 입력에 의해 결정되는 밀리 기계와 대비되는 특성이다. 무어 기계에서 각 상태는 고정된 출력 값을 가지며, 시스템이 그 상태에 머무르는 동안 출력은 변하지 않는다. 이러한 구조는 출력이 상태 전이 시점이 아닌, 상태 진입 후 일정하게 유지되어야 하는 시스템 설계에 적합하다.

무어 기계는 일반적으로 상태 전이표와 상태 전이도로 표현된다. 상태 전이표에서는 각 행이 현재 상태를 나타내고, 각 열이 가능한 입력을 나타내며, 교차점의 셀에는 주어진 입력에 따라 전이될 다음 상태가 기록된다. 출력은 별도의 열로 현재 상태와 매핑되어 표시되거나, 상태 전이도에서는 상태 원 안에 "상태명/출력값" 형식으로 함께 표기된다. 이는 출력이 전이 과정이 아닌 상태 자체에 부착되어 있음을 명확히 보여준다.

무어 기계는 출력이 안정적이고 예측 가능해야 하는 응용 분야에서 널리 사용된다. 예를 들어, 디지털 논리 회로의 카운터나 시퀀스 검출기, 특정 패턴이 감지되었을 때 신호를 지속적으로 발생시키는 시스템, 그리고 간단한 자동화 제어 장치 등이 있다. 또한 프로토콜 설계에서 연결 상태를 나타내는 신호나, 하드웨어 기반의 제어 유닛 설계 시 각 마이크로연산 단계에서의 제어 신호 생성에 무어 기계 모델이 적용되기도 한다.

상태 식별은 유한 상태 기계 설계의 첫 번째이자 가장 중요한 단계이다. 이 과정에서는 시스템이 취할 수 있는 모든 고유한 상태를 정의하고, 각 상태가 시스템의 어떤 조건이나 모드를 대표하는지 명확히 규정한다. 상태는 시스템의 과거 입력에 대한 요약 정보를 담고 있으며, 시스템의 동작을 결정하는 핵심 요소가 된다. 예를 들어, 자동판매기 설계에서는 '대기', '금액 입력 중', '상품 선택 중', '거스름돈 반환' 등과 같은 상태를 식별하게 된다.

효율적인 상태 식별을 위해서는 시스템의 동작을 명확히 이해하고, 중복되거나 불필요한 상태를 최소화하는 것이 중요하다. 너무 많은 상태를 정의하면 설계가 복잡해지고 구현이 어려워지며, 반대로 너무 적은 상태를 정의하면 시스템의 동작을 정확히 표현할 수 없게 된다. 설계자는 시스템의 요구사항을 분석하여, 입력에 따라 변화하는 시스템의 모든 중요한 '상황'을 상태로 추출해야 한다. 이때, 각 상태는 서로 구분 가능해야 하며, 시스템의 모든 가능한 동작 경로를 커버할 수 있어야 한다.

상태 식별이 완료되면, 각 상태에 대한 의미와 시스템이 그 상태에 있을 때의 동작을 문서화한다. 이는 이후 전이 규칙을 정의하고, 상태 전이도를 그리거나 표 형식의 상태 전이표를 작성하는 데 기초 자료가 된다. 잘 정의된 상태는 디지털 논리 회로의 안정적인 동작을 보장하고, 프로그램의 제어 흐름을 명확하게 하며, 프로토콜의 신뢰성을 높이는 데 기여한다.

전이 규칙 정의는 유한 상태 기계 설계 과정에서 핵심적인 단계이다. 이 과정에서는 시스템이 가질 수 있는 모든 현재 상태와 가능한 모든 입력 시나리오를 고려하여, 각 조합에 대해 시스템이 어떻게 반응하고 어떤 다음 상태로 이동할지를 명확히 규정한다. 이 규칙들은 상태 전이표나 상태 전이도와 같은 형태로 문서화되어, 기계의 논리적 동작을 완전하고 모호함 없이 기술한다.

전이 규칙을 정의할 때는 모든 가능한 입력에 대한 처리를 고려하여 설계해야 한다. 일반적으로 정의되지 않은 입력이나 예상치 못한 상황에 대한 처리를 명시함으로써 시스템의 견고성을 보장한다. 이를 위해 종종 명시적인 오류 상태를 도입하거나, 특정 입력을 무시하고 현재 상태를 유지하는 규칙을 추가하기도 한다. 이 단계는 프로토콜 설계나 프로그램 제어 흐름 설계에서 특히 중요하며, 시스템의 신뢰성과 예측 가능성을 결정한다.

정의된 전이 규칙은 이후 코드 구현 패턴으로 구체화된다. 일반적으로 switch-case 문이나 상태-입력 조회 테이블(룩업 테이블)을 사용하여, 논리적 규칙을 실제 프로그래밍 언어의 제어 구조로 매핑한다. 이 구현 단계에서는 정의된 규칙이 정확히 반영되어, 상태 전이표에 명시된 동작과 실제 시스템의 동작이 일치하도록 해야 한다.

상태 전이표를 바탕으로 유한 상태 기계를 실제 소프트웨어나 하드웨어로 구현하는 데는 몇 가지 일반적인 코드 패턴이 사용된다. 가장 기본적인 패턴은 상태 패턴이다. 이 패턴에서는 각 상태를 별도의 클래스로 정의하며, 각 상태 클래스는 입력에 따른 전이와 출력을 처리하는 메서드를 포함한다. 컨텍스트 객체는 현재 상태 객체를 참조하고, 모든 요청을 이 상태 객체에 위임한다. 이 방식은 각 상태의 동작이 명확히 캡슐화되어 새로운 상태 추가가 용이하지만, 상태 클래스 수가 많아질 경우 관리가 복잡해질 수 있다.

또 다른 널리 쓰이는 패턴은 상태 테이블을 직접 구현하는 방법이다. 이는 상태 전이표를 그대로 코드 내의 자료 구조로 옮기는 방식이다. 예를 들어, 현재 상태와 입력을 키로 하고, 다음 상태와 수행할 동작을 값으로 하는 해시맵이나 2차원 배열을 구성한다. 실행 엔진은 루프를 돌며 현재 상태와 입력을 조회하여 테이블에서 다음 상태와 액션을 찾아 실행한다. 이 패턴은 전이 로직이 데이터로 분리되어 명확하며, 상태 전이표를 변경할 때 코드 수정 없이 데이터만 수정하면 된다는 장점이 있다. 하지만 실행할 액션이 복잡할 경우 구현이 까다로울 수 있다.

간단한 유한 상태 기계의 경우, 제어 흐름 문을 사용한 구현도 흔하다. 스위치 문을 중첩하여 현재 상태를 판단한 후, 그 내부에서 입력에 따라 다음 상태로 전이하고 액션을 수행하는 방식이다. 이는 직관적이고 구현이 빠르지만, 상태와 전이가 많아지면 코드가 복잡해지고 유지보수가 어려워진다. 이러한 패턴들은 디지털 시스템 설계에서의 하드웨어 기술 언어 구현부터 프로그래밍 언어의 파서나 게임의 인공지능 로직에 이르기까지 다양한 응용 분야에서 선택적으로 적용된다.

상태 전이표는 통신 프로토콜 설계에서 핵심적인 도구로 활용된다. 프로토콜은 두 개 이상의 개체 간에 데이터를 교환하기 위해 정의된 규칙의 집합으로, 복잡한 상호작용을 명확하게 정의해야 한다. 상태 전이표는 프로토콜의 동작을 유한 상태 기계 모델로 추상화하여, 프로토콜이 가질 수 있는 각각의 상태와, 특정 입력(메시지 수신, 타임아웃 발생 등)에 따라 어떻게 다음 상태로 이동하고 어떤 출력(메시지 전송, 타이머 설정 등)을 내보내는지를 체계적으로 기술한다. 이를 통해 설계자는 프로토콜의 논리적 흐름을 시각적으로 파악하고, 모호함 없이 명세를 작성할 수 있다.

특히 네트워크 프로토콜이나 통신 프로토콜 설계 시, 상태 전이표는 프로토콜의 정확성과 견고성을 검증하는 데 필수적이다. 예를 들어, 연결 지향 프로토콜인 TCP의 연결 설정(3-way handshake) 및 해제 과정, 또는 데이터 링크 계층 프로토콜의 오류 제어 절차는 모두 상태 기반으로 동작한다. 설계 단계에서 상태 전이표를 작성하면, 예상치 못한 입력 시나리오나 데드락 상태에 빠지는 위험을 사전에 발견하고 수정할 수 있다. 또한, 이 명세는 이후 프로토콜 구현을 위한 코드 작성의 청사진 역할을 하여, 개발 과정의 오류를 줄이는 데 기여한다.

위 표는 연결 설정 과정의 단순화된 예시로, 프로토콜 설계에서 상태 전이표가 어떻게 구체적인 동작을 정의하는지 보여준다. 이와 같은 방식으로 세션 관리, 오류 복구, 흐름 제어 등 다양한 프로토콜 기능을 상태 기계 모델로 설계할 수 있다. 결과적으로 상태 전이표는 복잡한 프로토콜 논리를 구조화하고, 구현과 테스트를 체계화하는 표준적인 방법론을 제공한다.

상태 전이표는 유한 상태 기계의 동작을 정의하는 핵심 도구이다. 유한 상태 기계는 시스템이 취할 수 있는 상태의 수가 유한하고, 외부 입력에 따라 상태 간의 전이가 일어나는 수학적 모델이다. 이 모델은 자동 이론과 전산학의 기본 개념으로, 복잡한 시스템의 동작을 단순화하고 체계적으로 설계할 분석하는 데 사용된다.

상태 전이표는 이러한 유한 상태 기계의 모든 동작 규칙을 명확하게 나열한다. 표의 행은 일반적으로 현재 상태를 나타내고, 열은 가능한 입력을 나타낸다. 각 셀은 주어진 현재 상태와 입력 조건에서 시스템이 전이할 다음 상태와 발생해야 할 출력을 명시한다. 이는 설계자가 시스템의 모든 가능한 시나리오를 고려하고, 모호함 없이 동작을 명세화할 수 있게 한다.

유한 상태 기계는 크게 밀리 기계와 무어 기계로 구분된다. 밀리 기계에서는 출력이 현재 상태와 입력의 조합에 의해 결정되는 반면, 무어 기계에서는 출력이 오직 현재 상태에만 의존한다. 이 차이는 상태 전이표를 작성할 때 출력을 어느 열에 배치할지에 영향을 미친다. 두 모델 모두 디지털 논리 회로 설계, 프로그래밍 언어의 파싱 또는 어휘 분석, 그리고 다양한 통신 프로토콜의 설계에 널리 응용된다.

상태 전이표를 통해 설계된 유한 상태 기계는 이후 하드웨어 기술 언어나 소프트웨어 코드로 구현된다. 구현 시에는 switch 문이나 상태 패턴과 같은 코드 구현 패턴이 자주 사용되어, 표에 정의된 전이 로직을 실제 동작으로 변환한다.