Requisito previo: Diseño de autómatas finitos
Problema: Diseñe un código LEX para construir un DFA que acepte el lenguaje: todas las strings con un número impar de 0 y un número par de 1 sobre las entradas ‘0’ y ‘1’.
Ejemplos:
Input: 10001 Output: Accepted Input: 10011 Output: Not Accepted Input: asdf Output: Invalid
Enfoque:
LEX nos proporciona un estado INICIAL por defecto. Entonces, para hacer un DFA, use esto como el estado inicial del DFA. Ahora definimos cuatro estados más A, B, C y DEAD donde se usaría el estado DEAD si se encontrara con una entrada incorrecta o no válida. Cuando el usuario ingresa un carácter no válido, pasa al estado MUERTO e imprime el mensaje «INVÁLIDO» y si la string de entrada termina en el estado B, muestra el mensaje «Aceptado». Si la string de entrada termina en el estado INICIAL, A, C, se muestra el mensaje «No aceptado». (Consulte aquí ).
Nota:
para compilar un programa lex, el usuario necesita un sistema UNIX y flex que se puede instalar usando sudo apt-get install flex. Con todas las especificaciones anteriores, abra la terminal de Unix y haga lo siguiente:
- Use el programa lex para cambiar el archivo de especificación a un programa en lenguaje C. El programa resultante se encuentra en el archivo lex.yy.c.
- Use el comando cc con el indicador -ll para compilar y vincular el programa con una biblioteca de subrutinas LEX. El programa ejecutable resultante se encuentra en el archivo a.out.
lex lextest cc lex.yy.c -lfl
Código LEX:
%{
%}
%s A B C DEAD
%%
<INITIAL>1 BEGIN A;
<INITIAL>0 BEGIN B;
<INITIAL>[^01\n] BEGIN DEAD;
<INITIAL>\n BEGIN INITIAL; {printf("Not Accepted\n");}
<A>1 BEGIN INITIAL;
<A>0 BEGIN C;
<A>[^01\n] BEGIN DEAD;
<A>\n BEGIN INITIAL; {printf("Not Accepted\n");}
<B>1 BEGIN C;
<B>0 BEGIN INITIAL;
<B>[^01\n] BEGIN DEAD;
<B>\n BEGIN INITIAL; {printf("Accepted\n");}
<C>1 BEGIN B;
<C>0 BEGIN A;
<C>[^01\n] BEGIN DEAD;
<C>\n BEGIN INITIAL; {printf("Not Accepted\n");}
<DEAD>[^\n] BEGIN DEAD;
<DEAD>\n BEGIN INITIAL; {printf("Invalid\n");}
%%
int main()
{
printf("Enter String\n");
yylex();
return 0;
}
Producción:
