Revisión actual |
Tu texto |
Línea 6: |
Línea 6: |
|
| |
|
| *a) ''Constantes reales con signo'' | | *a) ''Constantes reales con signo'' |
| S -> +A | -A | | S->+A|-A |
| A -> 0,C | 1..9B | | A->0,C|1..9B |
| B -> 0..9B | ,C | λ | | B->0..9B|,C|λ |
| C -> 0..9C | 1..9 | | C->0..9C|1..9 |
| | |
| S -> +A | -A
| |
| A -> E | E,D
| |
| E -> 0 | E'
| |
| E'-> 1..9 | E'0..9
| |
| D -> 1..9 | 0..9D
| |
|
| |
|
| *b) <math>L = {x = a^i b^j \vee x = (cd)^{2n+2}, i \geq 0, n,j \geq 1}</math> | | *b) <math>L = {x = a^i b^j \vee x = (cd)^{2n+2}, i \geq 0, n,j \geq 1}</math> |
| S -> Ab | cdcdcdB | | S->aS | bA | cdcdcdB |
| A -> aA | Ab | λ | | A->bA | λ |
| B -> cdcdB | λ | | B->cdcdB | λ |
|
| |
|
| *c) ''Cadenas que contengan 3 ceros consecutivos.'' | | *c) ''Cadenas que contengan 3 ceros consecutivos.'' |
| S -> 0A | 1S | | S->(0,1)S | 000A, A->(0,1)A, A->λ |
| A -> 0B | 1S
| |
| C -> 0C | 1S
| |
| C -> 0C | 1S | λ
| |
|
| |
|
| *d) ''Cadenas que representen una fecha valida de este siglo (p. ej, 29/2/01 es invalida)'' | | *d) ''Cadenas que representen una fecha valida de este siglo (p. ej, 29/2/01 es invalida)'' |
Línea 32: |
Línea 23: |
| | 29/(1,3..12)/(00..99) | | | 29/(1,3..12)/(00..99) |
| | 29/2/(00,04..96) | | | 29/2/(00,04..96) |
| | 30/(4,6,9,11)/(00..99) | | | 30/(2,4,6,9,11)/(00..99) |
| | 31/(1,3,5,7,8,10,12)/(00..99) | | | 31/(1,3,5,7,8,10,12)/(00..99) |
| *e) ''Cadenas que representen una hora valida (p. ej, 23:60 es invalida)'' | | *e) ''Cadenas que representen una hora valida (p. ej, 23:60 es invalida)'' |
| S -> B:CB | 1B:CB | 2D:CB | | S->(0,1)A | 2E |
| B -> 0..9 | | A->(0..9)B |
| C -> 0..5 | | B->:C |
| D -> 0 | 1 | 2 | 3 | | C->(0..5)D |
| | D->(0..9) |
| | E->(0..3)B |
|
| |
|
| ==Ejercicio 02== | | ==Ejercicio 02== |
|
| |
| ==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]] |