| Revisión actual |
Tu texto |
| Línea 43: |
Línea 43: |
|
| |
|
| ==Ejercicio 03== | | ==Ejercicio 03== |
|
| |
| ''Construir autómatas finitos para los siguientes lenguajes:''
| |
|
| |
| *g) ''Cadenas que contengan 3 ceros consecutivos. ∑ = {0,1}.''
| |
|
| |
| [[Imagen:P1E3G.png]]
| |
| <!-- http://graph.gafol.net/create
| |
| rankdir=LR;
| |
| size="8.5";
| |
|
| |
| node [fontname=Arial,fontsize=12];
| |
| node [width=0.6,height=0.6,fixedsize=true];
| |
| edge [fontname=Arial,fontsize=10];
| |
| edge [arrowhead=vee,arrowsize=0.70];
| |
|
| |
| start [style=invisible];
| |
| node [shape = doublecircle]; q3;
| |
| node [shape = circle];
| |
|
| |
| start -> q0;
| |
| q0 -> q0 [label="1"];
| |
| q0 -> q1 [label="0"];
| |
| q1 -> q0 [label="1"];
| |
| q1 -> q2 [label="0"];
| |
| q2 -> q0 [label="1"];
| |
| q2 -> q3 [label="0"];
| |
| q3 -> q3 [label="0|1"];
| |
| -->
| |
|
| |
| *h) ''Cadenas que no contengan dos unos consecutivos. ∑ = {0,1}.''
| |
|
| |
| [[Imagen:P1E3H.png]]
| |
| <!-- http://graph.gafol.net/create
| |
| rankdir=LR;
| |
| size="8.5";
| |
|
| |
| node [fontname=Arial,fontsize=12];
| |
| node [width=0.6,height=0.6,fixedsize=true];
| |
| edge [fontname=Arial,fontsize=10];
| |
| edge [arrowhead=vee,arrowsize=0.70];
| |
|
| |
| start [style=invisible];
| |
| node [shape = doublecircle]; q0 q1;
| |
| node [shape = circle];
| |
|
| |
| start -> q0;
| |
| q0 -> q0 [label="0"];
| |
| q0 -> q1 [label="1"];
| |
| q1 -> q0 [label="0"];
| |
| -->
| |
|
| |
| *i) ''Cadenas con un número impar de ceros y un número par de unos''
| |
|
| |
| [[Imagen:P1E3I.png]]
| |
| <!-- http://graph.gafol.net/create
| |
| rankdir=LR;
| |
| size="8.5";
| |
|
| |
| node [fontname=Arial,fontsize=12];
| |
| node [width=0.6,height=0.6,fixedsize=true];
| |
| edge [fontname=Arial,fontsize=10];
| |
| edge [arrowhead=vee,arrowsize=0.70];
| |
|
| |
| start [style=invisible];
| |
| node [shape = doublecircle]; q1;
| |
| node [shape = circle];
| |
|
| |
| start -> q0;
| |
| q0 -> q1 [label="0"];
| |
| q1 -> q0 [label="0"];
| |
| q2 -> q3 [label="0"];
| |
| q3 -> q2 [label="0"];
| |
| q0 -> q2 [label="1"];
| |
| q2 -> q0 [label="1"];
| |
| q1 -> q3 [label="1"];
| |
| q3 -> q1 [label="1"];
| |
| -->
| |
|
| |
| *j) ''Cadenas donde en todo prefijo (subcadena inicial) la cantida de ceros difiera de la cantidad de unos en no más de 1. Es decir, para todo prefijo se cumple: <math>| \text{cant. de ceros} - \text{cant. de unos} | \leq 1</math>. ∑ = {0,1}.''
| |
|
| |
| [[Imagen:P1E3J.png]]
| |
| <!-- http://graph.gafol.net/create
| |
| rankdir=LR;
| |
| size="8.5";
| |
|
| |
| node [fontname=Arial,fontsize=12];
| |
| node [width=0.6,height=0.6,fixedsize=true];
| |
| edge [fontname=Arial,fontsize=10];
| |
| edge [arrowhead=vee,arrowsize=0.70];
| |
|
| |
| start [style=invisible];
| |
| node [shape = doublecircle]; q0 q1 q2;
| |
| node [shape = circle];
| |
|
| |
| start -> q0;
| |
| q0 -> q1 [label="1"];
| |
| q1 -> q0 [label="0"];
| |
| q0 -> q2 [label="0"];
| |
| q2 -> q0 [label="1"];
| |
| -->
| |
|
| |
| ==Ejercicio 04== | | ==Ejercicio 04== |
| ==Ejercicio 05== | | ==Ejercicio 05== |
| Dados automatas finitos para L1 y L2 indicar c´omo construir aut´omatas
| |
| finitos para los siguientes lenguajes, con las mismas consideraciones que
| |
| en el ejercicio anterior:
| |
| (a) L1 U L2 (union)
| |
| (b) L1 n L2 (interseccion)
| |
| (c) L1.L2 (concatenacion)
| |
| (d) L1 \ L2 (resta)
| |
|
| |
|
| |
| [a] creo un nuevo AFND-\ (automata no deterministico con trans. lambda)
| |
| talque tenga un estado inicia q_o que una con una transicion lambda a los estados finales de los automatas de L1 y L2
| |
| Vale que es la union por la definicion de cadena aceptada en un AFND-\
| |
| que dice que
| |
|
| |
| c es aceptada <==> g(qo,c) pertenece a F , c una cadena
| |
| , con g la funcion de transcicion
| |
| , qo estado inicial
| |
| , F conj de estados finales o aceptores
| |
| [idea de lo q deberia ser la demostracion] : vale trivialmente pues la trans lambda obligatoria de qo no modifica a las cadenas de L1 y L2 y cualquier palabra q sea aceptada por cualquiera de los dos automatas lo sera en el nuevo pues por alguno de las dos tranciciones se llegara al estado aceptor.
| |
|
| |
|
| |
| [b] El automata que deriva de la interseccion se construye de la sigueinte manera :
| |
| Q = Q1 x Q2 ( prod cartesiano de los estados de L1 y L2)
| |
| q0 = (q1,q2) (con q1 y q2 siendo los estados iniciales de Q1 y Q2)
| |
| g( (x,y) , a ) = (g1(x,a),g2(y,a)) con (x,y) pertenece Q
| |
| F = F1 x F2
| |
|
| |
| [demo] :
| |
|
| |
|
| |
|
| |
|
| |
|
| |
| [c]
| |
|
| |
| [d] L1 \ L2 = L1 n (L2^c) (L2^c --> L2 complemento , es decir la clasura de Kleene del alfabeto menos L2)
| |
|
| |
| - aplico la interseccion del item b y el complemento de un ejercicio previo
| |
|
| |
| ==Ejercicio 06== | | ==Ejercicio 06== |
|
| |
|
|
| |
|
| [[Category:Prácticas]] | | [[Category:Prácticas]] |
