Lenguajes Y Automatas
Páginas: 4 (864 palabras)
Publicado: 3 de noviembre de 2015
Lenguajes y autómatas I
Expresiones Regulares
Unidad II
Departamento de Sistemas y Computación
Instituto Tecnológico de Nuevo León
agosto–diciembre de 2015
Sistemas de estados finito
Un autómatafinito 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 unsistema 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 ejemplode 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 deservicio 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 deprocesadores 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 cadasí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. Algunosestados 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érticesdel 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...
Expresiones Regulares
Unidad II
Departamento de Sistemas y Computación
Instituto Tecnológico de Nuevo León
agosto–diciembre de 2015
Sistemas de estados finito
Un autómatafinito 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 unsistema 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 ejemplode 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 deservicio 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 deprocesadores 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 cadasí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. Algunosestados 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érticesdel 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...
Leer documento completo
Regístrate para leer el documento completo.