Diferencia entre revisiones de «Práctica 1: Gramáticas Regulares y Autómatas Finitos (Teoría de Lenguajes)»
(No se muestran 28 ediciones intermedias de 2 usuarios) | |||
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-> | S -> Ab | cdcdcdB | ||
A-> | A -> aA | Ab | λ | ||
B->cdcdB | λ | B -> cdcdB | λ | ||
*c) ''Cadenas que contengan 3 ceros consecutivos.'' | *c) ''Cadenas que contengan 3 ceros consecutivos.'' | ||
S-> | 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)'' | *d) ''Cadenas que representen una fecha valida de este siglo (p. ej, 29/2/01 es invalida)'' | ||
Línea 23: | Línea 32: | ||
| 29/(1,3..12)/(00..99) | | 29/(1,3..12)/(00..99) | ||
| 29/2/(00,04..96) | | 29/2/(00,04..96) | ||
| 30/( | | 30/(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-> | S -> B:CB | 1B:CB | 2D:CB | ||
B -> 0..9 | |||
C -> 0..5 | |||
C-> | D -> 0 | 1 | 2 | 3 | ||
D-> | |||
==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]] |
Revisión actual - 22:12 30 abr 2017
Ejercicio 01[editar]
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)
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/(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[editar]
Ejercicio 03[editar]
Construir autómatas finitos para los siguientes lenguajes:
- g) Cadenas que contengan 3 ceros consecutivos. ∑ = {0,1}.
- h) Cadenas que no contengan dos unos consecutivos. ∑ = {0,1}.
- i) Cadenas con un número impar de ceros y un número par de unos
- 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: . ∑ = {0,1}.
Ejercicio 04[editar]
Ejercicio 05[editar]
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