기계 학습

기계 학습은 알고리즘과 컴퓨터 프로그램이 학습 예제로부터 무엇을 배울 수 있는지 연구하는 이론 컴퓨터 과학의 한 분야입니다. 이 문제에서는 기계 학습의 가장 단순한 형태를 구현합니다. 주어진 단어 집합을 올바르게 인식하도록 결정적 유한 오토마타를 학습시킵니다.

형식적으로 결정적 유한 오토마타는 $\langle\Sigma, U, s, T, \varphi\rangle$로 나타냅니다. 여기서 $\Sigma$는 유한한 입력 알파벳($\Sigma = \{0, 1\}$)이고, $U$는 유한한 상태 집합, $s \in U$는 초기 상태, $T \subset U$는 허용 상태 집합, $\varphi : U \times \Sigma \rightarrow U$는 전이 함수입니다.

오토마타의 입력은 $\Sigma$의 기호로 이루어진 단어 $\alpha$입니다. 처음에 오토마타는 상태 $s$에 있습니다. 매 단계마다 입력의 다음 기호 $c$를 읽고, 현재 상태 $u$에서 $\varphi(u, c)$로 이동합니다. 단어 전체를 처리한 뒤 오토마타가 허용 상태에 있으면 $\alpha$를 허용하고, 그렇지 않으면 허용하지 않습니다.

길이가 0부터 $n$까지인 모든 단어를 두 집합 $S^+$와 $S^-$로 나눕니다. 오토마타가 $S^+$의 모든 단어를 허용하고 $S^-$의 모든 단어를 허용하지 않으면, 이 오토마타는 주어진 분할에 맞습니다. 길이가 $n$보다 긴 단어는 허용될 수도 있고 허용되지 않을 수도 있습니다.

주어진 분할에 맞으면서 상태 수가 최소인 오토마타를 구하세요.

첫 줄에 정수 $n$($1 \le n \le 12$)이 주어집니다. 이어서 $2^{n+1}-1$개의 줄이 $S^+$와 $S^-$를 나타냅니다. 각 줄에는 단어 하나가 적혀 있으며, 그 단어가 $S^+$에 속하면 앞에 +가, $S^-$에 속하면 앞에 -가 붙습니다. 단어는 길이순으로 정렬되어 있고, 길이가 같은 단어끼리는 사전순으로 정렬되어 있습니다.

첫 줄에 최소 상태 수 $u$($u \ge 1$)와 초기 상태의 번호 $s$를 출력합니다. 상태는 1부터 $u$까지 번호가 매겨집니다.

둘째 줄에는 허용 상태의 개수 $t$를 출력하고, 이어서 허용 상태의 번호 $t$개를 출력합니다.

그다음 $u$개의 줄을 출력합니다. $i$번째 줄에는 $\varphi(i, 0)$과 $\varphi(i, 1)$을 공백으로 구분해 적습니다.