Ejemplos.
(1) Dado el alfabeto S = {a, b, c}, escriba las palabras del lenguaje L = {x / x € ∑}.
L = {a, b, c}
(2) ¿Cuál es la cardinalidad del lenguaje L = {ε, a, aa, aaa}?
|L| = 4
(3) Describa, mediante una frase en castellano, el lenguaje del Ejemplo 2.
“El lenguaje formado por la palabra vacía, y las palabras que tienen entre 1 y 3 aes”.
(4) Escriba todas las palabras del lenguaje L = {a2n+1 / 1 ≤ n ≤ 4}.
L = {aaa, aaaaa, aaaaaaa, aaaaaaaaa}
(5) Sea el lenguaje L = {ε, a, ba, abc}. ¿Cuál es el mínimo alfabeto S sobre el que se puede construir este lenguaje?
El mínimo alfabeto es: ∑ = {a, b, c}
(6) Sea el lenguaje L = {0, 00, 01, 010}. Escriba una concatenación de dos palabras que produce otra palabra de este lenguaje.
Sean S1 = 01 y S2 = 0. Entonces: S1S2 = 010 es una palabra del lenguaje.
(7) Sea el lenguaje anterior. Escriba una concatenación de dos palabras que produce una cadena que no es palabra del lenguaje.
Sean S1 = 01 y S2 = 0. Entonces: S2S1 = 001, que no pertenece al lenguaje.
(8) Sea el lenguaje del Ejemplo (6). Escriba tres sublenguajes de L, de distinta cardinalidad.
L1 = {0} – L2 = {0, 00} – L3 = {00, 01, 010}
(9) Describa, mediante una frase en castellano, el lenguaje L = {anbn / 1 ≤ n ≤ 3000}.
“Todas las palabras sobre el ∑ = {a, b} que tienen entre 1 y 3000 aes seguidas de (o concatenadas con) la misma cantidad de bes”.
(10) Sea ∑ = {a, b} y sea el lenguaje ∑*. ¿Cuántas palabras de longitud 3 tiene este lenguaje? ¿Y cuántas de longitud 4?
Tiene 23 palabras de longitud 3 y 24 palabras de longitud 4.
(11) Sea el lenguaje infinito L = {abn / n ≥ 1}. Escriba las tres palabras de menor longitud.
Las tres palabras de menor longitud son: ab, abb y abbb.
(12) Sea el lenguaje infinito L = {(ab)n / n ≥ 1}. Escriba las tres palabras de menor longitud.
Las tres palabras de menor longitud son: ab, abab y ababab.
(13) Sea el alfabeto ∑ = {0, 1}. Describa, por comprensión, un lenguaje infinito L sobre ∑ (que no sea ∑*).
L = {(01)n / n ≥ 1}
(14) Describa, mediante una frase en castellano, el lenguaje definido en el ejercicio anterior.
“El lenguaje formado por todas las palabras que contienen uno o más pares consecutivos de 01”.
