Lenguajes y autómatas I Expresiones Regulares
Enviado por beto5408 • 3 de Noviembre de 2015 • Documentos de Investigación • 754 Palabras (4 Páginas) • 329 Visitas
Lenguajes y autómatas I
Expresiones Regulares
Unidad II
Sistemas de estados finito
Un autómata finito es el modelo matemático de un sistema, con
entradas y salidas discretas. El sistema puede estar en cualquiera
de una cantidad finita de configuraciones internas o estados. Los
estados de un sistema conjuntan la información concerniente a
entradas pasadas que se requieren para determinar el
comportamiento del sistema en entradas subsecuentes.
Ejemplo
El control de un elevador es un ejemplo de un sistema de estados
finitos. El mecanismo no recuerda todas las peticiones previas de
servicio, solo el piso actual, la dirección del movimiento (arriba o
abajo) y el conjunto de peticiones de servicio todavía no
satisfechas.
Ejemplos de los sistemas finitos
En las ciencias computacionales se encuentran muchos ejemplos de
sistemas de estados finitos y la teoría de autómatas finitos es útil
para el diseño de estos sistemas.
▶ Editores de texto
▶ Analizadores léxicos
▶ Circuitos de conmutación
La teoría de autómatas finitos es ampliamente utilizada en el
diseño eficiente de procesadores de cadenas.
Autómatas finitos
Consiste en una conjunto finito de estado y un conjunto de
transiciones de estado que ocurren en símbolos de entrada
seleccionados de un alfabeto . Para cada símbolo de entrada
corresponde exactamente una transición de cada estado a otro
estado (posiblemente al mismo). El estado inicial, usualmente
denotado q0, es en el cual el autómata inicia. Algunos estados son
designados como estados finales o de aceptación.
Diagrama de transición
Un grafo dirigido, llamado diagrama de transición, esta asociado
con un autómata finito de manera que:
▶ Los vértices del grafo correspoden a los estados del autómata
finito.
▶ Si hay una transición del estado q al p en la entrada a
entonces hay un arco etiquetado a del estado q al estado p en
el diagrama de transición.
▶ El estado inicial es representado con q0 y le apunta una flecha
que va de la palabra inicio o equivalente al nodo.
▶ El estado final es representado por doble linea en el circulo.
▶ Si el autómata finito acepta la cadena x si la secuencia de
transiciones correspondiente a los símbolos de x lleva del
estado inicial al estado de aceptación.
Definición formal de un autómata finito
Un autómata finito se define formalmente por un 5-tupla
(Q;; ; q0; F), donde
Q Es un conjunto finito de estados
En el alfabeto de entrada finito
q0 Es el estado inicial y q0 2 Q
F Es el conjunto de estados finales y F Q
Es la función de transición que mapea Q ! Q.
Esto es (q; a) 8 q 2 Q ^ a 2
Autómata finito no determinista
Definición
Es
...