Hasbro

APUNTES DE
TEORÍA DE AUTÓMATAS











CATEDRÁTICA: LIC. PATRICIA MARTÍNEZ MORENO, M.A.







APUNTES DE
TEORIA DE AUTÓMATAS


INTRODUCCION A LOS ASPECTOS TEÓRICOS DE CIENCIAS COMPUTACIONALES AUTÓMATAS Y LENGUAJES FORMALES.

Alfabetos y lenguajes

Símbolo o caracter: Unidad mínima en un lenguaje.
Alfabeto: Conjunto no vacío y finito de símbolos, ejemplo elalfabeto binario { 0 , 1 }. Denotaremos al alfabeto por el símbolo Σ.
Cadena o palabra: Secuencia finita de símbolos de un determinado alfabeto, ejemplo { 001, 01, 111 } en el alfabeto binario.
Cadena vacía: Se denota por el símbolo ε, y es una palabra bajo cualquier alfabeto.
Lenguaje: Conjunto de palabras escritas sobre un alfabeto específico, ejemplo { aaa, abba, bbbaaa} es un lenguaje sobre Σ = { a, b }.
Si Σ es un alfabeto, también es un lenguaje. (El formado por todas las cadenas con un único símbolo.)

Lenguaje vacío: Es el que está compuesto por ninguna cadena y se denota como ( que es diferente al lenguaje que contiene la cadena vacía. ( = {} y ( ( { ε }

Si Σ es un alfabeto y w es una cadena sobre Σ. Si L es un lenguaje formado por algunasde las cadenas sobre Σ y si w está en L, entonces se dice que w es un elemento de L. Esto es w ( L.

El lenguaje universal sobre Σ se conoce como cerradura de Σ y se denota por: Σ* donde * va a significar 0 o más.

Σ1 = { a, b}
Σ0={ ε }
Σ*= Σ0 ( Σ1 ( Σ2...... = { ε ,a,b,aa,ab,ba,bb,...}


Operaciones con cadenas


Longitud de cadena: Si w es una cadena su longitudse denota como: |w| y es la cantidad de símbolos que contiene la cadena.

| ε |=0 | b |=1 | aa |=2
para w ( Σ* | w | >=0

Concatenación de Cadenas: Se denota por wz o w ( z para las cadenas w y z, el resultado es añadir la cadena z a la cadena w.

w = aa, z = bba
wz = aabba


ε es laidentidad para la concatenación.



Potencia de una Cadena: Si w es una cadena, para n que pertenece a los Naturales se define:

ε para n = 0 ó
wn =
w ( wn-1 para n >=1



Igualdad de cadenas: Si w y z son cadenas se dice que w es igual a z si tienen la misma longitud y los mismos símbolos en la misma posición y se denota mediante w = z.Sufijo y Prefijo de Cadenas sobre un alfabeto.
Si w y x son cadenas se dice que x es prefijo de w si para alguna cadena y se obtiene que w = xy. Si y = ε entonces para w = xy se tiene que w = x, con lo que toda cadena puede considerarse prefijo de sí misma. ε Es prefijo de cualquier cadena. (Lo mismo para sufijo.)


Prefijo Propio: Cadenas que son prefijo de una palabra pero noiguales a la misma (lo mismo para Sufijo Propio.)


Subcadena: w es una subcadena de z si existen las cadenas x e y para las que z = xwy.






Inversa o Traspuesta de w: Es la imagen refleja de w y se denota por: wI donde

w, si w = ε, ó
wI =
yI a, si w = ay, para a que pertenece al alfabeto e y que pertenece a Σ*.

La inversa se deshace así misma, esto es, ( xI) I = x.





Operaciones con Lenguajes



Sean A y B lenguajes sobre un alfabeto.

La concatenación de A y B es (A ( B)
Es A ( B = {w ( x | w ( A y x ( B}

Si A es un lenguaje sobre Σ1 y B es un lenguaje sobre Σ2, entonces la concatenación A ( B es un lenguaje sobre Σ1 ( Σ2.

La identidad para la concatenación de un lenguaje es el lenguaje quecontiene a la cadena vacía. Esto es, A ( { ε } = { ε } ( A = A


Potencia sobre Lenguajes: Sea A un lenguaje sobre Σ definamos


{ ε } para n = 0 ó
An =
A ( An-1 para n >=1



Si A= (, A0 = (0 = {ε}

La Unión: Si A y B son lenguajes sobre Σ, entonces
A ( B ={x | x ( A ó x ( B}

La intersección: A ( B ={x...