Republica Bolivariana de VenezuelaMinisterio del Poder Popular para la Educación

Decanato de IngenieríaUniversidad Fermín ToroCabudare – Edo Lara

Presentado por:Lourdes Barrios C.I. 19.954.486Automatas y Lenguajes Formales

AUTOMATAS

Y LENGUAJES

FORMALES

Símbolos: Es un entidad abstracta que nodefinimos formalmente, puede ser uncarácter o un conjunto de caracteres1.2 ; P.F ; *.@ ; etc.

Cadena: Representa una secuencia finita desímbolos.W3: “222213”

Longitud de Cadena: si w es una cadenasobre cualquier alfabeto, la longitud de westa formada por la cantidad de símbolos quela conformen

Es una cadena que no contiene símbolos,es decir dicha cadena esta constituida por(0) denotada por “λ” y “ε”

Dada una cadena vacía “ε” de dichacadena denotada por |ε| = 0

CADENA VACIAEs una expresión que describe un

conjunto de cadenas sin enumerar suselementos

Específicamente, las expresionesregulares se construyen utilizando losoperadores unión, concatenación y clausura de Kleene. Además cadaexpresión regular tiene un autómata

EX

PR

ESIO

NES

REG

ULA

RES

Tres expresiones regulares posibles:ε,∅,ar =ε.Construimos el siguiente autómata M = ({q 0,q F },Σ, {δ(q 0,ε} =q F },q 0 {q F })

Claramente,M cumple las condiciones impuestas y ademásL(M ) =L(r )

TEOREMA DE KLEENE

FORMALES

Concatenación: sean w1 y w2 dos cadenasrespectivamente, la concatenación de w1 y w2es la cadena que se obtiene al añadir a lacadena w1 la palabra w2 y se denota w1w2

EJEMPLO: sea w1=“pana” y w2= “dero” laconcatenación de w1 con w2 es la cadena dew1w2=w1w2=“panadero”

POTENCIA

La potencia i-esima para una palabra dada“w” corresponde a la concatenación “i” veces dela palabra “w” con ella misma

EJEMPLO: sea w “abc”, una cadena entonces:WO= ε ; W1=abc ; W3= abcabc ; W4=abcabcabc

Asi sucesivamente se dice que wi es lapotencia i-ésima de W

Sea la palabra w=X1,X2…Xn se tiene que lacadena inversa de W denotada por: Wi sedenota invirtiendo el orden de los símbolos enla palabra w,wl=Xn,X2,X1…..

EJEMPLO: Sean los símbolos {1,2,3} {a,b,c}dos cadenas asociadas a los conjuntos desímbolos dados serias W1=122 W2=abca;respectivamente para las cadenas W1 y W2

REFLEX

ION

LENGUAJES

REGULARES

Los lenguajes más sencillos que seconsiderarán son los lenguajes regulares, esdecir, los que se pueden generar a partir de loslenguajes básicos, con la aplicación de lasoperaciones de unión, concatenación y * deKleene un número finito de veces.

Es un modelocomputacional querealiza cómputos enforma automáticasobreuna entrada paraproducir una salida.

Es un modelocomputacional querealiza cómputosen formaautomática sobreuna entrada paraproduciruna salida.

AFN

D

expresión regular tiene un autómatafinito asociado.