DFA en código LEX que acepta un número par de ceros y un número par de unos

Lex es un programa de computadora que genera analizadores léxicos, que se usa comúnmente con el generador de analizadores sintácticos YACC. Lex, originalmente escrito por Mike Lesk y Eric Schmidt y descrito en 1975, es el generador de analizador léxico estándar en muchos sistemas Unix, y se especifica una herramienta equivalente como parte del estándar POSIX. Lex lee un flujo de entrada que especifica el analizador léxico y genera el código fuente que implementa el lexer en el lenguaje de programación C.

Aceptor finito determinista: 
en la teoría de la computación, una rama de la informática teórica, un autómata finito determinista (DFA), también conocido como aceptor finito determinista (DFA) y máquina de estado finito determinista (DFSM), es un autómata de estado finito. máquina que acepta y rechaza strings de símbolos y solo produce un cálculo (o ejecución) único del autómata para cada string de entrada. Determinista se refiere a la unicidad del cálculo. En busca de los modelos más simples para capturar máquinas de estados finitos, McCulloch y Pitts estuvieron entre los primeros investigadores en introducir un concepto similar a los autómatas finitos en 1943.

Acercarse –

LEX nos proporciona un estado INITIAL por defecto. Entonces, para hacer un DFA, use este estado inicial como el estado inicial del DFA. Defina dos estados más, A y B, donde B es el estado muerto que se usaría si encuentra una entrada incorrecta o no válida. Cuando el usuario recibe una entrada que no es válida, muévase al estado B e imprima el mensaje «NO VÁLIDO» y si el usuario llega al estado INICIAL desde el estado A con un «\n», entonces muestre un mensaje «No aceptado». Pero si el usuario obtiene un \n en el estado inicial, el usuario muestra un mensaje «Aceptado».

Ejemplos –  

Input : 1001
Output : Accepted

Input : hjabdba
Output : INVALID

Para implementar el DFA anterior, el usuario debe escribir el siguiente código en un archivo lex con una extensión .l.

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 el terminal de unix y haga lo siguiente: 
1. 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. 
2. 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 –

%{
%}
 
%s A B
 
%%
<INITIAL>1 BEGIN INITIAL;
<INITIAL>0 BEGIN A;
<INITIAL>[^0|\n] BEGIN B;
<INITIAL>\n BEGIN INITIAL; printf("Accepted\n");
<A>1 BEGIN A;
<A>0 BEGIN INITIAL;
<A>[^0|\n] BEGIN B;
<A>\n BEGIN INITIAL; printf("Not Accepted\n");
<B>0 BEGIN B;
<B>1 BEGIN B;
<B>[^0|\n] BEGIN B;
<B>\n {BEGIN INITIAL; printf("INVALID\n");}
%%
 
void main()
{
yylex();
}

Producción – 

nickhil@NICKHIL:~$ lex prpg11.l
nickhil@NICKHIL:~$ cc lex.yy.c -lfl
nickhil@NICKHIL:~$ ./a.out
1000
Not Accepted
hello
INVALID
01010101
Accepted

MÉTODO 2:-

Acercarse:-

LEX nos proporciona un estado INITIAL por defecto. Entonces, para hacer un DFA, use esto como el estado inicial del DFA. Definimos cuatro estados más: A, B, C y DEAD, donde el estado DEAD se usaría si se encontrara 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 INICIAL, muestra el mensaje «Aceptado». Si la string de entrada termina en el estado A, B, C, se muestra el mensaje «No aceptado». 

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("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("Not 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:-

kashyap@kashyap-singh:~$ lex e0e1.l
Kashyap@Kashyap-singh:~$ cc lex.yy.c -lfl
Kashyap@Kashyap-singh:~$ ./a.out
1010
Accepted
hello
INVALID
11100
Not Accepted
111100
Accepted
0001
Not Accepted