Edición de «Práctica 1: Gramáticas Regulares y Autómatas Finitos (Teoría de Lenguajes)»

{{Back|Teoría de Lenguajes}}

==Ejercicio 01==

''Construir gramaticas regulares para los siguientes lenguajes:''

*a) ''Constantes reales con signo''
 S -> +A | -A
 A -> 0,C | 1..9B
 B -> 0..9B | ,C | λ
 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>
 S -> Ab | cdcdcdB
 A -> aA | Ab | λ
 B -> cdcdB | λ

*c) ''Cadenas que contengan 3 ceros consecutivos.''
 S -> 0A | 1S
 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)''
 S->(1..28)/(1..12)/(00..99) 
 | 29/(1,3..12)/(00..99)
 | 29/2/(00,04..96)
 | 30/(2,4,6,9,11)/(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)''
 S -> B:CB | 1B:CB | 2D:CB
 B -> 0..9
 C -> 0..5
 D -> 0 | 1 | 2 | 3

==Ejercicio 02==

==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 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==


[[Category:Prácticas]]