Autómatas - Apunte de cátedra PDF

Preview

Summary

Apunte de cátedra...

Description

 Definiciones básicas Expresión regular Definición de autómata finito Diagrama de transiciones Ejemplo con unión Ejemplo con cláusula de Kleene Autómata finito determinístico Tabla de transiciones AFD completo Equivalencia Autómatas finitos no determinísticos

Definiciones básicas Volvamos a repasar las definiciones básicas Los lenguajes formales están formados por palabras. Las palabras son cadenas cuyo componente son símbolos de un alfabeto. Simbolo o caracter: Elemento con el cual se forman los alfabetos Por ejemplo el símbolo a puede pertenecer al lenguaje español o ingles pero no al chino. Los símbolos > = & a pertenecen al lenguaje C Alfabeto: conjunto finito de símbolos. Lo identificaremos con la letra sigma (Σ). El alfabeto Σ={0, 1} puede crear el lenguaje binario. Cadena: secuencia finita de símbolos de un alfabeto. Por ejemplo, del alfabeto anterior podemos crear las cadenas 000101010 y 0101 Cadena vacía: Es una cadena que no tiene caracteres y la denotamos con el símbolo épsilon (ε). Este símbolo no forma parte de ningún alfabeto. Palabra: es una cadena que es parte de un lenguaje formal. Una cadena puede o no ser parte de un lenguaje formal, pero una palabra sí lo es. Lenguajes naturales: son aquellos con los que hablamos o escribimos. Evolucionan con el tiempo incorporando términos o reglas gramaticales por lo que las mismas surgen después, de forma que podamos explicar la estructura del lenguaje (sintaxis). El significado de cada palabra (semántica) nos va a importar más que cómo esté compuesto.

Lenguajes formales: son un lenguaje abstracto en el cual nos interesa más la forma (sintaxis) que su significado (semántica). Es por ello que las reglas gramaticales se definen antes, lo que implica que los mismos no puedan evolucionar. Algunos lenguajes formales que podemos crear con el siguiente alfabeto: Σ={0,1} L1= {0001, 10} L2= {1} L3= {ε, (01)*} Universo del discurso o lenguaje universal: se le dice a aquel lenguaje infinito que está formado por todas las palabras que se pueden llegar a formar con los símbolos de un alfabeto dado sumado a la palabra vacía. Por ejemplo Σ={a} W(Σ)={ε, a, aa, aaa, aaaa, aaaaa, …}

Expresión regular Para representar lenguajes regulares podemos utilizar las expresiones regulares. Éstas utilizan el alfabeto del lenguaje y otros símbolos. Con el símbolo epsilon, expresamos que el lenguaje reconoce la palabra vacía. Con el símbolo punto (.) o con nada (como en matemática) expresamos la concatenación de los símbolos El símbolo más (+) o el símbolo barra vertical (|) sirve para representar la unión. Por ejemplo,tenemos el lenguaje regular L = {ab} esto quiere decir que el lenguaje está formado por una única palabra y esa palabra es ab. La expresión regular que representa ese lenguaje, será E = ab o E = a.b ya que es la concatenación entre el símbolo a y el símbolo b. Ahora, si queremos representar lenguajes con más palabras como L = {ab, ba} entonces necesitaremos utilizar la unión. La expresión regular para este lenguaje será L = ab + ba.

Como la unión es conmutativa, yo puedo tener la expresión aa + ab o la expresión a(a + b) y ambas representan el lenguaje con las palabras aa y ab. En este caso, decimos que las expresiones son equivalente. Pero cuidado! Que la expresión aa + b es distinta a la expresión a(a+b) ya que la concatenación tiene mayor prioridad que la unión. Hasta ahora hemos definido lenguajes finitos pero es mucho interesante crear lenguajes infinitos. Para expresarlos tenemos dos operadores más: ● el operador estrella de Kleene (o clausura de Kleene) que se representa con un asterisco como supraíndice (*) ● el operador clausura positiva (supraíndice con +) Entendamoslo con un ejemplo: a* es la expresión regular que representa el lenguaje universal del alfabeto con el símbolo a. En cambio a+ representa lo mismo que a* pero sin la palabra vacía. Entonces podemos ver algunas equivalencias: aa* = a+ ε = ε* = ε+ a*a*=a* a*a*aa* = a+ (ε + a)* = (ε + a)+ = a* Otras equivalencias: Sea R1 R2 y R3 expresiones regulares por si solas, las siguientes también son expresiones regulares: R1+R2 = R2+R1 R1R2 R1*=R1** R1+ R1R3+R2R3 = (R1+R2)R3

Definición de autómata finito Un autómata finito es un modelo matemático para modelar un sistema que recibe una cadena para determinar si esa cadena pertenece o no al lenguaje que ese autómata reconoce. Para ello los autómatas transitan estados a medida que procesan cada carácter. Si cuando todos los caracteres han sido procesado el autómata se encuentra en un estado final o de aceptación, el autómata reconoce la cadena procesada. Es imprescindible que el autómata contenga un único estado inicial sobre el cual comenzar el proceso.

Diagrama de transiciones Todo autómata podemos construirlo con un digrafo. Cada estado será un circulo y vincularemos cada estado con una flecha con un símbolo que denota la transición de un estado a otro cuando se procesa dicho símbolo. El estado inicial lo podemos denotar con un supraíndice menos (-) o con una flecha que apunte al círculo. Los estados finales, en cambio, tendrán un supraíndice más (+) o un doble círculo. Ejemplo

Este autómata reconoce el lenguaje denotado por la expresión regular ab  . Veamos qué pasa cuando dejamos que el autómata determine si ab pertenece o no al lenguaje. El autómata lee el primer carácter: a. Desde el estado 0 transita al estado 1. 0 => a => 1 Ahora que el autómata está en el estado 1, lee el siguiente caracter: b. Desde el estado 1 transita al estado 2. 0 => a => 1 => b => 2 En este momento el autómata no tiene más caracteres que analizar y termina su actividad. Como se encuentra en el estado 2 y el mismo es un estado de aceptación, el autómata ha detectado que la cadena ab pertenece al lenguaje. Vamos a ver qué sucede ahora que le damos a analizar la cadena a. 0 => a => 1 Esto ya lo habíamos visto antes pero, ahora qué? El autómata no tiene más caracteres que leer. Como el autómata terminó en el estado 1, que no es de aceptación, podemos afirmar que el autómata rechaza la cadena a. En este caso veamos la cadena abba. Lee a y transita de 0 a 1. Lee la primer b y transita del 1 al 2. Cuando lee b por segunda vez, el autómata encuentra que no hay más transiciones desde 2 y no puede seguir trabajando. A pesar de estar en un estado final, quedaron caracteres por procesar, entonces el autómata no reconoce la cadena abba 0 => a => 1 => b => 2 => b => ? Ahora un caso más: la cadena baba.

El autómata, como en todos los casos, inicia su actividad en 0. Como no encuentra una transición por el caracter b, el autómata no puede trabajar y afirma que no reconoce la cadena. 0 => b => ?

Ejemplo con unión Tenemos la expresión regular ab + aab o, lo que es lo mismo, a(b + ab). Un posible autómata que la reconoce es:

Ahora agreguemos otra palabra más: a + ab + abb:

Fijense que un estado final puede ser uno intermedio en la representación del autómata. No siempre que tengamos x cantidad de palabras tendremos x estados finales. Veamos este ejemplo: 01+10

Ejemplo con cláusula de Kleene Queremos representar el lenguaje representado por la expresión regular a*

o a(a+b)*c

o (ab)*

Autómata finito determinístico Para que un autómata entre en la definición de deterministico, se debe cumplir que cuando lee un caracter sólo pueda ir a un único estado. Podemos definirlo con: ● un conjunto finito de estados entre los que se encontrará el estado inicial y uno o más estados finales ● un alfabeto ● las transiciones que nos dirán de qué estado a qué estado debe ir según cual caracter Matemáticamente se define como una quintupla: (Q, ∑, T, q0, F) Q será el conjunto de todos los estados finitos ∑ el alfabeto q0 es el estado inicial que será parte del conjunto Q F es el conjunto de estados finales (cada uno de los cuales será parte de Q) T se definirá como una función Qx∑ -> Q o T(q, x) = q2 en donde q será el estado inicial de la transicion, x será un simbolo del alfabeto y q2 será otro o el mismo estado en donde quedará luego de realizada la transición.

Vamos con un ejemplo Sea el autómata X=({0,1,2,3}, {a,b}, T, 0, {3}) T se define con la siguiente forma: T(0,a)=1 T(0,b)=2 T(1,a)=3 T(2,a)=3 Será el siguiente autómata

Tabla de transiciones Hay otra manera mucho más cómoda de representar estas transiciones y es con una tabla. Si miramos el ejemplo anterior, la tabla de transiciones sería a

b

0

1

2

1

3

2

3

3 Donde las columnas son los caracteres del alfabeto, las filas son cada estado y cada par contiene el estado al cual transitaría.

AFD completo Podemos decir apenas vemos una tabla si un Autómata finito deterministico es completo si todas las transiciones por cada caracter van a otro estado, es decir, no tiene ninguna celda sin completar. Computacionalmente vamos a querer trabajar con AAFFDD completos ya que nos permitirá saber si una cadena no es un palabra enseguida. Para eso creamos el estado de rechazo, que será aquel al que vaya cuando no deba procesar más. Para eso, surge la necesidad de completar los AAFFDD que no lo estén. Si vemos la tabla, será cuestión de crear un nuevo estado (que será el de rechazo) y agregar en cada transición por caracter que no vaya a otro estado, que vaya al estado de rechazo. Veamos cómo quedaría nuestro ejemplo con un estado de rechazo: a

b

0

1

2

1

3

R

2

3

R

3

R R

R R R Con lo que nuestro diagrama quedará

Equivalencia Al igual que con las expresiones regulares, con los autómatas finitos también tenemos la equivalencia. Dos autómatas son equivalentes si reconocen el mismo lenguaje

Autómatas finitos no determinísticos Los autómatas no determinísticos se diferencian de los determinísticos en que tenemos más de un estado posible al cual ir por un mismo caracter.

En general utilizamos estos autómatas cuando estamos tratando de construirlos ya que nos puede resultar más sencillo realizar este tipo de autómatas que los no determinísticos. Por ejemplo para hacer el autómata: todas las palabras que empiezan con a y terminan con b es fácil que salga este diagrama

Si vemos la tabla de transiciones para este autómata. a 0

1

1

1

b

{1,2}

2 Entonces, de la función de transición cambia de Qx∑ -> Q a Qx∑ -> 2Q

Autómata finito con transiciones-epsilon TODO...