Matlab Uch1 Clase12

MATEMÁTICA DISCRETA Clase 12 •LENGUAJES FORMALES •MAQUINA DE ESTADOS FINITOS

1

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 vamos a 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 Humanidades Algebra Computacional

2

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 Humanidades Algebra Computacional

3

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 Humanidades Algebra Computacional

4

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 Humanidades Algebra Computacional

5

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ón de dos cadenas α y β es αβ . Por ejemplo 1) si w = abra y v = cada, entonces wvbra es la palabra abracadabra. 2) Sea u=ab , v=ca y w=bb. Entonces uv=abca vw=cabb (uv)w=abcabb u(vw)=abcabb El resultado de la concatenación de u,v y w es independiente de el orden en que las operaciones son ejecutadas. Matematicamente esta propiedad es conocida como asociatividad Universidad de Ciencias y Humanidades Algebra Computacional

6

¿Qué palabras puede usted formar con: yo tengo sed? ………………………………………………………………………………………………………………………………. …………………………………………………………………………………………………………………………..…. ……………………………………………………………………………………………………………………………... ……………………………………………………………………………………………………………………………...

Universidad de Ciencias y Humanidades Algebra Computacional

7

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 Humanidades Algebra Computacional

8

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 parte de ese lenguaje ¿Qué otros lenguajes conoce usted que se usan en la vida real? ………………………………………………………………………………………………………………………………. ……………………………………………………………………………………………………………………………... ……………………………………………………………………………………………………………………………... Universidad de Ciencias y Humanidades Algebra Computacional

9

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 ejemplo 1)En matemática tenemos una cierta gramatica 1-)5(=4- no es lo mismo que (1-5)=-4 2)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 Humanidades Algebra Computacional

10

MAQUINA DE ESTADOS FINITOS Un autómata finito o máquina de estado finito es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce. 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.

Nota.Autómata del griego automatos (ατόματος) que significa espontáneo o con movimiento propio, Universidad de Ciencias y Humanidades Algebra Computacional

11

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 Humanidades Algebra Computacional

12

Implementación de una maquina de estado en lenguaje Por 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 Humanidades Algebra Computacional

13

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 Humanidades Algebra Computacional

14

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 Humanidades Algebra Computacional

15

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 Humanidades Algebra Computacional

16

Ejemplo 3.- (Estados finales) se quiere modelar el funcionamiento de una máquina automática vendedora 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 Humanidades Algebra Computacional

17

DIAGRAMA DE ESTADOS Y EVENTOS

•Las flechas indican que moneda se inserta.(evento) •Los círculos indican que monto se tiene acumulado (estado) Estado inicial

Universidad de Ciencias y Humanidades Algebra Computacional

Estado final

18

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 Humanidades Algebra Computacional

19

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 Humanidades Algebra Computacional

20

Ejemplo 1.- El autómata finito de la figura puede ser expresado formalmente como: M = (K,∑,δ,q0,F), donde:

Universidad de Ciencias y Humanidades Algebra Computacional

21

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 baba ni bba, babba, etc. Universidad de Ciencias y Humanidades Algebra Computacional

22

Ejemplo 2.Un autómata finito que acepta cualquier cantidad de 1s seguido de un 0.

1

q

0

r

q

0

1

r

q

r ¿Qué ocurre al ingresar la cadena ¨1110¨? ……………………………………………………………………………………………………… ¿Qué ocurre al ingresar la cadena ¨111¨? ………………………………………………………………………………………………………

Universidad de Ciencias y Humanidades Algebra Computacional

23

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 Humanidades Algebra Computacional

24

EJERCICIOS COMPLEMENTARIOS 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?)

Universidad de Ciencias y Humanidades Algebra Computacional

25

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?

Universidad de Ciencias y Humanidades Algebra Computacional

26