Upload
lourdesnbv
View
9
Download
0
Embed Size (px)
Citation preview
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.