Teoria de grupos- programacion en tiempo real

TEORÍA DE GRUPOS
SEMIGRUPOS
S ≠0 es semigrupo si está dotado de una operación binaria * (interna) que verifica la propiedad Asociativa: a * (b * c) = (a * b) * c diremos que es un semigrupo conmutativo si se verifica, además, la propiedad Conmutativa: a * b = b *a
Ejemplos: Son semigrupos conmutativos:
• El conjunto N provisto de la suma (N, +).
• El conjunto Z provisto del producto (Z, ・).Ejemplos:
• N con la operación a * b = ab no es un semigrupo.
• Z con la operación de sustracción tampoco es semigrupo.
Ejemplo: (P(A),*) y (P(A), ∩) son dos semigrupos conmutativos.

Ejemplos:
• Si A ≠0 y AA = {f | f : A → A}, entonces (AA, ◦) es un semigrupo no conmutativo.
• (Mn, ・) es un semigrupo no conmutativo.
SUBSEMIGRUPOS
Dado un semigrupo (S, *) y un subconjunto A * S diremosque es un subsemigrupo si restringiendo la operación * a los elementos de A se sigue teniendo una estructura de semigrupo, es decir (A, *) es también semigrupo. Es evidente que la ´única condición para que A sea subsemigrupo de S es que la restricción de *A sea una operación. Cuando un conjunto cumple esta condición se suele decir que A es cerrado para la operación. En la figura, A no seríasubsemigrupo de S.

Ejemplos:
• Dado el semigrupo (Z,+) El subconjunto 2Z de los enteros pares es subsemigrupo, en cambio el conjunto de los impares no lo es.
• En el semigrupo (AA, ◦) el subconjunto de las funciones biyectivas S(A) es un subsemigrupo.
MONOIDES
Dado un semigrupo (S, ∗) diremos que tiene elemento neutro si existe un elemento distinguido e * S que verifica e*a = a*e = a *a * S.Teorema 1 En todo semigrupo, el elemento neutro, si existe, debe ser único. A un semigrupo con elemento neutro se le llama monoide. Si además el semigrupo es conmutativo se le llama monoide conmutativo.
Ejercicio: Determina cuáles de los ejemplos de semigrupos ya vistos son también monoides.
Ejemplos:
• La estructura (N,+) es monoide, en cambio (Z+,+) no lo es, puesto que 0 € Z+.
• Las matricesreales Mn×m forman un monoide conmutativo con la operación + de matrices. Si consideramos las matrices cuadradas con el producto (Mn×n, ・) tenemos un monoide no conmutativo.
SUBMONOIDES
Dado un monoide (S, *), un subconjunto A *S es submonoide, si además de ser subsemigrupo, contiene al elemento neutro. Por tanto, según vimos anteriormente se verifica
Teorema 2 Sea (S, *) un monoide y A *S.
Lascondiciones necesarias y suficientes para que el subconjunto A sea submonoide son:
1) Que sea cerrado para la operación, es decir:
a, b ∈ A ⇒ a ∗ b ∈ A.
2) e ∈ A.

Ejemplo: Llamaremos nZ al conjunto de los productos de un entero n por todos los elementos de Z. Si n > 1 obtenemos que (nZ,+) son submonoides de (Z, +), en cambio (nZ, ・) son subsemigrupos (y no submonoides) de (Z, ・) (que síes monoide).
EL SEMIGRUPO LIBRE DE LAS CADENAS
Llamaremos alfabeto a un conjunto Σ al que se le exige que ningún elemento pueda ser formado por yuxtaposición de elementos del propio Σ. A los elementos de Σ se les llama también cadenas de longitud 1.
Yuxtaponiendo dos elementos de Σ se obtiene un nuevo elemento de un conjunto de cadenas de longitud 2. Este proceso se puede extender recursivamentepara formar cadenas de longitud n. Si denominamos Σ1 =Σ, entonces
∑n = {xy | x € Σ, y € Σn−1} n > 1
El conjunto de todas las cadenas –de longitud mayor o igual que 1– se representa por Σ+ = n=1∞Σn

Consideramos de forma axiomática la existencia de una cadena ε que no pertenece a ningún Σn y que llamaremos cadena de longitud 0, o bien, cadena nula. Esta cadena tiene la propiedad dedejar invariante a cualquier cadena por yuxtaposición, es decir
xε = εx = x vx * Σn
Por ´ultimo, llamaremos Σ* al conjunto formado por las cadenas de cualquier longitud, incluida la cadena nula.
Σ* =Σ+ U {ε}
Este conjunto, dotado con la operación binaria de yuxtaponer dos cadenas, también llamada concatenación, verifica la propiedad asociativa, y además tiene elemento neutro ε. Se le...