Programar Un Autómata En C++

26 de Septiembre del 2012
Omar Ascencio Saavedra
Autómatas

Autómatas y Leguajes regulares
Procesamiento regular de cadenas
Omar Ascencio Saavedra

Objetivo de la práctica
Determinizar eimplementar una máquina de estados y una función de
procesamiento regular de cadenas usando técnicas recurrentes.

Autómata:

0,1
������������

1

������������

0,1

1

������������

0������������

Determinización del Autómata:

0

A=

B* =

D=

E=

C=

1

26 de Septiembre del 2012
Omar Ascencio Saavedra
Autómatas

Minimización del Autómata:
0
]
]

A
CB
D
E

*
*
*

1
]
]
]
]
]

]
]
]
]
]

0
]
]
]
]

*
*
*

A
B
C
D
E

1
]
]
]
]
]

]
]
]
]
]

0
]
]
]
]

A
*B
C
*D
*E

1
]
]
]
]
]]
]
]
]
]

Autómata reducido:

0
������

0

1

������

������

������

0,1
La expresión regular es:
L A=0(0*10*)*0*11(0|1)*|(0*10)*0*|10(0*10)*0*11(0*10)*|10(0*10)*0*|11(0|1)*26 de Septiembre del 2012
Omar Ascencio Saavedra
Autómatas

Código Fuente:
#ifndef _AUTOMATA__
#define _AUTOMATA__
class Automata {
private:
int delta(int estado,char x);
int process(intestado, char *cadena);
public:
bool test(char *cadena);
};
#endif
#include "automatas.h"
int Automata::delta(int estado, char x){
switch(x){
case '0':
switch(estado){
case 0:
return 1;break;
case 1:
return 1;
break;
case 2:
return 1;
break;
case 3:
return 3;
break;
}
break;
case '1':
switch(estado){
case 0:
return 2;
break;
case 1:
return 2;
break;
case 2:
return3;
break;
case 3:
return 3;
break;
}
break;
default:

26 de Septiembre del 2012
Omar Ascencio Saavedra
Autómatas

return (-1);
break;
}
}
int Automata::process(int estado, char*cadena){
for(int i = 0;cadena[i] != 0; i++){
estado = delta(estado,cadena[i]);
}
if((estado == 1) || (estado == 3))
return 2;
else
return 0;
}
bool Automata::test(char *cadena){
int pf = 0;...