## 5 Synthesis Example  
We discuss a synthesis example for Mealy FSM \(A1\) (Figure 6). To implement the FSM circuit, we use LUTs with \(S_{L}=5\). The FSM states correspond to the STG vertices [17]. To show interstate transitions, the vertices are connected by arcs. An STG includes H arcs. The \(h\)-th arc \((h\in\{1,...,H\})\) is marked by a pair \(<l_{h},O_{h}>\). In this pair, the symbol \(l_{h}\) stands for a conjunction of either FSM inputs \(i_{l}\in I\) or their complements. This is an input signal. The set \(O_{h}\subseteq O\) includes FSM outputs \(o_{n}\in O\) generated during the transition number \(h\). The STG (Figure 6) determines the following sets: \(S=\{s_{1},...,s_{9}\}\), \(I=\{i_{1},...,i_{7}\}\), and \(O=\{o_{1},...,o_{7}\}\). Therefore, the FSM \(A1\) is characterized by \(M=9\), \(L=N=7\). There are 22 arcs in the initial STG. This gives 22 transitions among the states of FSM \(A1\). Step 1. This step is omitted if an FSM is represented by STT. The transformation is executed in the following way [14]. The STT includes H lines. Each line corresponds to an STG arc. Each transition is characterized by its current state \(s_{C}\), the next state \(s_{T}\), inputs \(I_{CT}\) (for the \(h\)-th arc, this is the signal \(l_{h}\)), outputs \(O_{CT}\) (for the \(h\)-th arc, this is the OC \(O_{h}\)), and \(h\). Therefore, each arc determines the columns \(s_{C}\), \(s_{T}\), \(I_{CT}\), \(O_{CT}\), and \(h\). Table 1 is an STT of \(A1\). This table uniquely corresponds to the STG (Figure 6). We add the column \(q\) into Table 1 to show the subscripts of output collections. Step 2. The following values of \(L(s_{m})\) can be found from the analysis of Table 1: \(L(s_{m})=1\) for states \(s_{1}\), \(s_{3}\), \(s_{4}\), \(s_{6}\), \(s_{7}\); \(L(s_{m})=2\) for states \(s_{2}\), \(s_{5}\), \(s_{8}\), \(s_{9}\). Additionally, \(M=9\). Using (1) gives \(R1=4\). As follows from the initial conditions of the example, \(S_{L}=5\). Therefore, condition (18) takes place for states with \(L(s_{m})=1\). Thus, the following sets can be created: \(S^{0}=\{s_{1},s_{3},s_{4},s_{6},s_{7}\}\) and \(S2=\{s_{2},s_{5},s_{8},s_{9}\}\). As follows from our analysis, some states may be transferred from \(S^{0}\) to \(S2\). Thus, the elements of these sets can be changed. From Table 1, we can find the sets \(I1=\{i_{1},i_{2},i_{3}\}\) and \(I2=\{i_{2},i_{3},i_{5},i_{6},i_{7}\}\). Step 3. Using known approach [20], we can find the partition \(\pi_{S2}=\{S^{1},S^{2}\}\) of the set \(S1\). It includes the classes \(S^{1}=\{s_{2},s_{5}\}\) and \(S^{2}=\{s_{8},s_{9}\}\). Because the set S1 is a preliminary  
Figure 6: Initial STG. one, this partition is also preliminary. Each class includes \(M_{j}=2\) elements. Using (8) gives the following relation: \(R_{1}=R_{2}=2\). Using (9) gives \(R3=4\). Therefore, there is a set of state variables \(ASV2=\{v_{1},...,v_{4}\}\). Step 4. The classes \(S^{j}\in\pi_{52}\) determine the following sets of inputs: \(l^{1}=\{i_{2},i_{5},i_{6}\}\) and \(l^{2}=\overline{\{i_{3},i_{5},i_{7}\}}\). Therefore, we have \(L_{1}=L_{2}=3\). This means we cannot add new inputs in these sets due to violation of condition (10). Each set \(S^{j}\in\pi_{52}\) can include up to 3 elements without violation of (10). Therefore, one additional state can be added to each of the sets \(S^{j}\in\pi_{52}\). The method of state redistribution is discussed in detail in the paper [22]. In our current paper, we just show the result of redistribution, which is the following: \(S^{0}=\{s_{1},s_{3},s_{4}\}\) and \(S1=\{s_{2},s_{5},s_{6},s_{7},s_{8},s_{9}\}\). The redistribution gives the following classes: \(S^{1}=\{s_{2},s_{5},s_{7}\}\) and \(S^{2}=\{s_{6},s_{8},s_{9}\}\). Now, we obtain \(M_{1}=M_{2}=3\). Using these values and Formula (8), we can see that \(R_{1}=R_{2}=2\) and \(R4=4\). Therefore, the total number of state variables \(v_{r}\in ASV2\) does not change, but now the set \(S^{0}\) includes fewer elements. Now we can expect a decrease in the value of the LUT count for the circuit of _CoreFC_. Step 5.