SEP                                DGIT                    SEIT

     INSTITUTO  TECNOLÓGICO  DE  MINATITLAN

Operaciones de conjuntos de ∑*

Las cadenas de símbolos juegan un papel importante en las ciencias computacionales. Programas computacionales, documentos escritos en texto, fórmulas matemáticas y teoremas en un sistema formal son objetos que representamos convencionalmente como secuencias finitas de símbolos. Así, para poder escribir programas que manipulen otros programas, programas editores de texto, programas para manipular fórmulas algebraicas o programas que prueben teoremas debemos de tener las herramientas necesarias para la manipulación de cadenas individuales y conjuntos de cadenas.

El símbolo å denotará un alfabeto finito y å* será el conjunto de todas las cadenas de longitud finita formados por los símbolos provenientes de å. La principal operación sobre los elementos de å* es la concatenación.

Sea å un alfabeto y x  y y elementos de å*. Si x =a₁ a₂… a_m y y = b₁ b₂... b_n donde a_i, b_j Î å y m, n Î N entonces la concatenación de x con y, denotada x·y, o simplemente xy, es la cadena xy = a₁ a₂… a_m b₁ b₂... b_n. Si x =L, entonces xy = y para toda x; similarmente si y = L, entonces xy= x

Lo siguiente es una notación conveniente para representar la concatenación de una cadena con sí misma n veces. Esta definición inductiva es basada en la definición de N y además no requiere cláusula extrema.

Sea x un elemento de å*. Para cada n Î N, la cadena xⁿ es definido como sigue:

1.  x⁰ = L

2.  xⁿ⁺¹ = x⁰· x

Como por ejemplo, si å = {a, b} y x = ab, entonces x⁰ = L, x¹ = ab, x² = abab, x³ = ababab.

Con frecuencia trataremos colecciones de cadenas en vez de cadenas individuales. Por ejemplo, en una especificación de lenguaje de programación, deberemos de caracterizar conjuntos enteros de programas los cuales pueden ser escritos en el lenguaje. Dada la importancia de estos elementos, una considerable estructura de terminologías y notaciones han sido desarrolladas para concordar con esto.

Sea å un alfabeto finito. Un lenguaje sobre å es un subconjunto de å*. Por ejemplo, el conjunto {a, ab, abb} es un lenguaje sobre å = {a, b}.

Desde que cada lenguaje es un conjunto la colección usual de operaciones de conjuntos vistas en este documento pueden ser aplicadas a los lenguajes. De cualquier modo, dado que son colecciones de cadena, hay otras operaciones de lenguaje importantes que pueden ser definidas también, muchas de las cuales son basadas en las operaciones de concatenación. Estas operaciones son importantes en una variedad de áreas de aplicación así como también para el estudio de modelos de computación.

Sea  A y  B lenguajes sobre å. El  conjunto producto de A con B, denotado como A · B, o simplemente  AB, es el lenguaje AB = { xy 1 x Î A Ù y Π B }.

El lenguaje AB consiste en todas las cadenas formadas por la concatenación de un elemento de A con un elemento de B. Se debe hacer notar que en general AB ¹ BA ya que la operación de producto de conjunto no es conmutativa.

Sea A, B, C y D lenguajes arbitrarios sobre å, de lo cual se obtienen las siguientes relaciones:

a)  AÆ = ÆA = Æ

b)  A{ L } = { L } A = A

c)  ( AB) C = A( BC )

d)  Si A Ì B y C Ì D, entonces AC Ì BD

e)  A(B È C) = AB È AC

f)  ( B È C ) A = BA È CA

g)  A ( B Ç C) Ì AB  AC

h)  ( B Ç C) A Ì BA Ç CA

Sea A un lenguaje sobre å. El lenguaje Aⁿ es definido inductivamente como sigue:

A⁰ = { L }

Aⁿ⁺¹ = Aⁿ · A

El lenguaje Aⁿ es un conjunto de productos de A con si mismo n veces. Además si zÎ Aⁿ con n ³ 1, entonces z = w₁w₂... w_n, donde w_i Î A para cada i desde 1 hasta n.