Sesion-10-Automatas-y-lenguajes-formales

Vista previa del material en texto

ESTALMAT -Andalucía Actividades 13/14 
_______________________________________________________________________________________
Segundo Curso.
Sesión: 10 Fecha: 18/01/14 Título: Lenguajes Formales y Autómatas
Agenda de la sesión:
1) Motivación
• Se trata de introducir los conceptos de lenguaje y gramática, partiendo de las ideas que puedan tener 
de estas nociones, y ver hasta qué punto pueden ser útiles estas ideas y estructuras en matemáticas.
• La clase se estructurará en una serie de grupos, en función del número exacto de alumnos. Los 
grupos deberían tener entre 3 y 5 miembros. 
• La primera tarea consistirá en pedirles que (por grupos) generen una lista de las principales ideas que 
a ellos les sugiere la noción de lenguaje: ¿qué és?, ¿para qué sirve?, ¿quién y cómo se usa?, ... A 
continuación se hará una puesta en común y se obtendrán las principales ideas.
• La segunda tarea es similar pero en torno a la noción de gramática. En última instancia se trata de ver 
cuáles son los conceptos de partida con los que llegan, y será interesante posteriormente ver cuáles 
son estos mismos conceptos al final de la sesión.
• Por último, se les preguntará si creen que estas ideas de los lenguajes y las gramáticas tienen algo que 
ver con las matemáticas, es decir, si pueden ser útiles para las matemáticas o las matemáticas pueden 
ser útiles para estas ideas ...
2) Autómatas de estados finitos
• Vamos a tirarnos directamente a la piscina. Y sin pasar por una definición exhaustiva de los 
fundamentos correspondientes, vamos a introducir varios ejemplos de autómatas de estados finitos.
• Ejemplo 1: Introduciremos el siguiente ejemplo, y explicaremos el funcionamiento:
• Esto nos permitirá introducir las nociones de:
◦ Estado
◦ Transición
 -------- pié de página
 ESTALMAT -Andalucía Actividades 13/14 
_______________________________________________________________________________________
◦ Estado inicial
◦ Estados finales
• Indirectamente tendremos una primera aproximación a las nociones de lenguaje generado y lenguaje 
reconocido
• El Anexo 1 incluye una versión relativamente simple (tomada de Wikipedia) de las nociones básicas 
sobre autómatas finitos.
• Intentaremos analizar si se entienden las nociones más formales que ya han aparecido. En concreto, 
las ideas de:
◦ Definición formal del autómata como una quintupla, y los componentes, en concreto la función 
de transición.
◦ Representación de la tabla de transiciones
◦ Mecanismo de funcionamiento del autómata
• Ejemplo 2:
◦ A partir de este ejemplo, se pide:
▪ Escribir la tabla de transición
▪ Definir el autómata (como un modelo formal)
▪ Dar algún ejemplo de secuencias que son reconocidas por el autómata y otras que no: ¿existe 
algún patrón de dichas secuencias?
◦ Definición formal del autómata como una quintupla, y los componentes, en concreto la función 
de transición.
• Reto 1: Por grupos, se plantea el siguiente reto:
◦ Partimos del siguiente gráfico
 -------- pié de página
 ESTALMAT -Andalucía Actividades 13/14 
_______________________________________________________________________________________
• Se debe: 
◦ Generar la tabla de transiciones
◦ ¿Cuál es la secuencia más corta de letras que puede aceptar el autómata?
◦ ¿Cuál es la secuencia más larga de letras que puede aceptar?
◦ Indica al menos una secuencia de letras que no acepte el autómata
• Reto 2: Construir un autómata que sea capaz de reconocer como válidas las secuencias de 0 y 1, pero 
de forma que nunca pueda haber dos ceros seguidos ni dos unos seguidos, y la longitud (número de 
ceros y unos) total sea par. 
◦ Por ejemplo, se reconocerán como correctas las secuencias 010101 o 10, pero no serán correctas 
las secuencias 01010 (longitud impar), o 0110 (dos unos seguidos).
• Reto 3: Construir un autómata que sea capaz de reconocer como válidas las secuencias de 0 y 1, pero 
puede haber como máximo una repetición seguida de un símbolo. No importa la longitud total de la 
secuencia.
◦ Por ejemplo, son correctas las secuencias 01010, 1010, 0011001
◦ Y son incorrectas 011100 (tres dígitos 1 seguidos)
3) Expresiones Regulares
• Es bien conocido que existe una correspondencia exacta entre autómatas de estados finitos y 
expresiones regulares, así que en esta parte vamos a introducir la noción de expresión regular, aunque 
sólo abordaremos los modelos básicos de especificación, dejando muchas de las características más 
avanzadas de éstas. En concreto, se explicarán los operadores de agrupación, alternación, y 
cuatificación (Anexo 2). Es decir, explicaremos los operadores:
◦ ( )
◦ |
◦ * + ?
 -------- pié de página
 ESTALMAT -Andalucía Actividades 13/14 
_______________________________________________________________________________________
• Ejemplo 3:
• Reto 4:
◦ Definir las expresiones regulares correspondientes a los autómatas de los ejemplos 1 y 2
• Reto 5:
◦ Construye tres autómatas y sus expresiones regulares correspondientes. Asígnale un nivel de 
dificultad de 1 a 3. Se colocarán en un paquete con 
◦ Una vez construidos cada grupo tendrá que coger un reto de cada uno de los niveles de dificultad. 
Si lo resuelve logrará los puntos del nivel, y si no lo resuelve, los puntos irán al grupo 
proponente.
4) Gramáticas Formales
• El siguiente bloque presentará el concepto de gramática formal, siempre a un nivel básico. 
Básicamente se introducirán los conceptos de Vocabulario y Reglas de Derivación o Producción. Se 
verá cómo las Expresiones Regulares (y vinculados con ellas los Autómatas Finitos) constituyen el 
primer nivel de las gramáticas formales. En el Anexo 3 aparecen los conceptos teóricos de referencia.
• Ejemplo 4: Comenzaremos introduciendo dos ejemplos, uno con motivación más lingüística y otro 
más matemático. Uno básico de las estructuras sintácticas del castellano para formar una frase como 
"El niño come patatas", y otro para formar expresiones aritméticas básicas como "1+2*3". En 
definitiva nos centraremos en las gramáticas libres de contexto.
• Reto 4: Gramática anbn
◦ Intentar definir un autómata para la expresión anbn. ¿Se puede? Razona la respuesta. Construye 
una gramática libre de contexto para dicho lenguaje.
 -------- pié de página
 ESTALMAT -Andalucía Actividades 13/14 
_______________________________________________________________________________________
• Los lenguajes y las matemáticas:
◦ Las matemáticas se expresan a partir de fórmulas, pero ¿son todas las fórmulas correctas? 
◦ Aparecen las nociones de:
▪ Cadena de caracteres
▪ Fórmula bien formada
▪ Teorema
◦ ¿Dónde están los límites?
◦ Estudia las siguientes fórmulas:
▪ area = altura * anchura
▪ diametro = 3,14 * (r ^ 2)
▪ altura - * 5 6 = diametro
▪ r + 1 = r - 1
5) Conclusiones
• Una vez hecho este recorrido nos planteamos recuperar las nociones vistas al principio. 
◦ ¿Qué es un lenguaje?
◦ ¿Qué es una gramática?
◦ ¿Qué relaciones hay entre los lenguajes y las matemáticas?
 -------- pié de página
 ESTALMAT -Andalucía Actividades 13/14 
_______________________________________________________________________________________
Anexo 1: Autómata finito
Definición formal
Formalmente, un autómata finito es una 5-tupla (Q, Σ, q0, δ, F) donde:
• es un conjunto finito de estados;
• es un alfabeto finito;
• es el estado inicial;
• es una función de transición;
• es un conjunto de estados finales o de aceptación.
•
Representación como diagramas de estados
 
 
Este autómata finito está definido sobre el alfabeto Σ={0,1}, posee dos estados s1 y s2, y 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.
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 representancomo 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 q0 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.
Representación como tabla de transiciones
Otra manera de describir el funcionamiento de un autómata finito es mediante el uso de tablas de 
transiciones o matrices de estados. Dos posibles tablas para el ejemplo de la imagen anterior 
podrían ser las siguientes:
salida
q Q∈
símbolo
σ Σ∈
llegada
δ(q,σ) Q∈
s1 0 s2
s1 1 s1
s2 0 s1
 -------- pié de página
http://es.wikipedia.org/wiki/Tupla
http://es.wikipedia.org/wiki/Grafo_dirigido
http://es.wikipedia.org/wiki/Arista_(teor%C3%ADa_de_grafos)
http://es.wikipedia.org/wiki/V%C3%A9rtice_(teor%C3%ADa_de_grafos)
http://es.wikipedia.org/wiki/Grafo
http://es.wikipedia.org/wiki/Tabla_de_transici%C3%B3n_de_estados
http://es.wikipedia.org/wiki/Estado_(inform%C3%A1tica)
http://es.wikipedia.org/wiki/Alfabeto
http://es.wikipedia.org/wiki/Tabla_de_transici%C3%B3n_de_estados
http://es.wikipedia.org/wiki/Alfabeto
http://es.wikipedia.org/wiki/Estado_(inform%C3%A1tica)
 ESTALMAT -Andalucía Actividades 13/14 
_______________________________________________________________________________________
s2 1 s2
0 1
→*s1 s2 s1
s2 s1 s2
La primera representa explícitamente los parámetros y el valor que toma cada ocurrencia de la función 
de transición. La segunda es más compacta, y marca con una flecha el estado inicial, y con un asterisco 
los estados finales.
Funcionamiento
 
 
El esquema general es el de una cinta lectora que avanza sólo hacia delante y de a una celda, según la función de 
transición.
En el comienzo del proceso de reconocimiento de una cadena de entrada, el autómata finito se 
encuentra en el estado inicial y a medida que procesa cada símbolo de la cadena va cambiando de 
estado de acuerdo a lo determinado por lafunción de transición. Cuando se ha procesado el último de 
los símbolos de la cadena de entrada, el autómata se detiene en el estado final del proceso. Si el 
estado final en el que se detuvo es un estado de aceptación, entonces la cadena pertenece al lenguaje 
reconocido por el autómata; en caso contrario, la cadena no pertenece a dicho lenguaje.
Note que el estado inicial de un autómata finito siempre es único, en tanto que los estados finales 
pueden ser más de uno, es decir, el conjunto puede contener más de un elemento. También puede 
darse el caso de que un estado final corresponda al mismo estado inicial.
 -------- pié de página
http://es.wikipedia.org/wiki/Entrada
http://es.wikipedia.org/wiki/Cadena_de_caracteres
http://es.wikipedia.org/wiki/Tabla_de_transici%C3%B3n_de_estados
http://es.wikipedia.org/wiki/Tabla_de_transici%C3%B3n_de_estados
 ESTALMAT -Andalucía Actividades 13/14 
_______________________________________________________________________________________
Anexo 2: Expresiones regulares
Las expresiones regulares se construyen utilizando los operadores unión, concatenación y clausura de 
Kleene. Además cada expresión regular tiene un autómata finito asociado....
Alternación
Una barra vertical separa las alternativas. Por ejemplo, "marrón|castaño" se corresponde 
con marrón o castaño.
Cuantificación
Un cuantificador tras un carácter especifica la frecuencia con la que éste puede ocurrir. Los 
cuantificadores más comunes son +, ? y *:
+
El signo más indica que el carácter que le precede debe aparecer al menos una vez. Por 
ejemplo, "ho+la" describe el conjunto infinito hola, hoola, hooola, hoooola, etcétera.
?
El signo de interrogación indica que el carácter que le precede puede aparecer como mucho 
una vez. Por ejemplo, "ob?scuro" se corresponde con oscuro yobscuro.
*
El asterisco indica que el carácter que le precede puede aparecer cero, una, o más veces. 
Por ejemplo, "0*42" se corresponde con 42, 042, 0042, 00042, etcétera.
Agrupación
Los paréntesis pueden usarse para definir el ámbito y precedencia de los demás operadores. Por 
ejemplo, "(p|m)adre" es lo mismo que "padre|madre", y "(des)?amor" se corresponde con amor y 
con desamor.
 -------- pié de página
http://es.wikipedia.org/wiki/Clausura_de_Kleene
http://es.wikipedia.org/wiki/Clausura_de_Kleene
http://es.wikipedia.org/wiki/Concatenaci%C3%B3n
http://es.wikipedia.org/wiki/Uni%C3%B3n_de_conjuntos
 ESTALMAT -Andalucía Actividades 13/14 
_______________________________________________________________________________________
Anexo 3: Gramáticas Formales
Definición de una ES-gramática
En la definición clásica que dio Noam Chomsky en la década de 1950, una gramática formal de 
estructura sintagmática (ES-gramática) es una cuádrupla G = (N,T,S,P) donde:
• N es un conjunto finito de símbolos no terminales (variables).
• T es un conjunto finito de símbolos terminales (constantes), disjunto con N.
• S es un símbolo distinguido de N, el símbolo inicial.
• P es un conjunto finito de reglas de producción, cada una de la forma:
 
donde * es la clausura de Kleene. Esto es, cada regla de producción mapea de una cadena de símbolos 
a otra, donde la primera cadena contiene al menos un símbolo no terminal. En el caso de que la 
segunda cadena sea la cadena vacía, para evitar confusión se la denota con una notación especial 
(usualmente , o ).
El alfabeto de la gramática es entonces el conjunto 
Derivaciones
Sea una gramática, y sean α, β, δ, φ, ρ, ... palabras de . Entonces:
• β se deriva de α en un paso de derivación, y lo denotamos con α β si existen dos 
cadenas , y una producción δ → ρ tales que α = δ , y β = ρ 
• Notamos con al cierre reflexivo y transitivo de . Es decir α β denota a una 
secuencia de derivaciones en un número finito de pasos desde α hasta β.
• es una forma sentencial de , si puede obtenerse la siguiente secuencia de 
derivaciones . En el caso particular de que se dice que x es una sentencia
• Se denomina lenguaje formal generado por G al conjunto 
Jerarquía de Chomsky
Cuando Noam Chomsky formalizó la idea de las gramáticas generativas en 1956, clasificó este tipo de 
gramáticas en varios tipos de complejidad creciente que forman la llamada jerarquía de Chomsky. La 
diferencia entre estos tipos es que cada uno de ellos tiene reglas más particulares y restringidas y por 
tanto generan una lenguajes formales menos generales. Dos tipos importante son las gramáticas libres 
de contexto (Tipo 2) y las gramáticas regulares (Tipo 3). Las lenguas que pueden ser descritas 
mediante esos tipos de gramáticas son lenguas libres de contexto y lenguas regulares, 
respectivamente. Estos dos tipos son mucho menos generales que las gramáticas no restringidas de 
Tipo 0 (es decir, que pueden ser procesadas o reconocidas mediante máquinas de Turing). Estos dos 
tipos de gramáticas se usan más frecuentemente puesto que los analizadores sintácticos para estos 
lenguajes pueden implementarse de manera eficiente.1 Por ejemplo, todas las lenguas regulares 
pueden ser reconocidas por un autómata finito. Para subconjuntos de gramáticas libres de contexto, 
existen algoritmos para generar analizadores sintácticos LL y analizadores sintácticos LR eficientes, que 
permiten reconocer los correspondientes lenguajes generados por esas gramáticas.
 -------- pié de página
http://es.wikipedia.org/wiki/Analizador_sint%C3%A1ctico_LR
http://es.wikipedia.org/wiki/Analizador_sint%C3%A1ctico_LL
http://es.wikipedia.org/wiki/Aut%C3%B3mata_finito
http://es.wikipedia.org/wiki/Gram%C3%A1tica_formal#cite_note-Grune.26Jacobs1990-1
http://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing
http://es.wikipedia.org/wiki/Lenguaje_regular
http://es.wikipedia.org/w/index.php?title=Lenguaje_libre_de_contexto&action=edit&redlink=1http://es.wikipedia.org/wiki/Gram%C3%A1tica_regular
http://es.wikipedia.org/wiki/Gram%C3%A1tica_libre_de_contexto
http://es.wikipedia.org/wiki/Gram%C3%A1tica_libre_de_contexto
http://es.wikipedia.org/wiki/Jerarqu%C3%ADa_de_Chomsky
http://es.wikipedia.org/wiki/Gram%C3%A1tica_generativa
http://es.wikipedia.org/wiki/Noam_Chomsky
http://es.wikipedia.org/wiki/Cadena_vac%C3%ADa
http://es.wikipedia.org/wiki/Clausura_de_Kleene
http://es.wikipedia.org/wiki/Conjuntos_disjuntos
http://es.wikipedia.org/wiki/Tupla
http://es.wikipedia.org/wiki/Noam_Chomsky
	1) Motivación
	2) Autómatas de estados finitos
	3) Expresiones Regulares
	4) Gramáticas Formales
	5) Conclusiones
	Anexo 1: Autómata finito
	Definición formal
	Representación como diagramas de estados
	Representación como tabla de transiciones
	Funcionamiento
	Anexo 2: Expresiones regulares
	Anexo 3: Gramáticas Formales
	Definición de una ES-gramática
	Derivaciones
	Jerarquía de Chomsky