Date post: | 11-Jun-2015 |
Category: |
Documents |
Upload: | sistemasuch |
View: | 578 times |
Download: | 1 times |
1
MATEMÁTICA DISCRETA
Clase 12•LENGUAJES FORMALES
•MAQUINA DE ESTADOS FINITOS
Universidad de Ciencias y HumanidadesAlgebra Computacional
2
DEFINICIONES PREVIAS
SIMBOLO.-La noción más primitiva es la de símbolo, que es simplemente una representación distinguible de cualquier información. Los símbolos pueden ser cualesquiera, como w, 9, #, etc., pero nosotros vamosa utilizar las letras a,b,c, etc. Un símbolo es una entidad indivisible.
¿Qué otros símbolos conoce usted que se usen en la vida real?……………………………………………………………………………………………………………………………….
…………………………………………………………………………………………………………………………..….
……………………………………………………………………………………………………………………………...
……………………………………………………………………………………………………………………………...
Universidad de Ciencias y HumanidadesAlgebra Computacional
3
ALFABETO.-Un alfabeto es un conjunto no vacío de símbolos. Así, el alfabeto del idioma español, E = {a, b, c, . . . , z}, es sólo uno de tantos alfabetos posibles. En general utilizaremos la notación ∑para representar un alfabeto.
Universidad de Ciencias y HumanidadesAlgebra Computacional
4
Con los símbolos de un alfabeto es posible formar secuencias o cadenas de caracteres, tales como:•Miguel, gato, mxzxptlk, balks, r, son cadenas del alfabeto español•abc, ccb, cab, aaaabbbccc son cadenas del alfabeto {a,b,c}.
Las cadenas de caracteres son llamadas también palabras.Un caso particular de cadena es la palabra vacía, ε, la cual no tiene ninguna letra (equivale al espacio en blanco).¿Qué otros alfabetos conoce usted que se usen en la vida real?
……………………………………………………………………………………………………………………………….
…………………………………………………………………………………………………………………………..….
Universidad de Ciencias y HumanidadesAlgebra Computacional
5
LONGITUD.-La longitud de una palabra es la cantidad de letras que contiene, contando las repeticiones; se denota por |w| para una palabra w. Por ejemplo:|perro|= 5.|010|= 3¿Cuál es la longitud de las siguientes palabras?
1) Llanta
2) Chino
3) Mieº*^*
4) =/<º
Universidad de Ciencias y HumanidadesAlgebra Computacional
6
CONCATENACIÓN DE PALABRAS.-Cuando escribimos varias palabras o caracteres uno a continuación de otro, se supone que forman una sola palabra (se concatenan). La notación usada para denotar la concatenaciónde dos cadenas α y β es αβ .Por ejemplo1) si w = abra y v = cada, entonces wvbra es la palabra abracadabra.
2) Sea u=ab , v=ca y w=bb. Entoncesuv=abca vw=cabb(uv)w=abcabb u(vw)=abcabb
El resultado de la concatenación de u,v y w es independientede el orden en que las operaciones son ejecutadas. Matematicamente esta propiedad es conocida como asociatividad
Universidad de Ciencias y HumanidadesAlgebra Computacional
7
¿Qué palabras puede usted formar con: yo tengo sed?
……………………………………………………………………………………………………………………………….
…………………………………………………………………………………………………………………………..….
……………………………………………………………………………………………………………………………...
……………………………………………………………………………………………………………………………...
Universidad de Ciencias y HumanidadesAlgebra Computacional
8
NOTACION DE UN ALFABETO.-El conjunto de todas las palabras que se pueden formar con un alfabeto ∑ es denotado convencionalmente por ∑*. Por ejemplo, si ∑ = {a, b}, entonces∑* = {ε, a, aa, aaa, aaaa, . . . , b, bb, . . . , ab, aba, abb, . . .} El conjunto es infinito, pero enumerable.
La potencia k de un alfabeto es el conjunto de cadenas con longitud k Por ejemplo si Σ={0,1} tenemos:Σ1 ={0,1} , Σ2 ={00,01,10,11}
¿Cuál es la potencia 3 de ∑={M,A,T,L,A,B}?
……………………………………………………………………………………………………………………………….
…………………………………………………………………………………………………………………………..….
Universidad de Ciencias y HumanidadesAlgebra Computacional
9
LENGUAJES.-Un lenguaje es simplemente un conjunto de palabras.Así por ejemplo:1) {abracadabra} es un lenguaje (de una sola palabra), 2) {ali, baba, y, sus, cuarenta, ladrones} es otro. 3) El lenguaje L de cadenas de el alfabeto {a,b} en donde cada cadena comienza con una a y tiene longitud par.Las cadenas aa, ab, aaaa, abbb, abab, abbbaaba forman partede ese lenguaje
¿Qué otros lenguajes conoce usted que se usan en la vida real?
……………………………………………………………………………………………………………………………….
……………………………………………………………………………………………………………………………...
……………………………………………………………………………………………………………………………...
Universidad de Ciencias y HumanidadesAlgebra Computacional
10
GRAMATICAS.-Una gramática es una herramienta o notación que nos permite definir un lenguaje por medio de una serie de reglas que nos dicen como construír cadenas válidas (oraciones) para el lenguaje. Por ejemplo1)En matemática tenemos una cierta gramatica 1-)5(=4- no es lo mismo que (1-5)=-42)En el idioma español no es lo mismo “Carlos lee un libro” que “libro Carlos un lee”
Nota.-Una gramática es una forma de describir al lenguaje.
Universidad de Ciencias y HumanidadesAlgebra Computacional
11
MAQUINA DE ESTADOS FINITOS
Ejemplo.-Cuando una aplicación enciende o apaga un LED, existen dos estados; un estado es cuando el LED está encendido y el otro cuando está apagado.
Un autómata finito o máquina de estado finito es unmodelo matemático de un sistema que recibe una cadenaconstituida por símbolos de un alfabeto y determina si esacadena pertenece al lenguaje que el autómata reconoce.
Nota.-Autómata del griego automatos (ατόματος) que significa espontáneo o con movimiento propio,
Universidad de Ciencias y HumanidadesAlgebra Computacional
12
Implementación:Cuando se implementa el concepto de la maquina de estados, se debe de elaborar una lluvia de ideas de todos los estados que se necesitan para una determinada aplicación. Una vez hecho esto se debe identificar el primer estado. Acto seguido debemos responder la siguiente pregunta ¿Que condición se necesita para salir de este estado y que estado es el siguiente?
Universidad de Ciencias y HumanidadesAlgebra Computacional
13
Implementación de una maquina de estado en lenguajePor ejemplo, cuando una aplicación enciende o apaga un LED, existen dos estados; un estado es cuando el LED está encendido y el otro cuando está apagado.
switch (STATE){case (State0): // Encender LED0
break;case (State1): // Encender LED1
break;case (State2); // Encender LED0
break;// ... y así continuamos
default:STATE = State0 //Si por alguna razón un estado
//indefinido ocurre}
Universidad de Ciencias y HumanidadesAlgebra Computacional
14
MODELADO DE SISTEMAS DISCRETOS.-El modelado de fenómenos y procesos es una actividad que permite:•Verificar hipótesis sobre dichos procesos;•Efectuar predicciones sobre el comportamiento futuro;•Hacer simulaciones (eventualmente computarizadas);•Hacer experimentos del tipo “¿qué pasaría si. . . ?”, sin tener que actuar sobre el proceso o fenómeno físico.
Llamamos eventos discretos a aquéllos en los que se considera su estado sólo en ciertos momentos, separados por intervalos de tiempo, sin importar lo que ocurre en el sistema entre estos momentos. Es como si la evolución del sistema fuera descrita por una secuencia de fotografías, en vez de un flujo continuo, y se pasa bruscamente de una fotografía a otra.
Universidad de Ciencias y HumanidadesAlgebra Computacional
15
La noción más básica de los modelos de eventos discretos es la de estado. Un estado es una situación en la que se permanece un cierto lapso de tiempo. Ejemplo 1.-Un ejemplo de la vida real es el de los “estados civiles” en que puede estar una persona: soltera, casada, viuda, divorciada, etc. De uno de estos estados se puede pasar a otro al ocurrir un evento o acción, que es el segundo concepto básico de la modelación discreta.
Universidad de Ciencias y HumanidadesAlgebra Computacional
16
Ejemplo2 .-Se presenta un modelo un aparato telefónico. En esta figura los nombres de los estados se refieren al aparato desde donde llamo,contesto, etc., y en caso contrario se especifica que es el otro(“suena otro”, que se refiere al aparato telefónico del interlocutor). En las transiciones, la “Y” inicial se refiere a acciones que hace uno mismo (por ejemplo, “YD”, que es “yo descuelgo”), mientras que la “O” se refiere al otro teléfono. La “C” de “YC” se refiere a “colgar”, mientras que la “M” es “marcar”.Así, el significado de las transiciones YC, OC, YM, OM, YD y OD deben quedar claras.
Universidad de Ciencias y HumanidadesAlgebra Computacional
17
Ejemplo 3.- (Estados finales)se quiere modelar el funcionamiento de una máquina automáticavendedora de bebidas enlatadas. Dicha máquina acepta monedas de valor 1, 2 y 5, y el precio de cada lata es de 5. Vamos a considerar que el evento llamado “1” es la introducción de una moneda de valor 1 en la máquina, el evento “2” para la moneda de valor 2, etc.
Universidad de Ciencias y HumanidadesAlgebra Computacional
18
•Las flechas indican que moneda se inserta.(evento)
•Los círculos indican que monto se tiene acumulado (estado)
DIAGRAMA DE ESTADOS Y EVENTOS
Estado final
Estado inicial
Universidad de Ciencias y HumanidadesAlgebra Computacional
19
Nota.-Las secuencias de eventos van a representarse por concatenaciones de caracteres, esto es, por palabras. Así, en el ejemplo de la máquina vendedora la palabra “1121” representa la secuencia de eventos “meter 1”, “meter 1”, “meter 2”, “meter 1”.
Universidad de Ciencias y HumanidadesAlgebra Computacional
20
DEFINICIÓN FORMAL DE AUTÓMATAS FINITOS
En esta sección vamos a presentar un formato matemático para representar las mismas informaciones que contiene un diagrama de estados. Como se utiliza terminología matemática en vez de dibujos, decimos que se trata de una notación formal.
Definición.- Una máquina de estados finitos M es un quíntuplo (K,∑,δ,s,F), donde:K es un conjunto de identificadores (símbolos) de estados;∑ es el alfabeto de entrada;s є K es el estado inicial;F⊆K es un conjunto de estados finales;δ : K×∑ → K es la función de transición, que a partir de un estado y un símbolo del alfabeto obtiene un nuevo estado.
Es importante notar que δ es una función y no simplemente una relación; esto implica que para un estado y un símbolo del alfabeto dados, habría un y sólo un estado siguiente.
Universidad de Ciencias y HumanidadesAlgebra Computacional
21
Ejemplo 1.- El autómata finito de la figura puede ser expresado formalmente como:
M = (K,∑,δ,q0,F), donde:
Universidad de Ciencias y HumanidadesAlgebra Computacional
22
La función de transición puede ser expresada mediante una tabla como la siguiente, para este ejemplo:
Nota.-El autómata acepta las palabras que empiezan con a, así como las palabras que contienen aa, y también las que terminan en b, como por ejemplo abab, aaaaa, baaa, etc. En cambio, no acepta babani bba, babba, etc.
Universidad de Ciencias y HumanidadesAlgebra Computacional
23
Ejemplo 2.-Un autómata finito que acepta cualquier cantidad de 1s seguido de un 0.
r0
1
q
¿Qué ocurre al ingresar la cadena ¨1110¨?………………………………………………………………………………………………………¿Qué ocurre al ingresar la cadena ¨111¨?………………………………………………………………………………………………………
0 1
q
r
r q
Universidad de Ciencias y HumanidadesAlgebra Computacional
24
Ejemplo3.-Un autómata A que acepta {x01y donde x,y∈ {0,1}} tiene por diagrama de transición a:
tiene tabla de transición a:
Universidad de Ciencias y HumanidadesAlgebra Computacional
25
1)Dar tres ejemplos de 2 lenguajes basados en el alfabeto {a, b, c}.
2)Indique 3 palabras de longitud 4 usando el alfabeto {012}
3)Diseñar un Autómata finito que acepte las palabras de el alfabeto {a, b} en que la cantidad de a’s es impar.
4) Interprete usted la siguiente máquina de estados(¿Qué ocurre al ingresar la palabra 010 y 000000000001?)
EJERCICIOS COMPLEMENTARIOS
Universidad de Ciencias y HumanidadesAlgebra Computacional
26
5) Cree la tabla de la función de transición del siguiente diagrama (Máquina de Moore)
6) El autómata ¿acepta la cadena 01101 y 1111?