Prerrequisito: Diseño de autómatas finitos
Problema: Diseñe un código LEX para construir un DFA que acepte el lenguaje: todas las strings que terminan en «11» sobre las entradas ‘0’ y ‘1’.
Ejemplos:
Input: 100011 Output: Accepted Input: 100101 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 tres estados más A, B 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 y A, se muestra el mensaje «No aceptado».
Nota:
Para compilar un programa LEX, el usuario necesita un sistema UNIX y un flex que se pueda instalar usando sudo apt-get install flex. Con todas las especificaciones anteriores, abra la terminal 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 DEAD
%%
<INITIAL>1 BEGIN A;
<INITIAL>0 BEGIN INITIAL;
<INITIAL>[^01\n] BEGIN DEAD;
<INITIAL>\n BEGIN INITIAL; {printf("Not Accepted\n");}
<A>1 BEGIN B;
<A>0 BEGIN INITIAL;
<A>[^01\n] BEGIN DEAD;
<A>\n BEGIN INITIAL; {printf("Not Accepted\n");}
<B>1 BEGIN B;
<B>0 BEGIN INITIAL;
<B>[^01\n] BEGIN DEAD;
<B>\n BEGIN INITIAL; {printf("Accepted\n");}
<DEAD>[^\n] BEGIN DEAD;
<DEAD>\n BEGIN INITIAL; {printf("Invalid\n");}
%%
int main()
{
printf("Enter String\n");
yylex();
return 0;
}
Producción:
