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

De Cuba-Wiki
Revisión del 01:01 15 abr 2010 de 186.124.124.20 (discusión) (→‎Ejercicio 05)
(difs.) ← Revisión anterior | Revisión actual (difs.) | Revisión siguiente → (difs.)

Plantilla:Back

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)
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}.

Archivo:P1E3G.png

  • h) Cadenas que no contengan dos unos consecutivos. ∑ = {0,1}.

Archivo:P1E3H.png

  • i) Cadenas con un número impar de ceros y un número par de unos

Archivo:P1E3I.png

  • 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}.

Archivo:P1E3J.png

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