matemática Discreta: 2012

martes, 3 de julio de 2012

Circuitos secuenciales

Circuitos secuenciales

En la lógica combinacional los circuitos producen una respuesta instantánea, es decir, las salidas se pueden calcular a partir de la combinación de los valores de las entradas en el mismo instante. La lógica combinacional no sirve para construir circuitos que con capacidad de memoria, es decir, funciones lógicas cuya salida en el instante presente depende de entradas en el pasado. Es entonces, cuando los circuitos secuenciales aparecen y cobran relevancia conceptos que no eran tan trascendentes para los circuitos combinacionales, algunos de estos conceptos son: instante presente, instante siguiente, estado, retroalimentación, tiempo de propagación, sincronización, memoria, secuencia, conteo, etc. Obsérvese que el principal concepto involucrado en todos los anteriores es el tiempo.

Los circuitos considerados hasta aquí, tienen la característica de que su salida depende solamente de la combinación presente de valores de las entradas, es decir, a una misma combinación de entrada responden siempre con la misma salida. Debido a esto, estos circuitos se denominan combinacionales.
Los circuitos combinacionales tienen muchas limitantes debido a que no son capaces de reconocer el orden en que se van presentando las combinaciones de entradas con respecto al tiempo, es decir, no pueden reconocer una secuencia de combinaciones, ya que no poseen una manera de almacenar información pasada, es decir no poseen memoria.
Un circuito cuya salida depende no solo de la combinación de entrada, sino también de la historia de las entradas anteriores se denomina Circuito Secuencial. La historia de las entradas anteriores en un momento dado se encuentra resumida en el estado del circuito, el cual se expresa en un conjunto de variables de estado.
El circuito secuencial debe ser capaz de mantener su estado durante algún tiempo, para ello se hace necesario el uso de dispositivos de memoria. Los dispositivos de memoria utilizados en circuitos secuenciales pueden ser tan sencillos como un simple retardador (inclusive, se puede usar el retardo natural asociado a las compuertas lógicas) o tan complejos como un circuito completo de memoria denominado multivibrador biestable o Flip Flop.
Como puede verse entonces, en los circuitos secuenciales entra un factor que no se había considerado en los combinacionales, dicho factor es el tiempo. De hecho, los circuitos secuenciales se clasifican de acuerdo a la manera como manejan el tiempo en circuitos secuenciales síncronos y circuitos secuenciales asíncronos.
En un circuito secuencial asíncrono, los cambios de estado ocurren al ritmo natural marcado por los retardos asociados a las compuertas lógicas utilizadas en su implementación, es decir, estos circuitos no usan elementos especiales de memoria, pues se sirven de los retardos propios (tiempos de propagación) de las compuertas lógicas usados en ellos. Esta manera de operar puede ocasionar algunos problemas de funcionamiento, ya que estos retardos naturales no están bajo el control del diseñador y además no son idénticos en cada compuerta lógica.
Los circuitos secuenciales síncronos, sólo permiten un cambio de estado en los instantes marcados por una señal de sincronismo de tipo oscilatorio denominada reloj. Con esto se pueden evitar los problemas que tienen los circuitos asíncronos originados por cambios de estado no uniformes en todo el circuito.
Entradas como de las variables de estado las cuales son guardadas en dispositivos de memoria. Este es el modelo más completo de un circuito secuencial y se denomina Modelo de Mealy.

Como puede verse, en el modelo de Mealy las salidas en el instante presente pueden depender tanto de las variables de estado (y por lo tanto del estado presente) como de las entradas. A este tipo de salidas se les llama Salidas tipo Mealy.

En general, un circuito secuencial puede ser una combinación de los tres modelos presentados arriba, es decir, puede poseer salidas tanto tipo Mealy como Tipo Moore, o sólo tipo Moore, o puede inclusive no tener dispositivos de memoria y funcionar solamente con la “memoria” asociada a los retardos naturales de las compuertas lógicas.

Conceptos fundamentales para analizar y diseñar circuitos secuenciales

En esta parte se plantearán los conceptos y la terminología necesaria para el análisis y diseño de los circuitos secuenciales. Estos conceptos son:
• Diagrama de estado clásico
• Tabla de funcionamiento
• Tabla de estado o tabla característica
• Diagrama de tiempo
• Tabla de excitación
• Diagrama de flujo de estado o carta ASM (Algorithmic State Machine)

Multivibradores Biestables (Flip Flops).

Los circuitos secuenciales básicos que funcionan también como unidades de memoria elementales se denominan multivibradores biestables (por tener dos estados estables –alto y bajo-), también conocidos como Flip Flops.

Al definir cada una de las herramientas mencionadas en la lista anterior consideraremos un circuito lógico secuencial asíncrono fundamental llamado Flip Flop Set Reset (FF-SR) el cual se describe a continuación con ayuda de las herramientas mencionadas.

El Flip Flop Set Reset FF-SR

El FF-SR es un dispositivo con dos entradas (Set y Reset) y una variable de estado o salida (Q) capaz de “guardar” un bit de información y funciona como sigue:
• Si su entrada Set se activa su estado Q se pone en Alto
• Si su entrada Reset se activa su estado Q se pone en Bajo
• Si no se activa ni Set ni Reset su estado no cambia
• Por supuesto, no se permite activar Set y Reset simultáneamente.

Diagrama de Bloques

Aunque el FF-SR posee dos entradas (S y R) y sólo una salida (Q), es común la implementación que provee además de Q su versión complementada Ǭ, como se muestra en la figura siguiente

Tabla de Funcionamiento

Los fabricantes de los circuitos integrados usan una tabla de funcionamiento para describir la operación de un circuito de una manera compacta, dicha tabla de funcionamiento no es otra cosa que una tabla de verdad como la usada para circuitos combinacionales, en la cual se ha introducido la información del tiempo que en el caso de circuitos secuenciales se vuelve esencial. Enseguida se ilustrará el uso de esta tabla para describir de manera compacta el funcionamiento del FF-SR.

En donde se ha utilizado la siguiente notación:

Tn = instante en el cual se aplican las entradas.
Tn+1 = instante después que el circuito responde.
Qo = salida Q en el instante tn.
Q+ = salida en el instante tn+1.

Nota: No es difícil notar que la tabla de funcionamiento es una tabla de verdad con la variable introducida Qo.

Diagrama de Estado Clásico

La misma información especificada por la tabla de funcionamiento puede ser representada de varias maneras diferentes, por ejemplo, el siguiente diagrama es una alternativa gráfica que tiene la particularidad de enfatizar el número y nombre de los estados del circuito, por ello se le llama diagrama de estado o de estado clásico. Así, para el FF-SR:

Obsérvese que el diagrama de estado clásico incluye información separada de la siguiente manera:

Nombres simbólicos dados a los estados (opcional)
Nombres y valores que las variables de estado toman en cada estado.
Nombres y valores de las variables de entrada
Transiciones posibles de un estado a otro y condiciones (sobre las variables de entrada) para producir dicha transición.
En algunas variantes de diagrama de estado se incluye también información sobre las variables de salida que no se muestran en el ejemplo, dado que para el FF-SR la variable de estado Q coincide con la variable de salida.

Tabla de Excitación

La información que guarda el diagrama de estado clásico se puede representar en forma de tabla colocando todas las transiciones posibles de un estado a otro como variables independientes de la tabla y las entradas como variables dependientes, es decir, se genera un renglón de la tabla por cada transición y anotando los valores necesarios de las entradas para producir dicha transición. Así, para el ejemplo del FF-SR se obtiene:

Tabla de Estado o Tabla Característica

Esta es otra manera de organizar en forma de tabla el comportamiento del circuito secuencial, Se trata básicamente de la misma tabla de funcionamiento ya descrita, salvo que ahora no se introduce ninguna variable de manera que el estado presente (Qo) se trata como si fuera otra entrada.
Para el ejemplo del FF-SR tendremos:

Diagramas de tiempo

Los diagramas de tiempo son representaciones gráficas de la evolución de los valores que toman las variables de interés en un circuito digital, de la manera como se podrían ver en la pantalla de un osciloscopio.
Los diagramas de tiempo no son una herramienta propia de los circuitos secuenciales, ya que estos también son útiles para circuitos combinacionales como se ilustró en los capítulos anteriores, sin embargo, en el caso de los circuitos secuenciales, la información de tiempo es más crucial por esto los diagramas de tiempo cobran una mayor importancia que en el caso combinacional.
Es importante mencionar que estos diagramas no son únicos para un circuito dado, de hecho, pueden poseer información incompleta o en ocasiones redundante. Así, para el ejemplo del FF-SR un posible diagrama de tiempo sería como en la siguiente figura:

Diseño de un circuito secuencial

De acuerdo a las estructuras planteadas para los circuitos secuenciales se puede ver que éstos se pueden diseñar con las herramientas descritas para los circuitos combinacionales, pero tomando en cuenta la retroalimentación del estado presente.

Diseño del Flip Flop Set Reset.

Como ejemplo introductorio, consideraremos el problema de diseñar el Flip Flop-SR. En este caso la salida Q+ depende del estado anterior Qo y de las entradas S y R, es decir,
Q+ = f(Qo, S, R)
Es decir, el diseño lo plantearemos como si se tratara de un circuito combinacionale, pero considerando Qo como si fuera una entrada más. Esta función la podemos plantear por medio de la siguiente tabla de verdad, obtenida de la tabla de estado descrita anteriormente:

El Mapa de Karnaugh correspondiente es el siguiente:

De donde podemos obtener la expresión siguiente. (Aunque no es un procedimiento común, la experiencia a demostrado que se puede obtener una implementación más sencilla despreciando las condiciones sin cuidado), entonces

Para implementar con sólo compuertas NOR negamos dos veces la expresión para obtener

Con lo cual podemos implementar el FF-SR con sólo dos compuertas NOR, como sigue

Esta implementación además tiene la ventaja de que también produce la función negada Q a la salida de la primera compuerta NOR, de manera que una mejor manera de dibujar este circuito es como se muestra en la siguiente figura

Diagramas de Flujo de Estado

Una herramienta alternativa para la representación, análisis y diseño de circuitos secuenciales son los
Diagramas de Flujo de Estado, también conocidos como diagramas ASM (Algorithmic State Machine), los cuales no son más que una manera diferente de dibujar un diagrama de estado clásico, con símbolos muy similares a los usados en los Diagramas de Flujo usados para especificar programas de computadora como los que se describen a continuación

Símbolos usados en los diagramas ASM

Bloque de Estado.- El diagrama deberá tener un bloque de estado por cada posible estado presente del circuito.
En este bloque se especifica una lista de las salidas que dependen de este estado (Salidas tipo Moore) y los valores que toman en dicho estado. También se deberá especificar a un lado del bloque los valores que toman las variables de estado.

Bloque de decisión.- Los bloques de decisión son los que establecen las condiciones para que ocurra un cambio de estado, es decir, definen las trayectorias posibles y las condiciones para pasar de un estado a otro.
Dentro del bloque se deberá especificar la expresión lógica (en términos de las entradas) que decide cual es la trayectoria a seguir y en cada salida del bloque se deberá especificar el valor de la expresión para seguir por dicha salida.

Bloque de Salida.- Este bloque siempre viene de un bloque de decisión para especificar salidas cuyo valor depende del estado y de las entradas de dicho bloque de decisión (Salidas tipo Mealy).
Se especifica dentro de este bloque la lista de salidas que dependen del estado y de las entradas así como los valores que toman dichas salidas.

Ejemplo

Para dibujar el diagrama de flujo de estado de un circuito secuencial es importante hacer una lista preliminar que contenga la siguiente información. (Los valores se especifican entre paréntesis para el caso del FF-SR).
- Número de Estados (2)
- Número de variables de estado (1)
- Nombres de las variables de Estado (Q), Entradas (S,R) y Salidas (Q) y tipo (Moore).
Obsérvese que en el caso del FF-SR la única salida corresponde a la única variable de estado, por lo tanto es de tipo Moore.
El número de estados indica directamente el número de bloques de estado, de manera que el diagrama queda como sigue

Eliazar Monserrat
Adrian Segovia
Salvador Morales

Maquina de estado finito.

Maquina de Estado Finito.

Una Máquina de Estado Finito, llamada también Autómata Finito es una abstracción computacional que describe el comportamiento de un sistema reactivo mediante un número determinado de Estados y un número determinado de Transiciones entre dicho Estados.

Las Transiciones de un estado a otro se generan en respuesta a eventos de entrada externos e internos; a su vez estas transiciones y/o subsecuentes estados pueden generar otros eventos de salida. Esta dependencia de las acciones (respuesta) del sistema a los eventos de entrada hace que las Máquinas de Estado Finito (MEF) sean una herramienta adecuada para el diseño de Sistemas Reactivos y la Programación Conducida por Eventos, cual es el caso de la mayoría de los sistemas embebidos basados en micro controladores o microprocesadores.

Sistemas Reactivos.

Un Sistema Reactivo es aquel que interactúa constantemente con su medio ambiente, tiene la característica de ser conducido por eventos (event driven), la respuesta de tiempo es crítica y una vez que el sistema se activa permanece en ese estado de manera indefinida. En estos sistemas los eventos llegan en tiempos impredecibles y el sistema debe tener la capacidad de responder de manera inmediata, en el orden de los milisegundos o microsegundos, sobre todo en sistemas donde la seguridad es crítica (ejemplo: un piloto automático en un avión o una máquina para soporte de vida en un hospital).

La gran mayoría de los sistemas embebidos (en base a micro controladores o microprocesadores) corresponden a esta categoría, debido a que estos sistemas están típicamente conectados a varios tipos de sensores y transductores de entrada encargados de captar los estímulos del medio ambiente (temperatura, presión, luz, magnetismo, fuerza / peso, etc.), procesar dicha información y generar una respuesta del sistema hacia el medio ambiente a través de transductores de salida y actuadores.

Sistemas Transformacionales.

A diferencia de los Sistemas Reactivos un Sistema Transformacional es aquel que recibe cierta información de entrada, realiza una cierta cantidad de cómputo, produce cierta información de salida y luego termina. No muchos sistemas embebidos caen en esta categoría; ejemplos más típicos son las aplicaciones para PC, como por ejemplo: Un procesador de texto

Diagrama de Estado Finito o Diagrama de Transición de Estados

Un Diagrama de Estado Finito es un gráfico que representa los diferentes estados de una MEF y todas las transiciones posibles entre los estados.

Como ejemplo, consideremos un muy simplificado sistema de control de un ascensor:

Estados: El sistema está formado por tres estados: DETENIDO, YENDO_ARRIBA y YENDO_ABAJO. Los diferentes estados se los representa mediante bloques cuadrados (como en este caso) o círculos.

Transiciones: Las transiciones se las representa mediante flechas que indican la dirección de transición de un estado a otro.

Eventos: Los eventos para el sistema en este ejemplo son los siguientes:

selección_piso: Es un evento externo que se genera toda vez que un usuario selecciona un piso o llama al ascensor desde otro piso.
arribo_nuevo_piso: Es un evento interno que se genera cada vez que los sensores detectan que se ha arribado al nuevo piso seleccionado por el usuario.

Los eventos se anotan en el gráfico por encima de las flechas de transición.

Condiciones de Transición: Dos transiciones en este sistema de ejemplo tienen asociadas sus respectivas Condiciones de Transición. No todas las transiciones poseen Condiciones de Transición.

piso_nuevo > piso_actual: Es la condición necesaria para que se produzca una transición del estado DETENIDO al estado YENDO_ARRIBA.
piso_nuevo < piso_actual: Es la condición necesaria para que se produzca una transición del estado DETENIDO al estado YENDO_ABAJO.

Codificación en Lenguaje C.

El sistema de control del ascensor se puede codificar en Lenguaje C de la siguiente manera:

01./* Ejemplo de Máquina de Estado Finito para un ascensor simplificado */

02.enum eEstados { // Los estados se la MEF se definen en una enumaración

03.DETENIDO,

04.YENDO_ARRIBA,

05.YENDO_ABAJO

06.} estado;

07.

08.int piso_nuevo, piso_actual;

09.main() {

10.estado = DETENIDO; // La MEF se inicializa en estado DETENIDO

11.while (TRUE) {

12.switch (estado) {

13.case DETENIDO:{ //

14.// Verificar si se ha seleccionado un nuevo piso:

15.piso_nuevo = seleccion_piso();

16.if (piso_nuevo > piso_actual)

17.estado = YENDO_ARRIBA;

18.else if (piso_nuevo < piso_actual)

19.estado = YENDO_ARRIBA;

20.} break;

21.case YENDO_ARRIBA:{

22.piso_actual = comprobacion_piso();

23.if (piso_nuevo == piso_actual)

24.estado = DETENIDO;

25.} break;

26.case YENDO_ABAJO:{

27.piso_actual = comprobacion_piso();

28.if (piso_nuevo == piso_actual)

29.estado = DETENIDO;

30.} break;

31.}

32.}

33.}

     Como se ve arriba, la MEF se codifica
generalmente en un bloque "switch - case". Todos los estados del
sistema están definidos en una enumeración "enum { ... }" y la
variable "estado" almacena el estado actual del sistema.



Cada opción "case" representa un estado particular de la MEF:

case DETENIDO:{ ... }

case YENDO_ARRIBA:{ ... }

case YENDO_ABAJO:{ ... }

estado = YENDO_ARRIBA;

estado = DETENIDO;

if (piso_nuevo > piso_actual) ... else ...

if (piso_nuevo < piso_actual) ... else ...


Las Máquinas de Estado Finito
no son Diagramas de Flujo

       Las MEF no son diagramas de flujo y no deben
confundirse con los mismos. En una MEF las acciones se asocian con las flechas
(transiciones), mientras que un Diagrama de Flujo las acciones se asocian a los
vértices de la flecha o a los bloques de proceso. Cuando una MEF se encuentra
en uno de sus estados, básicamente se encuentra "en reposo" esperando
a que suceda un evento, mientras que en un Diagrama de Flujo el sistema se
encuentra activo realizando una tarea



















Tipos de Máquinas de Estado
Finito







Existen principalmente dos
tipos de Máquinas de Estado Finito: Las Reconocedoras o Detectoras y las
Transductoras.



Reconocedoras o Detectoras. 




    Llamadas también Detectoras de
Secuencia, realizan básicamente la detección de patrones o secuencias
determinadas en respuesta a las entradas recibidas. Por su definición teórica
este tipo de sistema no proveen señales de salida (acciones), simplemente
transicionan desde un estado inicial a un estado final de "Exito", en
cuyo caso se entiende que un patrón o secuencia ha sido reconocida
exitosamente. Las MEF Detectoras de Secuencia son útiles en aplicaciones en las
que se necesita verificar contraseñas, códigos o la validación de paquetes de
datos en transmisión digital, este último un ejemplo muy típico de su uso. A
continuación se muestra el ejemplo de una verificación de un código /
contraseña con una MEF Detectora de Secuencia:







 
 
  
  
  
  
  
  
  
  
  
  
  
  
 
 
 

 


       En este ejemplo el único
patrón que la MEF aceptará y reconocerá es: 57936. (En realidad cualquier
patrón más largo que contenga la secuencia anterior, como: 1257936 o 5793688
será también reconocido por la MEF, sin embargo la verificación de estos casos
se ha omitido en el ejemplo por simplicidad).


      El estado inicial de la MEF es el denominado "Ninguno". Cualquier evento
(número) diferente a 5 causará una transición al mismo estado y sólo la
recepción de un "5" causará la transición al estado "1
Bueno". La recepción de un "7" en el estado "1 Bueno"
causará una transición al estado "2 Buenos", cualquier otro valor diferente
causará una transición a "Ninguno", lo cual obliga a reiniciar todo
el proceso; y asi sucesivamente hasta llegar al estado "4 Buenos".


        En el estado "4 Buenos", un "6" causará una transición a
"Abierto". A dicha transición está asociada una acción (salida) del
sistema, la cual consiste en "desasegurar" (por ejemplo: abrir una
cerradura). Cualquier otro valor diferente de "6" obliga a reiniciar
el proceso desde "Ninguno".

                                                      
        En el estado "Abierto", un evento "cerrar" (por ejemplo,
cerrar la puerta asociada a la cerradura) causará que el sistema transicione a
"Ninguno" y a dicha transición viene también asociada una acción o
salida del sistema que consiste en "asegurar" el sistema (cerrojo).



Transductoras.

    

     Las MEFs transductoras se caracterizan por
generar acciones o salidas dependiendo de las entradas y/o estados; se
implementan en sistemas embebidos típicamente para aplicaciones de control. Un
ejemplo de este tipo de sistema es el ejemplo del ascensor ya analizado en la
primera parte de este artículo.










Ventajas de las Máquinas de
Estado Finito

Son
     intuitivas y fáciles de entender.
Abstraen
     convenientemente detalles secundarios que no son necesarios para el
     análisis del sistema a un alto nivel y se centran en aspectos claves del
     mismo.
Aportan
     un componente visual que facilita el análisis y diseño del sistema.
Son
     universalmente aplicables.
Su
     uso es común un sistemas de transmisión de datos y el uso de protocolos de
     comunicación.
En
     programación minimiza grandemente la tendencia a escribir "código
     espagueti" y puede ayudar a reducir la
     cantidad de variables globales necesarias, aumentando al mismo tiempo la
     confiabilidad del sistema.





Desventajas de las Máquinas de
Estado Finito

No
     son aplicables a todos los problemas de diseño.
Funcionan
     bien en sistemas pequeños con una cantidad de estados en el órden de las
     decenas.
No
     funcionan bien en sistemas con una cantidad de estados en el órden de las
     centenas o miles de estados, aunque en estos casos es posible la
     estructuración mediante una combinación de MEFs más pequeñas.
La
     adición de funcionalidad es un poco inflexible.
Son
     "planas" por naturaleza, no poseen estructura definida y no
     permiten una jerarquización de los componentes que minimize la repetición
     innecesaria de ciertos estados. Una mejor alternativa en este caso es el
     uso de las Cartillas de Estado (Statecharts) y el uso de UML (Unified
     Modelling Language).
Es
     fácil caer en el error de definir demasiados estados para el sistema, lo
     cual minimiza la eficiencia, o de definir menos estados de lo que es
     necesario, lo cual contradice al propósito de las MEFs de reducir la
     cantidad de código convolucionado (demasiadas sentencias condicionales del
     tipo "if - then - else").







http://www.youtube.com/watch?v=u3j4Qy5nNo4&feature=related

Borrero Daniel

Luimar Abreu

Cardenas Zoraida

Sosa Dubal

AUTÓMATA DE ESTADO FINITO

AUTÓMATA DE ESTADO FINITO

Se trata de una maquina de estado finito en la que 0 ={0,1} , es decir un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida.

Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida.

En los estados para los que la última salida es 1 se llaman Estados de Aceptación.

DEFINICIÓN FORMAL

Formalmente, un autómata finito es una 5-tupla (Q, Σ, q₀, δ, F) donde:

Q es un conjunto finito de estados.
∑ es un alfabeto finito;
q₀ ϵ Q es el estado inicial;
δ: Q x ∑ → Q es una función de transición;
es un conjunto de estados finales o de aceptación.

Autómata de Estados Finitos (AF): Describen, reconocen y definen a los Lenguajes Regulares.

Modelo Matemático de un sistema con estados y salidas discretas.

Tipos de Autómatas Finitos:

- Autómata Finito Determinista (AFD). No pueden estar en más de un estado simultáneamente.

- Autómata Finito No Determinista (AFN). Puede estar en varios estados al mismo tiempo.

Definición de Autómatas de estados Finitos Deterministas (AFD):

Un AFD es una quíntupla A = (Q, Σ, δ, q0, F)

Por ejemplo: si p y q están en Q y a en Σ,

Se define la transición δ (q,a) = p.

En la figura se observa como hay una transición de q a p dado a.

Es decir, existe un arco etiqueta a entre q u p.

Los estados de aceptación se denotan gráficamente con un doble círculo, y en la tabla de transición con asterisco al lado del estado. Por ejemplo si r esta en F debe ser denotado con doble circulo como se observa en la figura.

Nota: En los AFD debe cumplirse que: Para toda a que esta en Σ existe exactamente una transición de salida de cada estado.

Notación para la Función de Transición: Se tiene tres formas para presentar la función de transición cualquiera de ellas es suficiente para completar el diseño del AFD. Estas son:

a) Diagrama de Transición

b) Función de transición

c) Tabla de Transiciones: Representación Tabular

Ejemplo: Dado el lenguaje L = {x | x en {0,1} y x comienza con 0}, es decir todas las cadenas binarias que comienzan con 0. El AFD que lo reconoce es el siguiente:

M = (Q, Σ, δ, q0, F)

Σ= {0,1}, F = {q1}, Q= {q0, q1, q2}

δ	0	1
--> q0	q1	q2
*q1	q1	q1
q2	q2	q2

Función de transición δ

δ(q0,0) = q1

δ(q0,1) = q2

δ(q1,0) = q1

δ(q1,1) = q1

δ(q2,0) = q2

δ(q2,1) = q2

Las tres representaciones de la función de transición son equivalentes, y cada suficiente para dar el AF. Puede escoger una representación pero comprendiendo la relación entre ellas.

Autómata Finito No Determinista AFND.

Son autómatas de estados finitos que tienen la capacidad de estar en más de un estado simultáneamente. Ventaja: son más compactos, flexibles y fáciles de diseñar que los AFD permiten cero, una o más transiciones de salida de un estado para el mismo símbolo. No hay que considerar todos los casos en cada estado.

La diferencia con AFD es la función δ: Q x Σ→ 2Q ó también δ: Q x Σ→ Q*

En la figura δ (q,a) = {p, r}

A= (Q, Σ, δ, q0, F)

δ: Q x Σ → Q*

δ (q,a) = R , R Q , δ(q,a) = {p, r}

Función de Transición Extendida:

δˆ = Q x Σ* → Q*

1) δˆ (q,ε) = {q}

2) δˆ (q,xa) = { r | para algún p en δˆ(q,x), δˆ(p,a) = r }

REPRESENTACIÓN COMO DIAGRAMAS DE ESTADOS

Los autómatas finitos se pueden representar mediante grafos particulares, también llamados diagramas de estados finitos, de la siguiente manera:

Los estados Q se representan como vértices, etiquetados con su nombre en el interior.
Una transición δ desde un estado a otro, dependiente de un símbolo del alfabeto, se representa mediante una arista dirigida que une a estos vértices, y que está etiquetada con dicho símbolo.
El estado inicial q₀ se caracteriza por tener una arista que llega a él, proveniente de ningún otro vértice.
El o los estados finales F se representan mediante vértices que están encerrados a su vez por otra circunferencia.

Ejemplo

Su definición sobre el alfabeto Σ={0,1}, posee dos estados s1 y s2.
Sus transiciones son δ(s1,0)=s2, δ(s1,1)=s1, δ(s2,0)=s1 y δ(s2,1)=s2.
Su estado inicial es s1, que es también su único estado final

Ejemplo:

1 1) Dibuje un diagrama de transmisión para la M.E.F, definida por la tabla siguiente y determine que es un autómata de estado finito. Indique el conjunto de los estados de aceptación: