AUTOMATAS

REPÚBLICA BOLIVARIAN DE VENEZUELA

UNIVERSIDAD PEDAGÓGICA EXPERIMENTAL LIBERTADOR

INSTITUTO PEDAGOGICO DE BARQUISIMETO

“LUIS BELTRÁN PRIETO FIGUEROA”

Autómatas y Maquina finitas

(UPEL-IPB)

Alumno:

Luis torres

Barquisimeto, Septiembre de 2015

Matemática Discreta

¿Qué es un Circuito Secuencial?

         Es  conocida con ese nombre ya que depende de la salida, además de las variables de entrada, del valor que proviene de la salida. Esto significa que estos circuitos cuentan con una memoria.  Además, una gran parte de los circuitos secuenciales se activan con una señal cíclica o de reloj, y se denominan circuitos secuenciales síncronos.

           

Es decir, que la principal diferencia  entre este circuito y el circuito combinatorio es que en este existe una realimentación de una señal de salida hacia la entrada.

           

En la imagen se puede observar que la salida de la compuerta OR es realimentada y a la misma vez se utiliza como entrada  de la compuerta AND inferior, esto quiere decir que la salida (F) de este circuito digital dependerá de las entradas (A y B), pero también dependerán del valor que tenía la salida  F (la misma salida que se realimenta) previamente.

¿Qué es un Sumador en Serie?

            La función que tiene un sumador en serie binario es sumar dos números binario representados con 0 y 1 cada uno cuenta con una secuencia de pulsos o números, y la suma de dichos números binarios están representadas  por otra secuencia de pulso como por ejemplo.

           

Si A=10011  y  B=10111, la suma que nos saldrá es:

                                                 A       1  0  0  1  1

                                                          +  +  +  +  +

                                                B       1  0  1  1  1

                                                             +  +  +  +

                             Transportado   1      1  1  1    

                                         Suma   1  0  1  0  1  0

                Como  se pudo observar en esta suma se colocaron los bits que representaban las entrada tanto  A como  B y así nos dará una salida en bits el cual es el resultado de A y B.

             Lo importante es que en un circuito en donde se suman los bits que  le corresponden  A  y B también se toman en cuenta los dígitos transportado es decir que si por ejemplo tenemos

0+0+0=0

0+1+0=1

1+1+0=0 y me llevo 1 el cual es dígito trasportado se lleva 1 para la otra entrada.

1+1+1=1 y me llevo 1 el cual es dígito trasportado se lleva 1 para la otra entrada.

            Lo que nos da a entender que todas estas operaciones son combinatoria excepto en las operaciones que trabajan con un dígito transportado ya que esas son secuenciales porque en esa se toma el bits transportado el cual fue producido por durante un periodo de pulso e incorporado al pulso siguiente.

¿Qué es un Autómata?

            Un autómata es una maquina o mecanismo de naturaleza formal, es decir, que solo existe como un mecanismo matemático que acepta una información de entrada (input) y es procesada y sometida a transformaciones simbólicas que se pueden adoptar la forma de un cálculo y cómputo para luego generar un resultado o salida (output), así que para definir un autómata como una maquina  es necesario imaginar a  una máquina capaz de seguir una secuencia finita de pasos al introducir un conjunto de datos en ella, solo se puede leer un dato en cada paso que se realicé, por tanto el número de pasos a seguir está dado por el número de datos a introducir. Cada entrada diferente genera una salida diferente, pero siempre el mismo resultado con los mismos datos de entrada.

Por lo tanto una computación es capaz de resolver un problema, sí y solo sí tiene una solución algorítmica, es decir, puede ser descrito mediante una secuencia finita de pasos bien definidos.

¿Qué es una máquina de estado finito?

            Una máquina de estados finitos es  un modelo abstracto para la manipulación de símbolos, nos permiten saber si una cadena pertenece a un lenguaje o nos pueden generar otro conjunto de símbolos como resultado.

Llamaremos una Máquina de Estados Finitos como Autómata Finito, el hecho es que un Autómata y una Máquina de Estados Finitos son lo mismo, podemos utilizar ambos términos de forma indistinta.

Los Autómatas se caracterizan por tener un Estado inicial, reciben una cadena de símbolos, cambian de estado por cada elemento leído o pueden permanecer en el mismo estado. También tienen un conjunto de Estados Finales o Aceptables que nos indican si una cadena pertenece al lenguaje al final de una lectura.

            Las partes que componen una Autómata son 5 y se pueden definir:

A = {Q, q0, F, Ʃ, δ}

Dónde:

Q: Conjunto finito de estados.

q0: Estado inicial donde q0 ∈ Q. Debe haber uno y sólo un estado inicial.

F: Conjunto de estados finales F ⊆ Q. El estado q0 también puede ser final.

Ʃ: Alfabeto finito de entrada.

δ: Función de Transición Q × Ʃ → Q.

Supongamos que el Autómata se encuentra en el estado qi donde qi ∈ Q, también tenemos el símbolo a donde a ∈ Ʃ. Una entrada a causa que el autómata Cambie del estado qi al estado qk. La función δ, llamada función de transición, describe este cambio de la forma δ (qi, a) → qk de esta forma obtenemos un nuevo estado. Se entiende por transición como el proceso que hace un autómata al cambiar de estado.

La forma más fácil de imaginar  a este  autómata es mediante un diagrama de Transición. Un diagrama de transición es un dígrafo etiquetado con los elementos de un autómata para este caso, pero de hecho se puede representar cualquier Máquina de Estados Finitos por medio de un diagrama de transición, es la forma más común de hacerlo por ejemplo

   En un diagrama de transición existe un nodo por cada estado qi de Q. Los estados finales están encerrados en un círculo doble. El estado inicial q0 es apuntado por una flecha que no proviene de ningún otro estado. Para cada estado qi y un símbolo a, hay exactamente una y sólo una flecha que inicia en qi y termina en δ (qi, a), es decir en qk, la flecha es etiquetada como a. Si qk pertenece a F decimos que la entrada es aceptada.

Debe haber exactamente una flecha saliendo de cada estado por cada símbolo a0, a1, a2...an, por tanto todos los estados tienen el mismo número de flechas saliendo de cada uno de ellos. Con esto garantizamos que nuestro autómata pueda ser llamado Determinista. No importa el estado ni el símbolo leído, siempre hay una transición definida.

 Para describir por completo una función de transición δ ocupamos una Tabla de Transición. Las columnas se etiquetan con los símbolos de entrada, la filas son etiquetadas con los estados y en las intersecciones se colocan los nuevos estados δ (qi, a), suponiendo que qi ∈ Q es la columna y a ∈ Ʃ  la fila que lo intersecta. La tabla de transición de la figura 1 es:

	a1	a2
→q0	q1	q2
q1	q0	q2
← q2	q1	q2

¿Qué es un lenguaje?

            Dado un alfabeto cualquiera I se define I∗ como el conjunto de todas las cadenas finitas que se pueden formar con los elementos de I, es decir los elementos de I∗ son secuencias finitas x = x1. . . xk con xi ∈ I, k ∈  N (se dice que x es de longitud k). Además si k = 0, se habla de la cadena vacía λ.

Si x = x1. . . xk e y = y1. . . ym son elementos de I∗, la concatenación de x e y es la cadena xy = x1. . . xky1. . . ym, que también pertenece a I∗.

            Es un conjunto de cadenas, las cuales deben estar formadas con los símbolos de un Alfabeto Ʃ, entonces decimos que el Lenguaje L está sobre el Alfabeto Ʃ. Por ejemplo: el lenguaje L = {100, 001, 00, 1111} se forma con los elementos de Ʃ = {1, 0}, la cadena σ = 1010 se forma también con los elementos de Ʃ (i.e. σ ∈ Ʃ) pero no pertenece al lenguaje L y se denota σ /∈ L.

¿Qué es un Gramática?

            Una gramática G desde el punto de vista de la teoría de autómatas es un conjunto finito de reglas que describen toda la secuencia de símbolos pertenecientes a un lenguaje específico L. Dos gramáticas que describan el mismo lenguaje se llaman gramáticas equivalentes.

Una gramática es una estructura algebraica formada por cuatro elementos fundamentales:

G = {NT, T, S, P}

Donde:

·         NT es el conjunto de elementos No Terminales

·         T es el conjunto de elementos Terminales

·         S es el Símbolo inicial de la gramática

·         P es el conjunto de Reglas de Producción

Tipo de Gramática:

Gramática Enteras:

         En la gramática  entera tiene como definición  que es como una cadena consistente en un signo opcional  + o −  seguido de una cadena de dígitos que van de 0 al 9. La siguiente gramática genera todos los enteros.

Gramática de Lindenmayer:

Definición 1:

         Una gramática de Lindenmayer interactiva libre de contexto consta de:

         Un conjunto finito N de símbolos no terminales.

         Un conjunto finito T de símbolos terminales, donde N∩T=∅

         Un conjunto finito P de producciones A →B, donde AЄ(N υT) y B Є(N υT)*.

Un símbolo inicial σ Є N.

La diferencia entre una gramática de Lindermayer interactiva libre de contexto y una gramática libre de contexto es que la primera permite el uso de producciones de la forma A →B donde A es un símbolo terminal o no terminal:

Definición 2:

Sea G =(N, P, T,σ) una gramática de Lindenmayer interactiva libre de contexto. Si α= x1... xn

Y existen producciones xi→ βi

En P, para i = 1,..., n, escribimos α⇒βi,...,βn

Decimos que βi,..., βn es derivable de manera directa de α. Si αi+1es derivable de manera directa de αi para i = 1,..., n-1, decimos que αn es derivable de α1y escribimos α1⇒ αn

Decimos que α1⇒ α2⇒ ...⇒ αn es la derivación de αn(a partir de α1). El lenguaje generado por G, denotado por L (G), consta de todas las cadenas de sobre T derivables a partir de α.