Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Introducción a la Teoría de Lenguajes Formales.

Lenguajes y autómatas Unidad 1
by

Lucero Zamora

on 8 February 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Introducción a la Teoría de Lenguajes Formales.

Alfabeto Palabras Lenguajes Gramáticas Results Operaciones con palabras Concatenación Se llama alfabeto a un conjunto finito, no vacío, cuyos elementos se denominan “letras” o “símbolos”. Se denomina palabra a toda secuencia finita de letras formada con los símbolos de un alfabeto Introducción a la Teoría de Lenguajes Formales. Operaciones Una gramática para estructura de expresiones
G = ( V , S , vo ,|-> )
Donde:
V= Conjunto finito
S= Subconjunto de V
vo E V - S
|->= Relación finita en V* Ing. Lucero Zamora M. Ejemplos: Se definen los alfabetos por la enumeración de los símbolos que contiene. –A1={A, B, C, D, E, F , G, ..., Z}
–A2={0,1}
–A3={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
–A4={(, )} Ejemplos:
A1: LUIS, DANIELA, ANA
A2: 10000011
A3: 2013 Se usarán letras minúsculas para representar las palabras de un alfabeto:
x = JOSE(sobre A1)
y = (()) (sobre A4)
z = 123456(sobre A3) La longitud de una palabra es el número de símbolos (letras) que la componen:
Ejemplo: | x | = 4 | y | = 4 | z | = 6 Se define la palabra vacía como aquella cuya longitud es cero.
Se representa mediante la letra lambda minúscula Se define “universo del discurso” o “lenguaje universal”, al conjunto de palabras que se pueden formar con las letras de un alfabeto, W( ) es un conjunto infinito. Ejemplo:
Un alfabeto con el menor número posible de letras (1).
–A = { a }
–En este caso, W(A) = { , a, aa, aaa, aaaa, ...}, y contiene un número infinito de elementos. NOTA: La palabra vacía pertenece a todos los lenguajes universales de todos los alfabetos posibles. Supongamos que
x=A0,A1...... Ai
|x| = i
y= B0,B1...... Bj
|y| = j Se llama concatenación de las palabras x e y a otra palabra, llamada z, se obtiene poniendo las letras de x y a continuación las de y:
z= A0,A1...... Ai,B0,B1...... Bj
Se cumple que:|z|=|x|+|y| Propiedades Operación cerrada. Es decir, la concatenación de dos palabras de W(A) es otra palabra de W(A). Si x W(A) e y W(A), entonces xyW(A). Propiedad asociativa: x(yz)=(xy)z Existencia de elemento neutro. El elemento neutro de una operación es la palabra vacía , tanto por la derecha como por la izquierda. Siendo x una palabra cualquiera, se cumple:
x^ = ^x = x Potencia Se denomina potencia i-ésima de una palabra
a la concatenación consigo misma i veces.
xi= xxx...xx
|----------------|
i se deben cumplir las siguientes relaciones
xi+1= xix = xxi (i > 0)
xixj= xi+j (i, j > 0) Potencia Potencia Potencia Potencia Para que ambas relaciones se cumplan también para i, j = 0,
basta con definir x0 = , cualquiera que sea x. Potencia Ejemplo:
x = ABCD, entonces
x2= xx = ABCDABCD
x3= xxx = ABCDABCDABCD
–la longitud de la potencia es |xi| = i *|x| Potencia Potencia Reflexión Sea x=A0A1...... An ,
se denomina palabra refleja o inversa de x, representado por x-1,
x-1= x=AnAn-1...... A0
esta palabra está formada por las mismas letras, pero ordenadas de forma inversa. Potencia Potencia Potencia ^ Se denomina lenguaje a un conjunto de palabras de un determinado alfabeto. un lenguaje es un conjunto de cadenas de símbolos (palabras, oraciones, textos o frases). Unión Concatenación Potencia Clausura positiva Cierre Reflexión Consideremos dos lenguajes diferentes definidos sobre el mismo alfabeto L1 W( ) y L2 W( )
Se denomina unión de ambos lenguajes al lenguaje formado por las palabras de ambos lenguajes :
L1 u L2= {x | x . L1 ó x . L2} Propiedades Operación cerrada. La unión de dos lenguajes definidos sobre el mismo alfabeto será otro lenguaje definido sobre ese alfabeto Propiedad asociativa: (L1 u L2) u L3 = L1 u (L2 u L3) Existencia de elemento neutro. El elemento neutro de un lenguaje es el lenguaje vacío , tanto por la derecha como por la izquierda. Siendo L un lenguaje cualquiera, se cumple:
L u ^ = ^ u L = L Propiedad conmutativa: Se verifica que L1 u L2 = L2 u L1 Propiedad de idempotencia Se verifica que L u L = L Consideremos dos lenguajes definidos sobre el mismo alfabeto, L1 y L2. La concatenación o producto de estos lenguajes es el lenguaje
L1L2 = {xy/xL1yxL2}
Las palabras de este lenguaje estarán formadas al concatenar cada una palabra del primero de los lenguajes con otra del segundo. La concatenación de lenguajes con el lenguaje vacío es:
.L = L. = . Propiedades Operación cerrada. La concatenación de lenguajes sobre el mismo alfabeto es otro lenguaje sobre ese alfabeto. Propiedad asociativa: (L1 L2) L3 = L1 (L2 L3) Existencia de elemento neutro. Cualquiera que sea el lenguaje considerado, el lenguaje de la palabra vacía cumple que
{ }L = L{ } = L Se define la potencia i-ésima de un lenguaje a la operación de concatenarlo consigo mismo i veces.
Li= LLL....L
|------------|
i Se cumplen las siguientes relaciones
–Li+1= LiL = LLi(i > 0)
–Li Lj= Li+j (i, j > 0) Para que las relaciones se cumplan para i, j = 0, se define
–L0 = { }, cualquiera que sea L Se define la clausura positiva de un lenguaje L:
L+= u Li
i=1 8 Lenguaje obtenido uniendo el lenguaje con todas sus potencias posibles excepto L0. Si L no contiene la palabra vacía, la clausura positiva tampoco. Ya que cualquier alfabeto es un lenguaje sobre él mismo (formado por las palabras de longitud 1), al aplicarle esta operación se observa que
.+ = W( ) -{ } Se define el cierre o clausura de un lenguaje L como:

L* = u Li
i=0
Lenguaje obtenido uniendo el lenguaje con todas sus potencias posibles, incluso L0. Todas las clausuras contienen la palabra vacía. 8 Se cumplen las siguientes relaciones:
–L* = L+ u { }
–L+= L L* = L* L(será imposible obtener la palabra vacía) Se llama lenguaje reflejo o inverso de L, representándose por L-1 Potencia Diferencia L1 - L2 = {w | w E L1 pero w E L2} Sea x=A0A1...... An ,
se denomina palabra refleja o inversa de x, representado por x-1,
Ejemplo:
x-1= x=AnAn-1...... A0 S es el conjunto de todas las "palabras" permitidas en el lenguaje V consta de S además de algunos otros símbolos La relación |-> sobre V* especifica los reemplazos permisibles, en el sentido de que, si W |-> W' se puede reemplazar W con W', siempre que aparezca la cadena W, ya sea sola o como subcadena de alguna otra cadena La proposición w |-> W' se llama producción de G.
Entonces W y W' son lados izquierdos y derechos de la producción, respectivamente Ejemplo:
Sea
S = {Juan, Julia, maneja, corre, descuidadamente, rápido, frecuentemente),
N = {oración, sujeto, predicado, verbo, adverbio) y sea V=S U N.
Sea vo =oración,
y supóngase que la relación |-> en V* queda descrita enumerando todas las producciones como sigue:
Oración |-> sujeto predicado
Sujeto |-> Juan
sujeto |-> Julia
predicado |-> verbo adverbio
verbo |-> maneja
verbo |-> corre
adverbio |-> descuidadamente
adverbio |-> rápido
adverbio |-> frecuentemente El conjunto S contiene todas las palabras permitidas en el lenguaje; N consta de las palabras que describen partes de la oración, pero que en realidad no están contenidas en el lenguaje. Se afirma que la oración “Julia maneja frecuentemente”, que será denotada por w, es una oración permisible o con sintaxis correcta, de acuerdo con las reglas de este lenguaje.
Para demostrar esto, considérese la siguiente serie de cadenas en V*. Oración.
sujeto predicado
Julia predicado
Julia verbo adverbio
Julia maneja adverbio
Julia maneja frecuentemente En las gramáticas para la estructura de oraciones, la búsqueda de una sintaxis correcta se refiere sólo al proceso mediante el cual al formar una oración se procura que ésta sea correcta gramaticalmente hablando, y nada
más. Diagrama de sintaxis Un segundo método para desplegar las producciones de ciertas gramáticas de tipo 2 es el diagrama de sintaxis. Permite ver al usuario como un movimiento a través de diagramas Árbol de deducción Oración Sujeto Predicado a) Oración Sujeto Predicado Julia b) Oración Sujeto Predicado Julia Verbo Adverbio c) Oración Sujeto Predicado Julia Verbo Adverbio Maneja d) Oración Sujeto Predicado Julia Verbo Adverbio Maneja Frecuentemente e) Tipo 0 si no se establecen restricciones sobre las producciones de G. Tipo 1 si para cualquier producción 1 2 w1 |-> w2, la longitud de w1 es menor o igual que la longitud
de w2 (donde la longitud de la cadena es el número de palabras en la cadena). Tipo 2 si el lado izquierdo de cada producción es un único símbolo no terminal y el lado derecho
consta de uno o mas símbolos. Tipo 3 si el lado izquierdo de cada producción es un único símbolo no terminal y el lado derecho
tiene uno o mas símbolos, incluyendo a lo mas un símbolo no terminal, que debe estar en el
extremo derecho de la cadena.
Full transcript