next up previous contents
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{displaymath}\begin{array}{rrcl}
\mbox{\it i.\/} & x*y &=& \mathop{\rm Ma...
...op{\rm Min}\{x,y\}\geq 10$. }
\end{array}\right.
\end{array}\end{displaymath}



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

\begin{displaymath}\forall x,y\in S:\ \ \ x*y=x.\end{displaymath}

Muestre que * es una operación asociativa.

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

\begin{displaymath}\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}\end{displaymath}

Muestre que entonces se cumple la relación

\begin{displaymath}\forall x,y,z:\ \ \ x*(y*z) = (x*y)*(x*z).\end{displaymath}

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

\begin{displaymath}\forall x,y:\ \ \ x\bullet y= x*a*y.\end{displaymath}

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,

\begin{displaymath}\exists a\in S:\ \ \ a*a=a.\end{displaymath}



7. Sea n>1 un entero positivo. Para cada entero x sea $\mbox{\rm long}_n(x)$ el mínimo entero k tal que nk>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,

\begin{displaymath}\forall x,y:\ \ xTy\,\Leftrightarrow\,(xRy)\&(xSy).\end{displaymath}

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,

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

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,

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

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

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

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

\begin{displaymath}\exists \alpha,\beta\in \Sigma ^*:\ (\sigma=\alpha\beta)\&(\tau=\beta\alpha).\end{displaymath}



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

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

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.
next up previous contents
Siguiente: Gramáticas formales Un nivel arriba: Fundamentos matemáticos Anterior: Propiedades de cerradura
Guillermo Morales-Luna
2000-06-27