Siguiente: Gramáticas formales Un nivel arriba: Fundamentos matemáticos Anterior: Propiedades de cerradura

Ejercicios

1. Proporcione tres ejemplos de monoides finitos mostrando sus respectivas tablas de operación.

2. En cada una de las operaciones definidas a continuación, sobre el conjunto de número naturales $I\!\!N=\{0,1,2,\ldots\}$, decida si es acaso asociativa o si posee una unidad lateral:

$$\begin{array}{rrcl} \mbox{\it i.\/} & x*y &=& \mathop{\rm Ma... ...op{\rm Min}\{x,y\}\geq 10$. } \end{array}\right. \end{array}$$

3. Sea S un conjunto no vacío dotado de una operación binaria $*:S^2\rightarrow S$ tal que

$$\forall x,y\in S:\ \ \ x*y=x.$$

Muestre que * es una operación asociativa.

4. Suponga que en un monoide (S,*) se cumplen las relaciones siguientes:

$$\begin{array}{rlrcl} \mbox{\it i.\/} &\forall x& x*x &=& x\ ... ...\/} &\forall x,y,z,w & (x*y)*(z*w) &=& (x*z)*(y*w) \end{array}$$

Muestre que entonces se cumple la relación

$$\forall x,y,z:\ \ \ x*(y*z) = (x*y)*(x*z).$$

Dé un ejemplo que ilustre este ejercicio.

5. Sea (S,*) un monoide y $a\in S$ un elemento cualquiera. Se define una nueva operación ``$\bullet$'' haciendo

$$\forall x,y:\ \ \ x\bullet y= x*a*y.$$

Muestre que esta nueva operación es asociativa. Dé condiciones sobre a suficientes para que esta operación posea unidad, y en tal caso caracterice a las unidades.

6. Muestre que si (S,*) es una estructura asociativa finita, entonces posee un elemento idempotente, es decir,

$$\exists a\in S:\ \ \ a*a=a.$$

7. Sea n>1 un entero positivo. Para cada entero x sea $\mbox{\rm long}_n(x)$ el mínimo entero k tal que n^k>x. $\mbox{\rm long}_n(x)$ se dice ser la longitud de x en base n. Dados $x,y\in I\!\!N$ definimos $x*y=x\cdot n^{\mbox{\scriptsize long}_n(x)}+y$. Pruebe que $(I\!\!N,*)$ es un monoide.

8. Sean R y S dos relaciones de equivalencia sobre un conjunto dado. Sea $T=R\cap S$, es decir,

$$\forall x,y:\ \ xTy\,\Leftrightarrow\,(xRy)\&(xSy).$$

a) Pruebe que T es una relación de equivalencia. b) Exprese al índice de T en términos de los índices de R y S. c) Sea $U=R\cup S$. Decida si acaso U es una relación de equivalencia y justifique su decisión.

9. En $I\!\!N$, considere la relación,

$$R=\{(x,y)\vert x-y\mbox{\rm es positivo e impar }\}.$$

Decida si acaso R es reflexiva, o simétrica, o transitiva, o antisimétrica, o de equivalencia o de orden.

10. En (0+1)^*, considere la relación,

$$R=\{(\sigma,\tau)\vert\sigma\mbox{\rm y }\tau\mbox{\rm poseen el mismo n\'umero de 0's }\}.$$

Decida si acaso R es reflexiva, o simétrica, o transitiva, o antisimétrica, o de equivalencia o de orden.

11. En un conjunto de 10 elementos, a) cuente el número de relaciones simétricas y bosqueje un procedimiento para generar a todas ellas, una a una, b) cuente el número de relaciones reflexivas y bosqueje un procedimiento para generar a todas ellas, una a una, c) cuente el número de relaciones transitivas y bosqueje un procedimiento para generar a todas ellas, una a una.

12. Sea R una relación de equivalencia y sea

$$S=\{(x,y)\vert\exists z\in S:\ (xRz)\&(zRy)\}.$$

Pruebe que S es una relación de equivalencia. Compare el índice de S con el de R.

13. Dé un ejemplo de una relación definida sobre algún conjunto que sea simétrica y transitiva mas no reflexiva.

14. Dos palabras $\sigma, \tau\in \Sigma ^*$ se dicen conjugadas si $\exists \upsilon\in \Sigma ^*:\ \sigma\upsilon= \upsilon\tau$. Pruebe que dos palabras $\sigma, \tau\in \Sigma ^*$ son conjugadas si y sólo si

$$\exists \alpha,\beta\in \Sigma ^*:\ (\sigma=\alpha\beta)\&(\tau=\beta\alpha).$$

15. Muestre que la relación de conjugación es una relación de equivalencia en el diccionario de cualquier alfabeto.

16. Muestre que si $\sigma=\alpha^n$, donde $\sigma, \alpha\in \Sigma ^*$ y $n\geq 0$, entonces cualquier conjugado de $\sigma$ es de la forma $\tau=\beta^n$, donde $\beta$ es un conjugado de $\alpha$.

17. Sea $\Sigma$ un alfabeto con m>0 símbolos. Sea $\omega:\Sigma \rightarrow [1,m]$ una enumeración de $\Sigma$. Se tiene un orden natural en $\Sigma$: $s\leq t \; \Leftrightarrow \; \omega(s) \leq \omega(t).$ a) Extendemos $\omega$ a una función $\omega^*:\Sigma^* \rightarrow I\!\!\!\!Q^+$, donde $I\!\!\!\!Q^+$ es el conjunto de números racionales positivos, haciendo

$$\begin{eqnarray*}\omega^*(\mbox{\it nil\/}) &=& 0 \\ \omega^*(s_1\cdots s_k) &=& \sum_{i=1}^k\frac{\omega(s_i)}{(m+1)^{i-1}}. \end{eqnarray*}$$

Decida si acaso $\omega^*$ es una biyección. b) Pruebe que la relación $\leq_{\omega}$ en $\Sigma^*$ definida como

$$\forall \sigma,\tau:\ \ \ \sigma\leq_{\omega}\tau \; \Leftrightarrow \; \omega^*(\sigma)\leq\omega^*(\tau),$$

es una relación de orden en $\Sigma^*$ que coincide con el orden lexicográfico inducido por $\omega$ en $\Sigma^*$. c) ¿Si se definiera $\omega^*(s_1\cdots s_k) = \sum_{i=1}^k\frac{\omega(s_i)}{(m)^{i-1}}$, podría concluirse lo mismo que en el inciso anterior ?

18. Decida cuáles de las siguientes relaciones se cumplen para cualesquiera tres lenguajes $L_1,L_2,L_3\subset \Sigma^*$:

$$\begin{eqnarray*}L_1\cap L_2 &=& L_2\cap L_1 \\ L_1(L_2\cup L_3) &=& L_1L_2\cu... ...1 L_2 &=& L_2 L_1 \\ L_1(L_2\cap L_3) &=& L_1L_2\cap L_1 L_3 \end{eqnarray*}$$

19. Sea $h:\Sigma^*\rightarrow \Sigma^*$ un homomorfismo. Decida cuáles de las siguientes relaciones se cumplen para cualesquiera dos lenguajes $L_1,L_2\subset \Sigma^*$:

$$\begin{eqnarray*}h(h(L_1)) &=& h(L_1) \\ h(L_1 L_2) &=& h(L_1)h( L_1) \\ h(L... ...h(L_1)\cap h( L_1) \\ h(L_1 \cup L_2) &=& h(L_1)\cup h( L_1) \end{eqnarray*}$$

20. Sea $h:(0+1)^*\rightarrow (0+1)^*$ el homomorfismo tal que h(0)=1,h(1)=01. Sea $f:I\!\!N\rightarrow I\!\!N$ la función $n\mapsto f(n)=\mbox{\rm long}(h^n(01))$. Dé una expresión aritmética para calcular f. Demuestre la validez de su expresión.
Siguiente: Gramáticas formales Un nivel arriba: Fundamentos matemáticos Anterior: Propiedades de cerradura