Proyecto
Páginas: 4 (960 palabras)
Publicado: 7 de mayo de 2012
&216758&&,Ï1 '( $() $ 3$57,5 '( (;35(6,21(6 5(*8/$5(6
Con anterioridad se ha mostrado la equivalencia computacional de los modelos AEFD, AEF y AEF-λ; esto quiere decir que para cada autómata deuno de estos tres modelos se pueden construir autómatas equivalentes en los otros modelos. Por lo tanto, los modelos enunciados aceptan exactamente los mismos lenguajes. Por otra parte, se demostró quepor cada AEF M uno puede construir una gramática lineal por derecha G tal que L(G) = L(M) y viceversa, y también que a partir de una gramática lineal por derecha (o por izquierda), uno siempre puedeconstruir una gramática lineal por izquierda (o por derecha) que genere el mismo lenguaje. Asimismo, se vio que a partir de un AEF M, a través del planteo y solución del sistema de ecuaciones linealesde conjuntos asociado a M, se puede encontrar una expresión regular γ tal que L(M) = γ. En definitiva, para completar las afirmaciones relativas a Lenguajes Regulares que se plantearon al inicio de launidad resta establecer un mecanismo que permita relacionar los lenguajes representados por las expresiones regulares con los aceptados por los autómatas finitos. Aún cuando por varios ejemplos hemosvisto que lenguajes descriptos por expresiones regulares son aceptados por autómatas finitos, no hemos probado que para cualquier expresión regular exista un autómata finito equivalente. Esto seestablece en el siguiente teorema:
7HRUHPD
Dada una expresión regular γ sobre un alfabeto finito V, se puede construir un AEF-λ M tal que el lenguaje aceptado por M sea exactamente el lenguajerepresentado por γ, es decir L(M) = γ.
'HPRVWUDFLyQ Puesto que la definición de las expresiones regulares se hace recursivamente, la demostración se lleva a cabo por inducción estructural sobre γ.
Siγ = ∅, el autómata correspondiente es:
o bien Si γ = λ, el autómata correspondiente es:
o bien Si γ = D, con D ∈ V, el autómata correspondiente es:
Si γ = α ∪ β, con α y β dos expresiones...
Con anterioridad se ha mostrado la equivalencia computacional de los modelos AEFD, AEF y AEF-λ; esto quiere decir que para cada autómata deuno de estos tres modelos se pueden construir autómatas equivalentes en los otros modelos. Por lo tanto, los modelos enunciados aceptan exactamente los mismos lenguajes. Por otra parte, se demostró quepor cada AEF M uno puede construir una gramática lineal por derecha G tal que L(G) = L(M) y viceversa, y también que a partir de una gramática lineal por derecha (o por izquierda), uno siempre puedeconstruir una gramática lineal por izquierda (o por derecha) que genere el mismo lenguaje. Asimismo, se vio que a partir de un AEF M, a través del planteo y solución del sistema de ecuaciones linealesde conjuntos asociado a M, se puede encontrar una expresión regular γ tal que L(M) = γ. En definitiva, para completar las afirmaciones relativas a Lenguajes Regulares que se plantearon al inicio de launidad resta establecer un mecanismo que permita relacionar los lenguajes representados por las expresiones regulares con los aceptados por los autómatas finitos. Aún cuando por varios ejemplos hemosvisto que lenguajes descriptos por expresiones regulares son aceptados por autómatas finitos, no hemos probado que para cualquier expresión regular exista un autómata finito equivalente. Esto seestablece en el siguiente teorema:
7HRUHPD
Dada una expresión regular γ sobre un alfabeto finito V, se puede construir un AEF-λ M tal que el lenguaje aceptado por M sea exactamente el lenguajerepresentado por γ, es decir L(M) = γ.
'HPRVWUDFLyQ Puesto que la definición de las expresiones regulares se hace recursivamente, la demostración se lleva a cabo por inducción estructural sobre γ.
Siγ = ∅, el autómata correspondiente es:
o bien Si γ = λ, el autómata correspondiente es:
o bien Si γ = D, con D ∈ V, el autómata correspondiente es:
Si γ = α ∪ β, con α y β dos expresiones...
Leer documento completo
Regístrate para leer el documento completo.