Machine Learning

Machine learning is a branch of theoretical computer science that studies what algorithms and computer programs can learn from training examples. In this problem you implement the simplest form of machine learning: train a deterministic finite automaton so that it correctly recognizes the words of a given set.

Formally, a deterministic finite automaton is a tuple $\langle\Sigma, U, s, T, \varphi\rangle$, where $\Sigma$ is the finite input alphabet (here $\Sigma = \{0, 1\}$), $U$ is a finite set of states, $s \in U$ is the initial state, $T \subset U$ is the set of accepting states, and $\varphi : U \times \Sigma \rightarrow U$ is the transition function.

The input to the automaton is a word $\alpha$ over $\Sigma$. Initially the automaton is in state $s$. At each step it reads the next symbol $c$ of the input and moves from its current state $u$ to $\varphi(u, c)$. After the whole word is processed, if the automaton is in an accepting state, it accepts $\alpha$. Otherwise it rejects $\alpha$.

Split all words of length from 0 to a given number $n$ into two sets, $S^+$ and $S^-$. An automaton matches this split if it accepts every word in $S^+$ and rejects every word in $S^-$. Words longer than $n$ may be either accepted or rejected.

Build an automaton that matches the given split and has the minimum possible number of states.

The first line contains an integer $n$ ($1 \le n \le 12$). The next $2^{n+1}-1$ lines describe $S^+$ and $S^-$. Each line contains one word preceded by + if the word is in $S^+$, or by - if it is in $S^-$. Words are sorted by length, and words of equal length are sorted lexicographically.

The first line contains $u$ ($u \ge 1$), the minimum number of states, and $s$, the number of the initial state. States are numbered from 1 to $u$.

The second line contains $t$, the number of accepting states, followed by the $t$ numbers of the accepting states.

Then $u$ lines follow. The $i$-th line contains $\varphi(i, 0)$ and $\varphi(i, 1)$, separated by a space.