hola

Lenguajes Formales y Autómatas

Ing. Lucila Patricia
ArellanoMendoza
2014

OBJETIVO
Proporcionar al alumno la teoría para el
diseño de lenguajes, así como los aspectos
formales de la teoría de lenguajes.

Conjunto: Es una colección de caracteres,
elementos o símbolos.
Operaciones con conjuntos:
Unión AUB = {x/x  A o x  B}
Intersección AB = { x/x  A y x  B}
Diferencia A-B ={x/x  A y x  B}

Conjunto Potencia
2A = {B/ B  A} conjunto formado por todos
los subconjuntos de A
Producto Cartesiano

AxB = {(a,b) / a  A y b  B}

Símbolos







Letras (a, b, c, ..,z)
Dígitos (0..9)
Caracteres (+,-,*,/,?,..)
Letras o caracteres (las palabras reservadas
de un lenguaje de programación)
Ejemplos: a, #,1,+,then, else

Alfabeto: Es un conjuntofinito no vacío de
símbolos.
Ejemplos:
 Alfabeto español
 {a,b,...,z}
 {a,b} alfabeto que contiene sólo 2 símbolos
Usualmente utilizaremos el símbolo  para
representar a un alfabeto.

Cadena, cuerda o string: Concatenación o
yuxtaposición de elementos o símbolos de un
determinado alfabeto. La representaremos
como w.

Palabra: Una palabra es una cadena finita
de símbolos.Dado un alfabeto  y un número natural n,
Una secuencia de símbolos a1a2...an es una
Palabra sobre el alfabeto  de largo n si y
sólo si para cada i=1,2,...,n, ai  .

Longitud de una Palabra: Dado un alfabeto
 y una cadena x= a1a2...an sobre , x
(módulo de x) denota la longitud de x, esto
es: a1a2...an = n.
Ejemplo:

Dado el alfabeto  = {a,b} y la palabra x=aab,
entonces x=3.Cadena vacía
Es una cadena que no tiene símbolos y se
denota con 
Su longitud es  = 0, pues  tiene cero
símbolos.



Concatenación

Dados x= a1a2...an y z= b1b2...bm ,
xz = a1a2...anb1b2...bm
xz= x+z= n + m
x= x = x
( es el elemento identidad en la
concatenación)



Potencia

Sea w una palabra, n  IN, se define
wn =

,

si n=0

wwn-1, si n > 0Ejemplo: Si w
w0 =
w1 =
w2 =
w3 =

= aba   = {a,b}

aba
abaaba
abaabaaba



Igualdad entre Cadenas

Dadas 2 palabras w y z  , se dice que
son iguales si tienen la misma longitud y los
mismos símbolos en la misma posición.
Formalmente:
Dadas las palabras w= a1a2...an y
z= b1b2...bm  , se dice que
w = z si y sólo si n = m y ai = bi para cada
i=1,2,...,n.Lenguaje: Un lenguaje es un conjunto de
palabras formadas a partir de un alfabeto.
Ejemplo:
 L = {1, 12, 1234, 14, 13} , es un lenguaje
sobre el alfabeto  = {0,1,2, ..., 9}


Si  es un alfabeto, también es un lenguaje,
el formado por todas las cadenas con un
único símbolo.





Dado que un lenguaje es un conjunto de
cadenas, se puede tener el lenguaje
compuesto por ninguna cadena,el lenguaje
vacío, y que se denota por .
Éste no es el mismo lenguaje que el que
consta sólo de la cadena vacía, {}.

Concatenación
AB = { wx  w  A y x  B}
Esto es, L esta formado por todas las
cadenas que se forman concatenando cada
cadena de A con todas las cadenas de B.

Ejemplo:

Si A = {ab} y B = {cd, ef}, entonces
L = AB = {abcd, abef}
Si A es un lenguaje sobre 1 y Bes un
lenguaje sobre 2, entonces L = AB será
un lenguaje sobre 1  2

Lenguaje potencia, está dado por:
{}, si n = 0
An =
AAn-1, si n > 0

Ejemplo:
Si A = {ab} sobre el alfabeto, entonces se
tiene que:
A0 =
A1 =
A2 =
A3 =
.......

{}
A = {ab}
AA1 = {abab}
AA2 = {ababab}

La unión e intersección

A  B = {x  x  A o x  B}

(Unión)

A  B = {x  x  A y x B}(Intersección)

Ejemplos:
Considerando el alfabeto ={0,1} y los
lenguajes
A={,0,1,011,11010} y B={0,1,101,111}
A  B ={,0,1,011,11010, 101,111}

A  B={ 0,1}

Sublenguaje
Si A y B son lenguajes sobre un alfabeto  y
si todas las cadenas de A son también
cadenas de B, entonces se dice que A es un
sublenguaje de B.
AB

Ejemplo:

AB
A={a, aa, aaa, aaaa} y B={an |...