Universidad Rey Juan Carlos Curso 2007–2008 ´ ´ Teorıa de Automatas y Lenguajes Formales ´tica de Sistemas Ingenier´ıa T´ ecnica en Informa Hoja de Problemas 1 Lenguajes Formales

Nivel del ejercicio : (!) b´asico, (♣) medio, (♠) avanzado. 1. (!) Sea Σ = {0, 1, 2}, x = 00, y = 1, z = 210. Definir las siguientes palabras : xy, xz, yz, xyz, (xy)−1 , x3 , x2 y2 , (xy)2 , (zxx)3 . Indicar sus longitudes. ¿Contiene W(Σ) la palabra vac´ıa λ?. Soluci´ on: xy = 001 xz = 00210 yz = 1210 xyz = 001210 (xy)−1 = 100 x3 = 000000 x2 y2 = 000011 (xy)2 = 001001 (zxx)3 = 210000021000002100000

|xy| = 3 |xz| = 5 |yz| = 4 |xyz| = 6 |(xy)−1 | = 3 |x3 | = 6 |x2 y2 | = 6 |(xy)2 | = 6 |(zxx)3 | = 21

2. (!) Describir las palabras pertenecientes a los siguientes lenguajes: L1 = {0n 1n | n ≥ 1} y

L2 = {0i 1j | 0 ≤ i ≤ j}

Soluci´ on: L1 es un lenguaje binario, palabras formadas por ceros y unos, donde todos los ceros preceden a los unos y existe el mismo n´ umero de ceros que de unos. Adem´as, no se reconoce la palabra vac´ıa (λ), ya que si nos fijamos, siempre nos exige que haya por lo menos un cero y un uno. L2 es un lenguaje binario, palabras formadas por ceros y unos, donde siempre hay un n´ umero mayor o igual de unos que de ceros y los ceros preceden siempre a los unos. Reconoce la cadena vac´ıa (λ). 3. (!) Describir formalmente (en notaci´on conjuntista) el lenguaje formado por 0’s y 1’s, en el que hay el doble de 0’s que de 1’s y todos los 0’s van delante de los 1’s.

P´agina 1 de 5

Hoja de Problemas 1 (cont.)

Soluci´ on: L = {02i 1i | i ≥ 1} 4. (!) Describir formalmente (en notaci´on conjuntista) el lenguaje formado por palabras que comienzan y terminan en a teniendo entre medias 3 o m´as b’s. Soluci´ on: Σ = {a, b}, L = {abn a|n ≥ 3} 5. (!) Dados el alfabeto Σ = {1, 2, 3, a, b, c}, y los lenguajes L1 = {1, 2, 3} y L2 = {a, b, c}, definir los lenguajes L21 , L1 ∪ L2 , L1 L2 y (L1 L2 )2 . Soluci´ on: L21 = {11, 12, 13, 21, 22, 23, 31, 32, 33} L1 ∪ L2 = {1, 2, 3, a, b, c} L1 L2 = {1a, 1b, 1c, 2a, 2b, 2c, 3a, 3b, 3c} (L1 L2 )2 = {1a1a, 1a1b, 1a1c, 1a2a, . . . , 3c3c}

6. (!) Sea L = {ab, aa, baa}. Indicar cu´ales de las siguientes palabras pertenecen a L+ : abaa, abab, abaabaaabaa, aaaabaaaa, baaaaabaaaab, baaaaabaa, λ. Soluci´ on: descomp.

abaa ∈ L+

−→

abab ∈ L+

descomp.

aaaabaaaa ∈ L+

descomp.

abaabaaabaa ∈ L+ baaaaabaaaab ∈ / L+ +

baaaaabaa ∈ L λ∈ / L+

ab !"#$ aa !"#$ ab !"#$ ab !"#$

−→

descomp.

−→ −→

descomp.

−→

descomp.

ab !"#$ aa !"#$ baa !"#$ ab !"#$ aa !"#$ aa !"#$ aa !"#$ baa !"#$ aa !"#$

baa !"#$ aa !"#$ ab !"#$ aa !"#$ aab !"#$

aab∈L /

−→ baa !"#$ aa !"#$ ab !"#$ aa !"#$ (Si λ ∈ / L, entonces λ ∈ / L+ )

7. (♣) Sean L1 = {an bn+1 | n ≥ 1} y L2 = {w | num. a# s = num. b# s}. ¿Es L1 = L∗1 ?. ¿Y L2 = L∗2 ?.

P´agina 2 de 5

Hoja de Problemas 1 (cont.)

Soluci´ on: Para demostrar las igualdades entre conjuntos (A = B) debemos demostrar que existe doble inclusi´on (que A ⊆ B y B ⊆ A). Es decir, que todos los componentes de A est´an en B y viceversa, que todos los componentes de B est´an en A. L1 = L∗1 En ning´ un caso puede ser que L1 = L∗1 . La raz´on est´a en que L∗1 contiene la palabra vac´ıa (λ) por definici´on, mientras que L1 no la contiene. Por lo tanto, no se cumple L∗1 ⊆ L1 . L2 = L∗2 % i Que L2 ⊆ L∗2 se deriva de la propia definici´on del cierre (L∗ = ∞ i=0 L ). Por lo que nos queda por demostrar que L∗2 ⊆ L2 . Como λ ∈ L∗2 , debemos demostrar que tambi´en λ ∈ L2 . Esto es cierto, ya que en la palabra vac´ıa el n´ umero de a’s es igual al n´ umero de b’s (ambas cero). Por lo tanto, λ ∈ L2 . Por otro lado debemos ver si el resto de palabras inclu´ıdas en L∗2 pertenecen a L2 . Eso tambi´en es cierto, ya que L∗2 se forma mediante la (m´ ultiple) concatenaci´on de palabras del lenguaje L2 . Si las palabras que estamos concatenando tienen igual n´ umero de a’s que de b’s, siempre estamos a˜ nadiendo el mismo n´ umero de cada una de las letras a la palabra resultante y, por lo tanto, la palabra resultado tambi´en se encuentra en L2 . Por lo tanto, podemos afirmar que L∗2 ⊆ L2 . Como L2 ⊆ L∗2 y L∗2 ⊆ L2 , entonces podemos decir que L2 = L∗2 . 8. (♣) ¿Existe alg´ un lenguaje tal que (L∗ ) = (L)∗ ?. Soluci´ on: Para demostrarlo utilizaremos la definici´ on del cierre que hemos visto anteriormente. Podemos decir que λ ∈ (L)∗ , pertenezca o no a L, gracias a la propia definici´on del cierre de un lenguaje. Por la misma raz´on, podemos afirmar que λ ∈ (L∗ ). Como λ ∈ (L∗ ), entonces λ ∈ / (L∗ ). Por lo tanto, hemos encontrado un elemento (la palabra vac´ıa λ) que, perteneciendo a (L)∗ , no pertenece a (L∗ ). Por lo tanto la igualdad no se cumple. 9. (♣) Demostrar o refutar la igualdad siguiente : (L∗ )−1 = (L−1 )∗ , para todo lenguaje L.

P´agina 3 de 5

Hoja de Problemas 1 (cont.)

Soluci´ on: Dado un lenguaje L cualquiera, L = {x1 , x2 , x3 , ..., xn , ...} Sea X una palabra que pertenece al cierre de ese lenguaje: X = x1 x2 x3 x4 ...xn ∈ L∗ Debemos comprobar que X −1 ∈ (L−1 )∗ para demostrar que (L∗ )−1 ⊆ (L−1 )∗ . Usando las propiedades de la reflexi´on: −1 (xy)−1 = y −1 x−1 y (L1 L2 )−1 = L−1 2 L1 ,

podemos afirmar que: −1 −1 X −1 = x−1 n xn−1 ...x1

Dado que: −1 −1 −1 −1 −1 ∈ (L−1 )∗ , por lo tanto, X −1 ∈ (L−1 )∗ L−1 = (x−1 n , xn−1 , ...x1 ) y xn xn−1 ...x1

entonces podemos afirmar que: (L∗ )−1 ⊆ (L−1 )∗ Podemos razonar de forma an´aloga para demostrar que: (L−1 )∗ ⊆ (L∗ )−1 aunque es trivial. 10. (♣) Demostrar que para todo lenguaje L, se verifica L∗ L∗ = L∗ . Soluci´ on: Simplemente deberemos aplicar la definici´on de cierre, recordemos: ∗

L =

∞ &

Li

i=0

Tambi´en tendremos en cuenta las propiedades de la potencia, en concreto: Li Lj = Li+j

P´agina 4 de 5

Hoja de Problemas 1 (cont.)

L1 (L2 ∪ L3 ) = L1 L2 ∪ L1 L3 Ahora, desarrollaremos el lado izquierdo de la igualdad: L∗ L∗ = (L0 ∪ L1 ∪ L2 ∪ . . .)(L0 ∪ L1 ∪ L2 ∪ . . .) = (L◦ L◦ ∪ L◦ L1 ∪ L◦ L2 ∪ . . . ∪ L1 L◦ ∪ L1 L1 ∪ L1 L2 ∪ . . .) Y simplemente, reagrupando los t´erminos y aplicando la propiedad anterior, nos queda: L∗ L∗

= L0 L0

∪ L0 L1 ∪ L1 L0

=

∪

λ

L1

∪ L0 L2 ∪ L1 L1 ∪ L2 L0 ∪ L2

∪ L0 L3 ∪ L1 L2 ∪ L2 L1 ∪ L3

∪... ∪... ∪... ∪ . . . = L∗

Que es lo que quer´ıamos demostrar. 11. (!) Describir el lenguaje generado por la gram´atica: G = ({S}, {a, b}, S, {S ::= SS | aSb | bSa | λ}) .

Soluci´ on: El lenguaje que describe esta gram´atica es el siguiente:L = {w | na (w) = nb (w)}, siendo nx (w) el n´ umero de x que aparecen en w.

P´agina 5 de 5