Pasajes
Supuestos:
1. Que haya un unico estado final y sea distinto del inicial.
2. Que al estado inicial no vuelva flechas.
3. Que del estado final no salgan flechas.
|
Expresion Regular |
Automata Finito |
Observaciones (Esta columna no esta muy formal...., es mas diria que esta MAL) |
|
Æ |
|
§ d=Æ § V=Æ |
|
l |
|
§ d=Æ § V={q0, F} |
|
a |
|
§ d={(q0, a, F)} § V=Æ |
|
a |
|
|
|
a* |
|
§ Q=Q’È{q0,F} § d=d’ § V=V’È{(q0,q0’), (q0,F),(F’,F),(F’,q0’)}
|
|
a+=aa* |
|
§ Q=Q’È{q0,F} § d=d’ § V=V’È{(q0,q0’), (F’,F),(F’,q0’)}
|
|
a|b |
|
§ Q=Q’ÈQ’’È{q0,F} § d=d’Èd’’ § V=V’ÈV’’È{(q0,q0’),(q0,q0’’),(F’,F),(F’’,F)} |
|
ab |
|
Este mmmmmmm, me gusta mas asi que como esta en la carpeta. |
|
[a]=a|l |
|
|
Sea M = (Q, A, d, q0, F, V) un NFA deseo obtener un M’ = (Q’, A’, d’, q0’, F’) DFA equivalente.
Q’ =P(Q) = 2Q Obs: Partes de Q: El conjunto de todos los subconjuntos de Q
A’ =A
d’: Q’ x A’ ® Q’ Obs: d’(Pr, a) = Cl({qj / (qi, a, qj) Î d, qi Î Pr})
q0’ =Cl(q0) Obs: Cl(qi) = { qj / (qi, qj) Î V*} qi Î Q
F’ = {Pi Î P(Q) / Pi Ç F ¹ Æ }
§ X=aY|bY Þ X=(a|b)Y
§ X=C|l Þ X=[C]
§ X=aY|aZ Þ X=a(Y|Z)
§ X=a|bX Þ X=b*a
§ La Gramatica debe estar Sin Reglas Lexicograficas
§ Los Simbolos No Terminales son los Estados
§ Los Simbolos Terminales las Transiciones
Formalizacion:
Q=VN
A=VT
q0=S
F={RÎ VN / R®l}
Si (B,aD) Î P Þ (B,a,D) Î d
Dado M = (Q, A, d, q0, F) Automata Finito Sin Transiciones l (Puede ser No Deterministico) quiero G = (VT, VN, P, S) que genere el mismo lenguaje.
Formalizacion:
VT=A
VN=Q
S=q0
P={
§ si (qi,a,qj) Î d Þ qi®aqj en P.
§ si qi Î F Þ qi®l
}
Clausura en Lenguajes Regulares
Si L1 y L2 son Lenguajes Regulares Þ L1ÈL2 es Lenguaje Regular.
Demostraciones:
Por Automatas Finitos:
§ Utilizas a|b
§ Conociendo los AFD de L1 y L2 (hay un metodo parecido al de la interseccion)
Por Gramaticas:
Si L1 y L2 son Lenguajes Regulares Þ L1^L2 es Lenguaje Regular (utilizar ab)
Si L es Lenguaje Regular Þ L* es Lenguaje Regular (utilizar a*)
Si L es Lenguaje Regular Þ L+ es Lenguaje Regular (utilizar a+)
Si L es Lenguaje Regular Þ LÈ{l} es Lenguaje Regular (utilizar [a])
Si L es Lenguaje Regular Þ LR es Lenguaje Regular (El reverso)
Si L es Lenguaje Regular Þ ~L es Lenguaje Regular (~L=A*-L)
o Tomo Automata Completo con Estados Trampa.
o Invierto los Estados de Aceptacion/Rechazo
Si L1 y L2 son Lenguajes Regulares Þ L1ÇL2 es un Lenguaje Regular.
o ~~L1ÇL2=~(~L1È~L2)
o Conociendo los AFD de L1 y L2:
§ M1 = (Q1, A1, d1, q0, F1)
§ M2 = (Q2, A2, d2, p0, F2)
§ L1ÇL2: M3 = (Q3, A3, d3, {q0,p0}, F2)
o Q3=Q1xQ2
o A3=A1ÈA2
o F3=F1xF2
o d3((qi,pj),a)=(d1(qi,a), d2(pj,a))
Si L1 y L2 son Lenguajes Libres de Contexto Þ L1ÈL2 es un Lenguaje Libre de Contexto
Demostraciones:
Por Automatas Finitos:
§ Utilizas a|b
§ Conociendo los AFD de L1 y L2 (hay un metodo parecido al de la interseccion)
Por Gramaticas:
Si L1 y L2 son Lenguajes Libres de Contexto Þ L1^L2 es Lenguaje Libre de Contexto
Si L es un Lenguaje Libre de Contexto Þ L* es un Lenguaje Libre de Contexto
Si L es un Lenguaje Libre de Contexto Þ L+ es un Lenguaje Libre de Contexto
Si L es un Lenguaje Libre de Contexto Þ LÈ{l} es un Lenguaje Libre de Contexto
Si L es un Lenguaje Libre de Contexto Þ LR es un Lenguaje Libre de Contexto
Si L es un Lenguaje Libre de Contexto NO IMPLICA ~L es un Lenguaje Libre de Contexto
§ Demuestro usando Interseccion + De Morgan + Pumping Lemma CFL
Si L1 y L2 es un Lenguaje Libre de Contexto NO IMPLICA L1ÇL2 es un CFL
§ Demuestro usando Pumping Lemma con la interseccion de dos L1 y L2 Libres de Contexto.
