1 SSL marzo 2009 Jorge Muchnik
1 DEFINICIONES BÁSICAS E
INTRODUCCIÓN A LENGUAJES FORMALES
Los LENGUAJES FORMALES están formados por PALABRAS, las palabras son CADENAS y las cadenas están
constituidas por SÍMBOLOS de un ALFABETO.
Esta frase involucra cinco términos (lenguaje, palabra, cadena, símbolo y alfabeto) que son fundamentales en este
campo. A continuación los analizamos detenidamente.
1.1 SÍMBOLOS y ALFABETOS
Un SÍMBOLO (también llamado CARÁCTER) es el elemento constructivo básico; es la entidad fundamental,
indivisible, a partir de la cual se forman los alfabetos.
Un ALFABETO es un conjunto finito de símbolos. Se lo identifica, habitualmente, con la letra griega (sigma) y
con sus caracteres se construyen las palabras de un lenguaje.
Ejemplo 1
La letra a es un símbolo o carácter que forma parte del alfabeto español, del alfabeto inglés, etc.
Ejemplo 2
Los símbolos >, = y + son elementos del alfabeto de los operadores de los lenguajes Pascal y ANSI C .
Ejemplo 3
El alfabeto = {0, 1} proporciona los caracteres utilizados en la construcción de los números binarios.
Ejemplo 4
Los números enteros con signo en base 10 se construyen con símbolos del siguiente alfabeto:
= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -, +}
Ejemplo 5
El “código ASCII” proporciona la representación interna de los caracteres que constituyen el alfabeto más utilizado
en computación.
1.2 CADENAS
Una CADENA, forma abreviada de la frase cadena de caracteres, es una secuencia finita de caracteres tomados de
cierto alfabeto y colocados uno a continuación de otro. Es decir: una cadena se construye CONCATENANDO
caracteres de un alfabeto dado. Como sinónimo de cadena se usa, a veces, el término inglés string.
Ejemplo 6
abac (se lee “a-b-a-c”) es una cadena formada con caracteres del alfabeto {a, b, c}.
Ejemplo 7
101110 (“uno-cero-uno-uno-uno-cero”) es una cadena construida con caracteres del alfabeto {0, 1}.
Ejemplo 8
a es una cadena formada por un solo símbolo de cualquier alfabeto que contenga el carácter a.
Para los conocedores del Lenguaje ANSI C: recuerden la diferencia que existe entre „a‟ y “a”. Es la
misma diferencia que existe entre un símbolo de un alfabeto y una cadena compuesta por ese único
símbolo.
20090410
2 SSL marzo 2009 Jorge Muchnik
1.2.1 LONGITUD DE UNA CADENA
La LONGITUD de una cadena S (se representa |S|) es la cantidad de caracteres que la componen.
Ejemplo 9
La longitud de la cadena abac es: |abac| = 4.
Ejemplo 10
La longitud de la cadena b es: |b| = 1.
1.2.2 CADENA VACÍA
La CADENA VACÍA, que se simboliza habitualmente con la letra griega (épsilon), es la cadena que no tiene
caracteres. En otras palabras: la cadena vacía es la cadena de longitud 0 (|| = 0).
Nota 1: Este símbolo no forma parte de ningún alfabeto.
Nota 2: Algunos autores utilizan la letra griega (lambda) para representar a la cadena vacía.
1.2.3 UNA SIMPLIFICACIÓN: LA POTENCIACIÓN DE UN SÍMBOLO
En muchas ocasiones, una cadena puede contener un carácter que se repite un número determinado de veces.
Ejemplo 11
La cadena aaaaabbbbbbb, construida sobre el alfabeto {a, b}, está formada por 5 aes concatenadas con 7 bes.
La POTENCIACIÓN de un símbolo simplifica la escritura de cadenas como la del ejemplo anterior, de la siguiente
manera: Sea c un carácter cualquiera; entonces, cn representa la concatenación del carácter c, consigo mismo, n-1
veces. Por lo tanto: c1 = c, c2 = cc, c3 = ccc, etc.
En otras palabras, cn representa la repetición del carácter c, n veces.
El operador supraíndice utilizado para potenciar un símbolo indica el número de veces que aparece el
símbolo “potenciado”.
Ejemplo 12
La cadena del Ejemplo 11 (aaaaabbbbbbb) puede escribirse, más sintéticamente, así: a5b7.
Como se puede apreciar, esta simplificación también produce una mejor y más rápida comprensión de la cadena en
cuestión. Y si todavía no está totalmente seguro de esta última afirmación, vea el siguiente ejemplo:
Ejemplo 13
¡La cadena aaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbb es a30b22!
1.2.4 CONCATENACIÓN DE DOS CADENAS
La operación de CONCATENACIÓN aplicada a cadenas (S1S2) produce una nueva cadena formada por los
caracteres de la primera cadena seguidos inmediatamente por los caracteres de la segunda cadena.
Ejemplo 14
Sean las cadenas S1 = aab y S2 = ba; entonces, S1S2 = aabba.
Nota 3: La concatenación se escribe, normalmente, sin utilizar el operador correspondiente (), como en el ejemplo
anterior. Simplemente se coloca una cadena a continuación de la otra.
Nota 4: La concatenación se extiende fácilmente a más de dos cadenas. Por ejemplo: S1S2S3 = S1S2S3.
20090410
3 SSL marzo 2009 Jorge Muchnik
Ejemplo 15
Concatenación de tres cadenas: (ab)(ba)(aab) = abbaaab.
La concatenación NO ES CONMUTATIVA (excepto en casos muy especiales).
Ejemplo 16
ab = ab, mientras que ba = ba. Como ab ba, se comprueba que la concatenación no es conmutativa.
Obviamente, si ambas cadenas son idénticas, entonces la concatenación sí es conmutativa:
Ejemplo 17
Si la primera cadena es ab y la segunda cadena también es ab, entonces: abab (en cualquier orden) es abab.
Otro caso en el que la concatenación es conmutativa ocurre cuando ambas cadenas están compuestas por una
repetición del mismo carácter:
Ejemplo 18
Sea S1 = aa y sea S2 = aaa. Entonces: S1S2 = a2a3 = a2+3 = a5 y S2S1 = a3a2 = a3+2 = a5.
En consecuencia, S1S2 = S2S1 = a5.
La cadena vacía () es la IDENTIDAD para la concatenación. Esto es: para cualquier cadena S,
S = S = S.
1.2.5 POTENCIACIÓN DE UNA CADENA
El supraíndice utilizado para representar la potenciación de un símbolo se extiende fácilmente a una cadena, de esta
manera: si S es una cadena, entonces Sn (con n 1 y entero) representa la cadena que resulta de concatenar la
cadena S, consigo misma, n-1 veces; es decir: la cadena final resulta de repetir la cadena original n veces. Por lo
tanto: S1 = S, S2 = SS, S3 = SSS, etc.
Esta definición se completa con la siguiente afirmación: S0 es (la cadena vacía), para cualquier cadena S.
Ejemplo 19
Sea S = ab; entonces: S3 = SSS = (ab)3 = ababab.
Ejemplo 20
Nótese la diferencia que existe entre la cadena (ab)3 y la cadena ab3: (ab)3 representa la cadena ababab, mientras
que ab3 es la cadena abbb.
Ejemplo 21
(abc)0 = (1234)0 = . ¿Por qué? Revise la definición de “Potenciación de una Cadena”.
Un caso particular: n = para cualquier valor entero de n 0.
1.2.6 PREFIJO, SUFIJO Y SUBCADENA DE UNA CADENA
En la bibliografía sobre este tema existen diferentes definiciones para estos tres conceptos. Nosotros utilizaremos las
siguientes definiciones:
1º Un PREFIJO de una cadena es una secuencia de cero o más caracteres iniciales de esa cadena.
Ejemplo 22
Sea la cadena abcd. Entonces, sus prefijos son: (la cadena vacía), a, ab, abc y abcd (la cadena completa).
2º Un SUFIJO de una cadena es una secuencia de cero o más caracteres finales de esa cadena.
20090410
4 SSL marzo 2009 Jorge Muchnik
Ejemplo 23
Sea la cadena abcd. Entonces, sus sufijos son: , d, cd, bcd y abcd.
3º Una SUBCADENA de una cadena es una secuencia de caracteres que se obtiene eliminando cero o más
caracteres iniciales y cero o más caracteres finales de esa cadena.
Ejemplo 24
Sea la cadena abcd. Entonces, sus subcadenas son: abcd, bcd, cd, d, abc, ab, a, bc, b, c y .
1.3 LENGUAJES NATURALES Y LENGUAJES FORMALES
Se denomina LENGUAJE NATURAL a todo lenguaje hablado y/o escrito que es utilizado por los seres humanos
para comunicarse. Por ejemplo: el español, el inglés y el chino son los tres lenguajes naturales empleados por más
personas en el mundo.
Los Lenguajes Naturales tienen tres características fundamentales:
1º EVOLUCIONAN con el paso del tiempo, incorporando nuevos términos y nuevas reglas gramaticales para
mejorar y actualizar la comunicación;
2º Sus REGLAS GRAMATICALES surgen después del lenguaje, para poder explicar su estructura, es decir: su
sintaxis;
3º El SIGNIFICADO (o sea, la semántica) de cada palabra y de cada oración de un Lenguaje Natural es, en general,
más importante que su composición sintáctica.
Ejemplo 25
“ablar" o “havlar” son sintácticamente incorrectas, pero todos sabemos ¡de qué estamos hablando!
Por otro lado, un LENGUAJE FORMAL (LF) es un conjunto de cadenas formadas con los caracteres de un alfabeto
dado, y tiene una característica fundamental: es un lenguaje abstracto, en el que el término FORMAL pone de
manifiesto que, en esta disciplina, solo estamos interesados en la forma de una cadena (sintaxis) y no en su
significado (semántica).
Contrariamente a lo que ocurre con los Lenguajes Naturales, los LENGUAJES FORMALES están definidos por
reglas gramaticales PREESTABLECIDAS y se deben ajustar rigurosamente a ellas. En consecuencia, un LF nunca
puede evolucionar.
Ejemplo 26
Sea = {a}, un alfabeto con un solo símbolo. Los que siguen son algunos LFs que se pueden construir sobre este
alfabeto: L1 = {a}; L2 = {aa, aaa}; L3 = {, a, a18}.
Ninguno de estos lenguajes puede “evolucionar”, es decir: no se puede modificar mediante el agregado de nuevas
palabras o quitando palabras ya existentes en el lenguaje. Si así se hiciera, obtendríamos otros lenguajes.
Ejemplo 27
Sea el lenguaje L2 = {aa, aaa} del ejemplo anterior. Si agregamos la palabra aaaa, el lenguaje deja de ser L2.
Observe cómo, en el Ejemplo 26, la letra a es utilizada en dos contextos diferentes, representando dos
entidades distintas. Por un lado, a es un símbolo de un alfabeto, mientras que, por otro lado, a es una
palabra de un lenguaje.
En consecuencia, el contexto en el que se encuentra un carácter, debe determinar, sin ambigüedades, el
significado único de ese símbolo, ya sea como miembro de un alfabeto o bien como componente de un LF.
20090410
5 SSL marzo 2009 Jorge Muchnik
1.3.1 PALABRA
Una cadena es vacía, o bien está compuesta por una sucesión de uno o más caracteres que pertenecen a un alfabeto
dado, como hemos visto ya en muchos ejemplos.
Además, una cadena puede ser un miembro de un LF, pero también puede no serlo. Por ello, incorporamos una
nueva definición: “si una cadena pertenece a un determinado lenguaje, decimos que es una PALABRA de ese
lenguaje”. La pertenencia de una cadena a un LF le da la propiedad de ser PALABRA de ese lenguaje en particular.
Ejemplo 28
Refiriéndonos al Ejemplo 26, observamos que el lenguaje L1 tiene una sola palabra, a, mientras que el lenguaje L3
tiene tres palabras: , a, a18. La cadena aa no es una palabra de ninguno de estos dos lenguajes, pero sí lo es del
lenguaje L2.
Ejemplo 29
Describamos un lenguaje por ENUMERACIÓN: sea el lenguaje L = {1, 10, 100, 1000, 10000}.
Utilizando el operador supraíndice, este lenguaje puede ser descripto por COMPRENSIÓN, en forma más compacta,
así: L = {10n / 0 n 4} sobre el alfabeto {0, 1}.
Entonces, la cadena 100 (“uno-cero-cero”) es una palabra del lenguaje L, mientras que 1101 (“uno-uno-cero-uno”)
es una cadena construida con caracteres del mismo alfabeto pero no es una palabra de L, ya que no pertenece a este
lenguaje.
Nota 5: Un LF puede ser descripto por enumeración, por comprensión, mediante una frase en un lenguaje natural
(castellano, en nuestro caso) o mediante otras formas especiales que veremos más adelante.
Ejemplo 30
Sea el lenguaje L del Ejemplo anterior. Lo podemos describir mediante una frase en castellano (lenguaje natural), de
la siguiente manera: “L es un lenguaje de 5 palabras, cada una de las cuales comienza con un símbolo 1 que es
seguido por una secuencia de entre cero y cuatro 0s”.
Si analizamos las tres formas de describir este lenguaje, seguramente consideraremos que son más simples las dos
que figuran en el Ejemplo 29. Sin embargo, hay muchos casos en los que la dificultad para describir el lenguaje con
“simbología matemática” es evidente; en estos casos, debemos utilizar una frase en lenguaje natural, evitando todo
tipo de ambigüedad.
Ejemplo 31
El lenguaje L = {, b, bb, bbb, bbbb, bbbbb, bbbbbb, bbbbbbb, bbbbbbbb} se comprende mejor si sus
palabras se describen por comprensión, así: L = {bi / 0 i 8}.
Ejemplo 32
El lenguaje L = {abi / 1 i 3000} está formado por 3000 palabras; cada una de ellas comienza con la letra a, la
cual es seguida de “entre 1 y 3000 bes”. ¡Qué complicado sería describir y leer este lenguaje por enumeración!
Ejemplo 33
El lenguaje L = {a2ibi / 0 i 2} está formado por tres palabras: si i = 0, a2*0b0 = a0b0 (ausencia de aes y ausencia
de bes) representa la palabra vacía (); si i = 1, la palabra es a2*1b1 = aab; y si i = 2, la palabra es a2*2b2 = aaaabb.
En consecuencia, si enumeramos todas las palabras, el lenguaje L es {, aab, aaaabb}.
1.3.2 PROPIEDADES DE LAS PALABRAS
Dado que una PALABRA es una cadena que pertenece a un determinado lenguaje, todos los conceptos sobre cadena
explicados anteriormente se aplican también a las palabras.
Por lo tanto, hablaremos de: longitud de una palabra, palabra vacía, concatenación de dos o más palabras,
potenciación de una palabra, prefijos y sufijos de una palabra, subpalabras, con el mismo significado ya visto.
20090410
6 SSL marzo 2009 Jorge Muchnik
Ejemplo 34
Sea el lenguaje L = {(abc)n / 0 n 3} = {, abc, abcabc, abcabcabc}.
Entonces: la longitud de la palabra abc es |abc| = 3.
La palabra vacía es un miembro de este lenguaje.
La concatenación de las palabras abc y abcabc produce otra palabra de este lenguaje (abcabcabc); en cambio, la
concatenación de la palabra abcabc consigo misma produce la cadena abcabcabcabc, que no es una palabra de
este lenguaje.
La potencia (abc)2 es una palabra del lenguaje.
La cadena ab es un prefijo de todas las palabras no vacías; lo mismo ocurre con el sufijo bc.
Finalmente, b es una subpalabra de todas las palabras no vacías de este lenguaje.
La concatenación de dos palabras produce una cadena que no siempre es una palabra del lenguaje, como
se observa en el ejemplo anterior y en el ejemplo que sigue.
Ejemplo 35
Sea el lenguaje L = {a2n+1 / 0 n 200}. Este lenguaje está formado por 201 palabras, cada una de las cuales tiene
un número impar de letras a. Por lo tanto, si n = 0, la palabra es a; si n = 1, la palabra es aaa; etc.
Si se concatenan dos palabras cualesquiera de L, el resultado será una cadena con una cantidad par de letras a, ya
que la suma de dos números impares produce un número par.
En consecuencia, la concatenación de dos palabras cualesquiera de este lenguaje produce una cadena que nunca es
una palabra de L.
1.3.3 CARDINALIDAD DE UN LENGUAJE FORMAL
La CARDINALIDAD de un LF es la cantidad de palabras que lo componen.
Ejemplo 36
L = {a, ab, aab} es un lenguaje de cardinalidad 3 sobre el alfabeto {a, b}.
Ejemplo 37
El lenguaje L = {} es un lenguaje muy especial, pues está formado solo por la palabra vacía. Su cardinalidad es 1,
ya que contiene una palabra.
1.3.4 SUBLENGUAJES
Dado que un Lenguaje Formal es un conjunto, un SUBLENGUAJE es un subconjunto de un lenguaje dado.
Ejemplo 38
Sea L1 = {a, ab, aab}. Entonces, L2 = {ab, aab} es un sublenguaje de L1, mientras que L3 = { } es el sublenguaje
vacío de L1.
El sublenguaje vacío, habitualmente representado con el símbolo ø, es sublenguaje de cualquier
lenguaje.
No se debe confundir el sublenguaje vacío, que tiene cardinalidad 0, con el lenguaje que solo contiene
la palabra vacía, que tiene cardinalidad 1.
1.3.5 LENGUAJES FORMALES INFINITOS
Todos los lenguajes ejemplificados hasta el momento han sido LENGUAJES FORMALES FINITOS, es decir:
lenguajes con un número finito de palabras.
Sin embargo, los LFs también pueden ser INFINITOS, lo que significa que estos lenguajes pueden tener una
cantidad infinita de palabras, pero cada una de longitud finita (no existen las palabras de longitud infinita).
20090410
7 SSL marzo 2009 Jorge Muchnik
Nota 6: Las propiedades de las palabras que han sido ejemplificadas anteriormente se aplican también a los
lenguajes infinitos.
Ejemplo 39
L = {an / n 1} es un LF infinito ya que no existe un límite superior para el supraíndice n.
Cada palabra de este lenguaje está formada por una secuencia de una o más aes. Por ello, la concatenación de dos
palabras cualesquiera de este lenguaje producirá siempre otra palabra del lenguaje L.
Por esta propiedad, se dice que este lenguaje L es cerrado bajo la concatenación.
Ejemplo 40
El lenguaje L = {abn / n 0} es otro lenguaje infinito. Está formado por la palabra a y todas aquellas palabras que
comienzan con a, seguida de una secuencia de una o más bes.
Este lenguaje no es cerrado bajo la concatenación ya que, por caso: si consideramos sus dos palabras de menor
longitud –a y ab– y las concatenamos, obtenemos la cadena aab, que no es una palabra de este lenguaje.
1.3.6 LENGUAJE UNIVERSAL SOBRE UN ALFABETO
Dado un alfabeto , el LENGUAJE UNIVERSAL sobre este alfabeto es un lenguaje infinito que contiene todas las
palabras que se pueden formar con los caracteres del alfabeto , más la palabra vacía.
Se lo representa con la notación *, que se lee “sigma clausura” o “sigma estrella”.
Importante: acabamos de introducir un nuevo operador que representamos con el supraíndice *. Este
es un operador unario (sobre un solo operando), como lo es la potenciación en matemáticas.
Se lo denomina “clausura de Kleene” o “estrella de Kleene”, y será muy utilizado en próximos capítulos.
Una propiedad fundamental del Lenguaje Universal es que es cerrado bajo concatenación (por eso la denominación
de “sigma clausura”).
Ejemplo 41
Si = {a, b}, entonces el Lenguaje Universal para este alfabeto es:
* = {, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, ..., aabaabbbab, …},
y la concatenación de palabras de este lenguaje siempre produce una palabra del Lenguaje Universal.
¿Puede encontrar un caso en que esta afirmación sea falsa?
Cualquier lenguaje L sobre el alfabeto es un sublenguaje de *. Por lo tanto, existen infinitos
lenguajes sobre un alfabeto dado.
1.4 RESUMEN: TÉRMINOS Y FRASES IMPORTANTES
SÍMBOLO o CARÁCTER
ALFABETO
CADENA (cadena de caracteres)
CONCATENACIÓN DE CARACTERES
LONGITUD DE UNA CADENA
CADENA VACÍA o CADENA NULA
POTENCIACIÓN DE UN SÍMBOLO
OPERADOR SUPRAÍNDICE
CONCATENACIÓN DE CADENAS
CONMUTATIVIDAD DE LA CONCATENACIÓN
POTENCIACIÓN DE UNA CADENA
PREFIJO DE UNA CADENA
SUFIJO DE UNA CADENA
20090410
8 SSL marzo 2009 Jorge Muchnik
SUBCADENA
LENGUAJES NATURALES vs LENGUAJES FORMALES
PROPIEDADES DE UN LENGUAJE NATURAL
PROPIEDADES DE UN LENGUAJE FORMAL
PALABRA
DIFERENCIA ENTRE CADENA Y PALABRA
DESCRIPCIÓN DE UN LENGUAJE POR ENUMERACIÓN
DESCRIPCIÓN DE UN LENGUAJE POR COMPRENSIÓN
DESCRIPCIÓN DE UN LENGUAJE MEDIANTE UNA FRASE EN LENGUAJE NATURAL
PROPIEDADES DE LAS PALABRAS
CONCATENACIÓN DE PALABRAS
CARDINALIDAD DE UN LENGUAJE
SUBLENGUAJES
LENGUAJES FORMALES
LENGUAJES FORMALES FINITOS
LENGUAJES FORMALES INFINITOS
LENGUAJE UNIVERSAL
OPERADOR “CLAUSURA DE KLEENE” O “ESTRELLA DE KLEENE”
1.5 EJERCICIOS
(1) Dado el alfabeto = {a, b, c}, escriba las palabras del lenguaje L = {x / x }.
(2) ¿Cuál es la cardinalidad del lenguaje L = {, a, aa, aaa}?
(3) Describa, mediante una frase en castellano, el lenguaje del Ejercicio 2.
(4) Escriba todas las palabras del lenguaje L = {a2n+1 / 1 n 4}.
(5) Sea el lenguaje L = {, a, ba, abc}. ¿Cuál es el mínimo alfabeto sobre el que se puede construir este
lenguaje?
(6) Sea el lenguaje L = {0, 00, 01, 010}. Escriba una concatenación de dos palabras que produce otra palabra de
este lenguaje.
(7) Sea el lenguaje anterior. Escriba una concatenación de dos palabras que produce una cadena que no es palabra
del lenguaje.
(8) Sea el lenguaje del Ejercicio (6). Escriba tres sublenguajes de L, de distinta cardinalidad.
(9) Describa, mediante una frase en castellano, el lenguaje L = {anbn / 1 n 3000}.
(10) Sea = {a, b} y sea el lenguaje *. ¿Cuántas palabras de longitud 3 tiene este lenguaje? ¿Y cuántas de
longitud 4?
(11) Sea el lenguaje infinito L = {abn / n 1}. Escriba las tres palabras de menor longitud.
(12) Sea el lenguaje infinito L = {(ab)n / n 1}. Escriba las tres palabras de menor longitud.
(13) Sea el alfabeto = {0, 1}. Describa, por comprensión, un lenguaje infinito L sobre (que no sea *).
(14) Describa, mediante una frase en castellano, el lenguaje definido en el ejercicio anterior.
IMPLEMENTACIÓN EN ANSI C
Para cada una de los ejercicios que siguen, construir en ANSI C la función solicitada y un programa que la pruebe
con todos los datos constantes que sean necesarios.
(15) Longitud de una cadena
(16) Determinar si una cadena dada es vacía.
(17) Concatenación de dos cadenas.
(18) Determinar si una subcadena es Prefijo de una cadena dada.
20090410
9 SSL marzo 2009 Jorge Muchnik
1.5 EJERCICIOS - RESPUESTAS POSIBLES
(1) L = {a, b, c}
(2) |L| = 4
(3) “El lenguaje formado por la palabra vacía, y las palabras que tienen
entre 1 y 3 aes”.
(4) L = {a3, a5, a7, a9}
(5) El mínimo alfabeto es: ∑ = {a, b, c}
(6) Sean S1 = 01 y S2 = 0. Entonces: S1S2 = 010 es una palabra del lenguaje.
(7) Sean S1 = 01 y S2 = 0. Entonces: S2S1 = 001, que no pertenece al
lenguaje.
(8) L1 = {0} - L2 = {0, 00} - L3 = {00, 01, 010}
(9) “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) Tiene 23 palabras de longitud 3 y 24 palabras de longitud 4.
(11) Las tres palabras de menor longitud son: ab, abb y abbb.
(12) Las tres palabras de menor longitud son: ab, abab y ababab.
(13) L = {(01)n / n ≥ 1}
(14) “El lenguaje formado por todas las palabras que contienen uno o más
pares consecutivos de 01”.
Implementación de las funciones en ANSI C:
(15) unsigned LongitudCadena (const char *s) {
unsigned i;
for (i=0; s[i]!= „\0‟; i++);
return i;
} /* fin */
/* programa de prueba */
#include <stdio.h>
unsigned LongitudCadena (const char *);
int main () {
printf ("Longitud de cadena vacia = %u\n", LongitudCadena(""));
printf ("Longiud de csdena \"abc\" = %u\n", LongitudCadena("abc"));
return 0;
} /* fin */
(16) int EsCadenaVacia (const char *s) {
if (s[0] == „\0‟) return 1; /* es vacia */
return 0; /* no es vacia */
} /* fin */
/* programa de prueba */
#include <stdio.h>
int EsCadenaVacia (const char *);
int main () {
if (EsCadenaVacia("")) printf ("La cadena vacia es vacia\n");
else printf ("La cadena vacia no es vacia\n");
if (EsCadenaVacia("abc")) printf ("La cadena \"abc\" es vacia\n");
else printf ("La cadena \"abc\" no es vacia\n");
return 0;
} /* fin */
20090410
10 SSL marzo 2009 Jorge Muchnik
(17) void ConcatenaCadenas (char *s1, const char *s2) {
unsigned i, j;
for (i=0; s1[i] != „\0‟; i++);
for (j=0; s2[j] != „\0‟; j++, i++)
s1[i] = s2[j];
s1[i] = „\0‟;
} /* fin */
/* programa de prueba */
#include <stdio.h>
void ConcatenaCadenas (char *, const char *);
int main () {
char s11[10+1] = "";
char s12[10+1] = "abc";
ConcatenaCadenas (s11,"xyz");
printf ("La nueva cadena es: %s\n", s11);
ConcatenaCadenas (s12,"xyz");
printf ("La nueva cadena es: %s\n", s12);
return 0;
} /* fin */
(18) int EsPrefijo (const char *s, const char *t)
{ unsigned i;
for (i=0; s[i] != „\0‟ && s[i] == t[i]; i++);
if (t[i] == „\0‟) return 1; /* t es prefijo de s */
return 0; /* no es prefijo */
} /* fin */
/* programa de prueba */
#include <stdio.h>
int EsPrefijo (const char *, const char *);
int main () {
if (EsPrefijo("abcd", "ab"))
printf ("\"ab\" es prefijo de \"abcd\"\n");
else
printf ("\"ab\" no es prefijo de \"abcd\"\n");
if (EsPrefijo("ab", "abcd"))
printf ("\"abcd\" es prefijo de \"ab\"\n");
else
printf ("\"abcd\" es prefijo de \"ab\"\n");
return 0;
} /* fin */
20090410
