Optimice la tabla de estado de una tabla de estado dada de una máquina completamente especificada utilizando un algoritmo basado en partición.
Ejemplos:
Input : 6 E 0 D 1 F 0 D 0 E 0 B 1 F 0 B 0 C 0 F 1 B 0 C 0 Output : A E, 0 D, 1 B F, 0 D, 0 C E, 0 B, 1 D F, 0 B, 0 E C, 0 F, 1 F B, 0 C, 0 P1=(ACE) (BDF) P2=(ACE) (BD) (F) P3=(AC) (BD) (E) (F) S1=(AC) S2=(BD) S3=(E) S4=(F) S1 S3, 0 S2, 1 S2 S4, 0 S2, 0 S3 S1, 0 S4, 1 S4 S2, 0 S1, 0
Enfoque utilizado:
Para máquina de estado completamente especificada Máquina de estado completamente especificada:
- Dos estados son equivalentes si las salidas son idénticas para todas las combinaciones de entrada Los siguientes estados son equivalentes para todas las combinaciones de entrada.
- La equivalencia de estados es una relación de equivalencia que divide los estados en clases de equivalencia disjuntas.
Máquina M1:
| PD | NS, Z (x=0) | NS, Z (x=1) |
|---|---|---|
| A | mi, 0 | D, 0 |
| B | F, 0 | D, 0 |
| C | mi, 0 | segundo, 1 |
| D | F, 0 | segundo, 0 |
| mi | C, 0 | F, 1 |
| F | segundo, 0 | C, 0 |
- Paso 1 (minimización de estado): identificar y eliminar estados redundantes
- Paso 2 (Asignación de estado): asigne un código binario único a cada estado
- Paso 3 (optimización de lógica combinacional): use códigos de estado no asignados como si no les importara.
- P0={(ABCDEF)}:
Inicialmente agregamos todos los estados en una partición. - P1={(ACE), (BDF)}:
B, D, F tiene otra respuesta de entrada-salida que otros estados. - P2={(ACE), (BD), (F)}:
según la salida del siguiente estado, F tiene otra respuesta de entrada-salida que otros estados del bloque de partición anterior (BDF). - P3={(AC), (BD), (E), (F)}:
Según la salida del siguiente estado, E tiene otra respuesta de entrada-salida que otros estados del bloque de partición anterior (ACE). - P4={(AC), (BD), (E), (F)} :
igual que P3, se encontró una partición equivalente. - Partición equivalente:
P3, aquí, P3 y P4 son iguales, por lo tanto, consideramos P3 como partición equivalente. - Nuevos Estados:
S1=(AC), S2=(BD), S3=(E), S4=(F)
- P0={(ABCDEF)}:
Aquí, los estados A, C se pueden combinar en un estado y los estados B, D se pueden combinar en otro estado. Consideramos S1, S2, S3, S4 como estados de la nueva tabla de estados optimistas.
Entonces, el número de estados se redujo a 4.
A continuación se muestra la implementación del enfoque:
C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct table {
int state;
int output;
} table;
int main()
{
char present_state, temp;
int ps, temp2;
// hash array
int hash;
// Input number of states
scanf("%d", &ps);
// make a table for input of next-state(NS) and output(Z)
table arr[2];
for (int i = 0; i < ps; i++) {
char present_state = 'A' + i;
// next-state(NS) and output(Z) for x=0
scanf("%*c%c%d", &temp, &arr[i][0].output);
// generate present state(PS)
arr[i][0].state = (int)temp - 65;
// next-state(NS) and output(Z) for x=1
scanf("%*c%c%d", &temp, &arr[i][1].output);
// generate present state(PS)
arr[i][1].state = (int)temp - 65;
}
for (int j = 0; j < ps; j++) {
char present_state = 'A' + j;
// print the given state table
printf("%c %c, %d %c, %d\n", present_state, (char)(arr[j][0].state + 65), arr[j][0].output,
(char)(arr[j][1].state + 65), arr[j][1].output);
}
int prev_result;
int new_result;
for (int i = 0; i < ps; i++) {
// divide P0(first partition P0=ABCDEF) according to their output in x=0, 1
// for x=0, x=1 whose output are same, are contained in same partition block
// for the example machine M1, P1 will be generated
// like { (ACE), (BDF) } and stored in prev_result
prev_result[i] = (2 * arr[i][0].output + arr[i][1].output);
}
// --------------------------------------------------------
// run this function for generate n-tn Partition(Pn)
for (int j = 0; j < 100; j++) {
for (int i = 0; i < ps; i++)
// Load previous result in new result
new_result[i] = prev_result[i];
for (int i = 0; i < ps; i++)
hash[i] = 0;
// ************ Update New Result ****************
int op = 100;
// print n-th partition (Pn)
printf("P%d=", j + 1);
for (int i = 0; i < ps; i++) {
// if i-th PS is not visited
if (hash[i] == 0) {
// make i-th PS visited
hash[i] = 1;
printf("(");
for (int j = i; j < ps; j++) {
if (prev_result[i] == prev_result[j]) {
// print n-th partition (Pn)
printf("%c", j + 65);
// increase i-th new-result
new_result[j] = new_result[j] * op;
// update new result according to next state
new_result[j] += (prev_result[arr[j][0].state] * 2 + prev_result[arr[j][1].state]);
hash[j] = 1; // make j-th PS visited
}
}
printf(") ");
op += 100;
}
}
printf("\n");
// Check New and Previous Result according to difference of e, If same
int flag = -1;
for (int x = 0; x < ps - 1; x++) {
for (int y = x + 1; y < ps; y++) {
if (prev_result[x] == prev_result[y]) {
// compare difference of x-th and y-th result(new and prev)
if (new_result[x] != new_result[y]) {
// if difference is not same and break
flag = 0;
break;
}
}
}
if (flag == 0)
break;
}
// ******************** Update Previous Result with new result **********************
int ij = 1;
for (int i = 0; i < ps; i++) {
hash[i] = 0;
}
for (int i = 0; i < ps; i++) {
// if i-th PS is not visited
if (hash[i] == 0) {
// make i-th PS visited
hash[i] = 1;
for (int j = i; j < ps; j++) {
if (new_result[i] == new_result[j]) {
// change values of prev result with minimal value(ij)
// (if Prev_result=[5, 8, 5, 5, 9], if change to [1, 2, 1, 1, 3])
prev_result[j] = ij;
hash[j] = 1; // make j-th PS visited
}
}
ij++;
}
}
// **********************************************************
// Equivalent Partition Found(new result and prev result is same)
if (flag != 0)
break;
}
// ----------- generate optimistic state table ------------------
int ij = 1, s;
for (int i = 0; i < ps; i++) {
hash[i] = 0;
}
for (int i = 0; i < ps; i++) {
// make i-th PS is not visited
if (hash[i] == 0) {
// print S-th partition block of equivalent partition
printf("S%d=(", ij);
// make i-th PS visited
hash[i] = 1;
for (int j = i; j < ps; j++) {
if (prev_result[i] == prev_result[j]) {
// make j-th PS visited
hash[j] = 1;
// print S-th partition block of equivalent partition
printf("%c", j + 65);
}
}
printf(") ");
// assign value of i-th PS for ij-th state
// of new optimistic state table
s[ij] = i;
ij++;
}
}
printf("\n");
for (int j = 1; j < ij; j++) {
int present_state = j;
// print optimistic state table
printf("S%d S%d, %d S%d, %d\n", present_state, (prev_result[arr[s[j]][0].state]),
arr[s[j]][0].output,
(prev_result[arr[s[j]][1].state]),
arr[s[j]][1].output);
}
// ***********************
return 0;
}
Aporte:
7 E 0 C 0 C 0 A 0 B 0 G 0 G 0 A 0 F 1 B 0 E 0 D 0 D 0 G 0
Producción:
A E, 0 C, 0 B C, 0 A, 0 C B, 0 G, 0 D G, 0 A, 0 E F, 1 B, 0 F E, 0 D, 0 G D, 0 G, 0 P1=(ABCDFG) (E) P2=(AF) (BCDG) (E) P3=(AF) (BD) (CG) (E) P4=(A) (BD) (CG) (E) (F) S1=(A) S2=(BD) S3=(CG) S4=(E) S5=(F) S1 S4, 0 S3, 0 S2 S3, 0 S1, 0 S3 S2, 0 S3, 0 S4 S5, 1 S2, 0 S5 S4, 0 S2, 0