Teoria de la computacion Lenguajes formales

        [pic 1]

[pic 2]

UNIVERSIDAD DE GUADALAJARA

CENTRO UNIVERSITARIO DE CIENCIAS EXACTAS E INGENIERIAS

ALUMNO: GUSTAVO RAMOS DE LA CRUZ

CARRERA: INGENIERIA INFORMATICA

CODIGO: 217294113

MATERIA: TEORIA DE LA COMPUTACION

PROFESOR: MARIA MAGDALENA LEAÑO

ACTIVIDAD:  Nº1 LENGUAS FORMALES

ACTIVIDAD I : LENGUAJES FORMALES

Fecha de entrega: I semana Entregables: Mínimo 3 ejercicios

1.- Indica cuál de las siguIentes sentencias se mantienen, y cuales no, para todos los lenguajes L1 y L2. Para mostrar que la sentencias no se mantienen, se deben dar dos ejemplos de L1 y L2 donde la sentencia es falsa. Cuando la sentencia sea verdadera, se debe dar una pequeña explicación del caso.

a)L ∗ 1 ∪ L ∗ 2=(L1 ∪ L2) ∗

b)L ∗ 1 ∩ L ∗ 2=(L1 ∩ L2) ∗

c)( L ∗ 1 ∩ L ∗ 2 ) ∗  = ( L 1 ∩ L 2 ) ∗

d)( L ∗ 1 · L ∗ 2 ) ∗ = ( L 1 ∪ L 2 ) ∗

e)(L1 ·L2) ∗ =(L1 ∪ L2)

2.- Sea L el lenguaje definido por L = { ꜫ  , 0, 10} Indica los siguientes conjuntos.

 a) L ∪  L  =   {  ꜫ010 }

b) L ∩ L    =   { ꜫ  , 0, 10}

c) L·L        =   { ε ε  , ε0 , ε10 ,0 ε ,00 ,010 , 10 ε , 100 ,1010 }

d) L·L       =    { ε ε  , ε0 , ε10 ,0 ε ,00 ,010 , 10 ε , 100 ,1010 }

e) L 2       =  { ε2, 02, 102 }

3.- Indique cual de las siguientes sentencia es VERDADERA y cual es FAL SA. Es necesario que se de una breve explicación de tu respuesta para ser tomada en cuenta. .

1. Existe un lenguaje L tal que L=L·L  verdadero

Cuando los elementos de L se repiten cada símbolo dos veces en la cadena.

1. Existe un lenguaje L con ε ε ∈ L tal que L=L ∗ verdadero

Cuando la cadena vacia forma parte de alguno de los lenguajes.

1. Para todos los lenguajes L, tenemos que L ∗ = (L ∪ ) ε ∗ Falso

Porque no todas las cadenas de ambos lenguajes  se concatenan.

1. Para todos los lenguajes L1,L2, y L3, si L1 ⊆ L2 y L ∗ 2 ⊆ L ∗ 3, entonces L1 ⊆ L3 Verdadero

Porque todos los elementos pertenecen al mismo conjunto y si L1 esta en L2 y L2 esta en L3 entonces L1 tambien esta en L3

1. Para todos los lenguajes L1 y L2, si L ∗ 1 = L ∗ 2, entonces L1 = L2   Verdadero

Porque ambos lenguajes contiene los mismos simbolos y por lo tanto uno es equivalente al otro.

4.- Dado el alfabeto  = {a, b}, Σ y el lenguaje definido sobre él, L = {aa, bb} ¿cómo son las palabras de lenguaje L4?

...