ELIMINACION DE FACTORES COMUNES IZQUIERDOS

ELIMINACION DE FACTORES COMUNES IZQUIERDOS UN AUTOMATA FINITO O MAQUINA DE ESTADO FINITO ES UN MODELO MATEMATICO DE UN SISTEMA QUE RECIBE UNA CADENA CONSTITUIDA POR SIMBOLOS DE UN ALFABETO Y DETERMINA SI ESA CADENA PERTENECE AL LENGUAJE QUE EL AUTAMATA RECONOCE. DEFINICION FORMAL FORMALMENTE, UN AUTOATA FINITO (AF) PUEDE SER DESCRITO COMO UNA 5-TUPLA (S,W,T,S,A) DONDE: W ES UN ALFABETO; S UN CONJUNTO DE ESTADOS; T ES LA FUNCION DE TRANSICION: ; ES EL ESTADO INICIAL; ES UN CONJUNTO DE ESTADOS DE ACEPTACION O FINALES. EJEMPLO 1 W= {0,1}, S = {S1, S2}, T = {(S1,0,{S2});(S1,1,{S1});(S2,0,{S1});(S2,1,{S2})} S = S1 A = {S1}. } FORMAS DE REPRESENTAR UN AUTOMATA FINITO ADEMAS DE NOTAR UN AF A TRAVES DE SU DEFINICION FORMAL ES POSIBLE REPRESENTARLO A TRAVES DE OTRAS NOTACIONES QUE RESULTAN MAS COMODAS. FACTORIZACION DE TERMINOS COMUNES IZQUIERDOS INMEDIATOS. EXISTEN GRAMÁTICAS QUE TIENE PRODUCCIONES DE LA FORMA A ¡ Å ß1 Å ß2 COMO POR EJEMPLO: S ¡ I E T S E S I E T S DONDE Å ES EL TÉRMINO COMÚN EN LAS PRODUCCIONES DE A. SIN EMBARGO PARA PODER LLEVAR A CABO EL ANÁLISIS SINTÁCTICO DE LAS MISMAS MEDIANTE ALGUNAS TÉCNICAS SE DEBE ELIMINAR LOS TÉRMINOS COMUNES IZQUIERDOS LLEVANDO A CABO EL PROCESO DE FACTORIZACIÓN SIGUIENTE: LAS PRODUCCIONES A ¡ Å ß1 Å ß2 SE TRANSFORMAN EN LAS SIGUIENTES A ¡ Å A´ A´¡ ß ß2 LAS CUALES NOS GENERAN EL MISMO LENGUAJE. EXISTE UN NUEVO SÍMBOLO NO TERMINAL A´ EN LA GRAMÁTICA, EL CUAL NO ALTERA LA GRAMÁTICA DEL LENGUAJE. GENERALIZANDO EL PROCEDIMIENTO PARA N PRODUCCIONES DE A QUE TIENEN FACTOR COMÚN IZQUIERDO: 1. AGRUPAR TODAS LAS PRODUCCIONES DE A, SIN IMPORTAR CUANTAS SEAN. A ¡ Å ß1 Å ß2 ... Å ßN Λ *DONDE Λ REPRESENTA OTRAS PRODUCCIONES DE A QUE NO TIENEN FACTOR COMÚN IZQUIERDO . 2. REMPLAZAR LAS PRODUCCIONES DE A A UN CONJUNTO EQUIVALENTE MEDIANTE LA SIGUIENTE TRANSFORMACIÓN A ¡ Å A´ Λ A´¡ ß1 ß2 ... ßN