WARNING:
JavaScript is turned OFF. None of the links on this concept map will
work until it is reactivated.
If you need help turning JavaScript On, click here.
Este Cmap, tiene información relacionada con: Actividad 5 Elaboración de Mapa Conceptual, Los Autómatas Finitos Operaciones posibles Cierre positivo : La operación cierre positivo de un lenguaje L es otro lenguaje L+ obtenido uniendo el lenguaje L con todas sus potencias posibles, excepto L0., Los Autómatas Finitos Operaciones posibles Unión o alternativa : Sean dos lenguajes definidos sobre un mismo alfabeto, se denomina unión de los dos lenguajes al conjunto formado por las cadenas que pertenezcan indistintamente a uno u otro de los dos lenguajes., Determinista Se caracteriza por que cada combinación (estado, símbolo de entrada) produce un solo (estado)., Determinista La minimización La minimización es un proceso que nos permite encontrar, para un dado autómata finito M, un autómata finito M’ con las siguientes propiedades: Si M y M’ comienzan por sus estados iniciales, producirán las mismas salidas para las mismas entradas. De ser posible M’ tendrá menos estados que M. Si esto no es posible, entonces M ya es un autómata mínimo., Los Autómatas Finitos Puede ser Determinista, cada combinación (estado, símbolo de entrada) produce un solo (estado). Equivalencia es Para todo autómata se puede obtener un autómata equivalente (i.e. reconoce el mismo lenguaje) donde el número de estados del autómata sea el mínimo., Diagramas de transición Son Nodos etiquetados por los estados (qi ∈ Conjunto de estados) Arcos entre nodos qi a qj etiquetados con ei (ei es un símbolo de entrada ) si existe la transición de qi , a qj con ei El estado inicial se señala con → El estado final se señala con * o doble círculo, Los Autómatas Finitos Operaciones posibles Concatenación : Sean dos lenguajes definidos sobre el mismo alfabeto, se denomina concatenación de los dos lenguajes al conjunto de todas las cadenas formadas concatenando una palabra del primer lenguaje con otra del segundo., Los Autómatas Finitos Puede ser No determinista, Los Autómatas Finitos Se representa por Diagramas de transición, Los Autómatas Finitos Operaciones posibles Cierreu operación estrella : La operación cierre de un lenguaje L es otro lenguaje L* obtenido uniendo el lenguaje L con todas sus potencias posibles, incluso L0., No determinista Se caracteriza por que cada combinación (estado, símbolo de entrada) produce varios (estado1, estado 2, ..., estado i) y son posibles transiciones con λ, Los Autómatas Finitos Se representa por Tablas de transición, Tablas de transición Son Filas encabezadas por los estados (qi ∈ Conjunto de estados) Columnas encabezadas por los símbolos de entrada (ei ∈ alfabeto de entrada ), Los Autómatas Finitos Operaciones posibles Potencia de un lenguaje : Se denomina potencia i-ésima de un lenguaje a la operación que consiste en concatenarlo consigo mis, cada combinación (estado, símbolo de entrada) produce varios (estado1, estado 2, ..., estado i) y son posibles transiciones con λ Equivalencia es Dado un AFND siempre es posible encontrar un AFD que reconozca el mismo lenguaje: El conjunto de los LAFND = al conjunto de los LAFD. Un AFND no es más potente que un AFD, sino que un AFD es un caso particular de AFND.