유한 상태 텍스트 처리 기계

유한 상태 기계(FSM, finite state machine)는 본질적으로 방향 그래프입니다. 그래프의 각 정점을 상태(state) 라고 하며, FSM이 동작하는 동안 상태 중 하나가 현재 상태 가 됩니다. 두 상태를 잇는 각 방향 간선을 전이(transition) 라고 합니다. 조건이 맞으면 현재 상태에서 나가는 전이 하나가 발생하고, 현재 상태는 그 전이가 가리키는 새로운 상태로 바뀝니다.

아주 간단한 예를 살펴봅시다.

이 FSM에는 A와 B라는 두 상태와 1, 2, 3으로 번호가 매겨진 세 전이가 있습니다. 현재 상태가 A이고 전이 1의 조건이 충족되면 현재 상태는 B가 됩니다. 현재 상태가 B이고 전이 2의 조건이 충족되면 현재 상태는 다시 A가 됩니다. 현재 상태가 B이고 전이 3의 조건이 충족되면 현재 상태는 B로 유지됩니다.

이 문제의 입력은 여러 개의 FSM을 설명합니다. 각 전이에는 입력 집합(input set) 이라고 부르는 문자 집합과 출력 문자열(output string) 이라고 부르는 문자열이 연결되어 있습니다. 현재 입력 문자가 어떤 전이의 입력 집합에 속하면 그 전이가 발생할 수 있으며, 전이가 발생하면 해당 출력 문자열이 출력됩니다.

입력은 {FSM 설명, FSM에 줄 입력} 쌍의 나열입니다. 하나의 FSM은 공백 문자(스페이스, 탭, 줄바꿈)로 구분된 다음 항목들로 설명됩니다.

• FSM의 상태 개수를 나타내는 정수. 각 상태마다 순서대로 다음이 주어집니다.
  • 길이 1~8의 상태 이름. 이름은 대소문자를 구분하며 서로 다릅니다.
  • 이 상태에서 나가는 전이의 개수를 나타내는 정수. 각 전이마다 순서대로 다음이 주어집니다.
    • 전이를 활성화하는 입력 집합,
    • 전이가 발생할 때 새로 현재 상태가 되는 상태의 이름,
    • 출력 문자열.

입력 집합과 출력 문자열은 공백이 없는 출력 가능 문자들의 나열이며, 다음과 같은 이스케이프 표기가 나타날 수 있습니다.

• \b — 빈칸(스페이스).
• \n — 줄의 끝.
• \\ — 하나의 역슬래시.
• \0 — 출력 문자열에만 나타나며, 전이가 발생해도 아무것도 출력하지 않음을 뜻합니다.
• \c — 입력 집합 으로 쓰이면 임의의 문자와 대응됩니다. 현재 상태의 다른 전이가 하나도 활성화되지 않았을 때, 입력 집합이 \c 인 전이가 활성화됩니다. 출력 문자열 로 쓰이면 현재 입력 문자를 그대로 출력하며, 한 출력 문자열 안에 여러 번 나타날 수 있습니다.

FSM 설명을 모두 읽은 뒤, 기계는 설명 다음에 오는 첫 완전한 줄에서 시작하는 문자들로 실행을 시작합니다. 시작 상태의 이름은 항상 START이고, 최종 상태의 이름은 항상 END입니다(END는 설명에 상태로 등장하지 않습니다). 기계가 END에 도달할 때까지, 필요하면 줄 경계를 넘어가며 문자를 하나씩 계속 입력합니다. 줄의 끝 문자는 입력 집합이 \n인 전이로만 대응되며, 현재 상태에 \n 전이가 없으면 줄의 끝 문자는 아무 출력 없이 소비되고 상태는 바뀌지 않습니다. 상태 개수가 0이면 입력이 끝납니다. 모든 입력은 형식에 맞음이 보장됩니다.

k번째 FSM(k = 1, 2, …)에 대해 다음 내용을 정확히 한 줄로 출력합니다.

Finite State Machine k:

그리고 다음 줄부터 그 기계의 전이들이 만들어 내는 출력을 이어서 출력합니다.

주어진 예제가 이를 보여 줍니다. 첫 번째 FSM은 한 줄 입력에서 모든 모음을 별표로 바꿉니다. 두 번째 FSM은 대문자 또는 소문자 X 바로 뒤에 오는 모음을 지우며, 역시 한 줄만 처리합니다. 세 번째 FSM은 홀수 번째 모음마다 대소문자를 바꾸고, 느낌표를 만나면 처리를 멈추고 그 입력 줄의 나머지는 무시합니다.