| Autor |
Mensaje |
alfred_oh
Nivel 4
Registrado: 20 Feb 2013
Mensajes: 102
|
|
Hola! Tengo que resolver este ejercicio
|
|
|
|
|
|
| |
    |
|
Huey 7
Nivel 6
Registrado: 03 Mar 2010
Mensajes: 267
Carrera: Electrónica
|
|
Ando medio oxidado con esto; supongo que la notación ![[tex]A \times B[/tex]](images/latex/669df5fbcc4b5275da99848880a9198107a83795_0.png "[tex]A \times B[/tex]") o ![[tex]A^2[/tex]](images/latex/d65b25b590dbbceae99d516e460fbd4b54c6ccc2_0.png "[tex]A^2[/tex]") es concatenación, la notación |A| es cantidad de elementos (cardinal) y la notación ![[tex]\varepsilon[/tex]](images/latex/4e36e4cc31c525ad4e2bd7eb0d72884866641126_0.png "[tex]\varepsilon[/tex]") es la cadena vacía, ¿no?
Si es así y si recuerdo bien este tema, el problema está en que no es cierto que para ![[tex]A \subseteq \Sigma^*[/tex]](images/latex/23b1c3ae2ac2e411dc868cf2ce761918846db4db_0.png "[tex]A \subseteq \Sigma^*[/tex]") y ![[tex]B \subseteq \Sigma^*[/tex]](images/latex/2b3122430690348d3562e36e121828c6327d891b_0.png "[tex]B \subseteq \Sigma^*[/tex]") , ![[tex]|A| = n \mbox{ y } |B| = m \Rightarrow |A \times B| = nm[/tex]](images/latex/1cef4747091868c1facbc9561f00b1be062bbd1c_0.png "[tex]|A| = n \mbox{ y } |B| = m \Rightarrow |A \times B| = nm[/tex]") . Lo que se cumple es ![[tex]|A \times B| \leq nm[/tex]](images/latex/99719df47f47124ef3121726c2004773c2bb7584_0.png "[tex]|A \times B| \leq nm[/tex]") . ¿Por qué? Porque dependiendo de cuáles son los elementos de A y de B, pueden haber repeticiones. La concatenación de elementos distintos de A y B puede dar el mismo resultado, que se cuenta una sola vez. Se da la igualdad ![[tex]|A \times B| = nm[/tex]](images/latex/3661dc58e2323f037243bfca9422e604370330eb_0.png "[tex]|A \times B| = nm[/tex]") si no existen repeticiones.
Por ejemplo, si ![[tex]\Sigma = \{a, b, c\}[/tex]](images/latex/a0a92458a659f5dc33b9ea907c2682f44beaf538_0.png "[tex]\Sigma = \{a, b, c\}[/tex]") , ![[tex]A = \{abc, b\}[/tex]](images/latex/3c741850e8a4ea1503c4664da87634bc8f211ac5_0.png "[tex]A = \{abc, b\}[/tex]") y ![[tex]B = \{c, ac\}[/tex]](images/latex/07fb10514916d46eda49b0d2431429f3182bf5a1_0.png "[tex]B = \{c, ac\}[/tex]") , entonces todas las concatenaciones dan resultados diferentes:
![[tex]A \times B = \{abcc, abcac, bc, bac\}[/tex]](images/latex/f6a7b9949fcafae8cc1f0b4c6b269a7fc59af05c_0.png "[tex]A \times B = \{abcc, abcac, bc, bac\}[/tex]") y ![[tex]|A \times B | = 4 = |A||B|[/tex]](images/latex/b231dfdb45a0af14db5bd7c29f61885e7e497e8f_0.png "[tex]|A \times B | = 4 = |A||B|[/tex]") .
Pero si ![[tex]A = \{abc, bb, ab\}[/tex]](images/latex/ac58cca203409d466655ba509c68dc8936e8eb87_0.png "[tex]A = \{abc, bb, ab\}[/tex]") y ![[tex]B = \{cb, ccb\}[/tex]](images/latex/0dcd3fd1d25a5ba1185784bf93eab81796356737_0.png "[tex]B = \{cb, ccb\}[/tex]") , entonces:
![[tex]A \times B = \{abccb, abcccb, bbcb, bbccb, abcb\}[/tex]](images/latex/4aefb5585ca9998b33b6b2b23cd0640ae694ee4b_0.png "[tex]A \times B = \{abccb, abcccb, bbcb, bbccb, abcb\}[/tex]") y ![[tex]|A \times B| = 5 < |A||B| = 6[/tex]](images/latex/5d6728dca88604fff5376034593e7d4ab3961885_0.png "[tex]|A \times B| = 5 < |A||B| = 6[/tex]") .
Porque tanto la concatenación de abc con cb como la concatenación de ab con ccb dan el mismo elemento, abccb. Es decir, hay una repetición.
Si ![[tex]\varepsilon \not\in A[/tex]](images/latex/37f5e53dedca012b54805309032e5d0412f968e9_0.png "[tex]\varepsilon \not\in A[/tex]") , y si ![[tex]B = A \cup \oslash^* = A \cup \{\varepsilon\}[/tex]](images/latex/45c316a67df3744b3942b6444e827dedb1ebefe7_0.png "[tex]B = A \cup \oslash^* = A \cup \{\varepsilon\}[/tex]") , es correcto que ![[tex]|B| = n + 1[/tex]](images/latex/a55e24538f469a820653b4ce05321ada9fd8e72c_0.png "[tex]|B| = n + 1[/tex]") , pero, si bien podrías decir que ![[tex]|B^2| \leq (n + 1)^2[/tex]](images/latex/b01c6d7f449f9697508e06f603d1c51be167e6c3_0.png "[tex]|B^2| \leq (n + 1)^2[/tex]") , en este caso sabés que van a haber repeticiones, porque para todo ![[tex]v \in A: \varepsilon v = v \varepsilon = v[/tex]](images/latex/cd61fb620329055b1bc89cf814ae08dc8eb2f111_0.png "[tex]v \in A: \varepsilon v = v \varepsilon = v[/tex]") , es decir, hay varios pares de concatenaciones con la cadena vacía que dan el mismo elemento de ![[tex]B^2[/tex]](images/latex/c80b43c204152f196b4c59f68d6a54ce7b4e930c_0.png "[tex]B^2[/tex]") . Esto se puede contabilizar mejor, para especificar una cota más ceñida de ![[tex]|B^2|[/tex]](images/latex/dfec6cb526bd70330bc7ee524c0ba098769fc079_0.png "[tex]|B^2|[/tex]") :
- La contatenación
![[tex]\varepsilon \varepsilon[/tex]](images/latex/33bede6db0355a6d23e6d9826f01ce7511bd6d63_0.png "[tex]\varepsilon \varepsilon[/tex]") es la única que produce , y contribuye un único elemento a .
- La concatenaciones de con cada
![[tex]v \in A[/tex]](images/latex/12c1d51314ad96920bf4b6f61c2afdb7eedd0204_0.png "[tex]v \in A[/tex]") (ninguno de los cuales es la cadena vacía por hipótesis), en cualquier orden, producen v, y contribuyen n elementos distintos de a .
- La concatenaciones de cada con cada
![[tex]w \in A[/tex]](images/latex/016d4c17897a634be6097cd1003ec2944e44e55f_0.png "[tex]w \in A[/tex]") contribuyen como máximo ![[tex]n^2[/tex]](images/latex/60dd8ed239f15b8f26fdcda28625216b8f6f100c_0.png "[tex]n^2[/tex]") elementos adicionales vw distintos de a . Serán exactamente elementos adicionales si no hay repeticiones y si ninguna concatenación vw vuelve a dar un elemento de A (como ocurriría si ![[tex]A = \{ab, a, b\}[/tex]](images/latex/43c0f116c45b58b5906cb1cb8fc168806ab20da1_0.png "[tex]A = \{ab, a, b\}[/tex]") ), y menos en caso contrario.
Entonces, lo que podés decir es que ![[tex]|B^2| \leq n^2 + n + 1[/tex]](images/latex/30982fed1008050a8231d488fb94b9da0b42961a_0.png "[tex]|B^2| \leq n^2 + n + 1[/tex]") . La igualdad valdrá si las concatenaciones de dos elementos de A son todas distintas entre ellas y con elementos de A.
|
|
|
|
_________________
|
|
 |
|
|
|
|
|
Ver tema siguiente
Ver tema anterior
Podés publicar nuevos temas en este foro
No podés responder a temas en este foro
No podés editar tus mensajes en este foro
No podés borrar tus mensajes en este foro
No podés votar en encuestas en este foro
No Podéspostear archivos en este foro
No Podés bajar archivos de este foro
|
Todas las horas son ART, ARST (GMT - 3, GMT - 2 Horas)
Protected by CBACK CrackerTracker365 Attacks blocked.
|
|
|
[ Tiempo: 0.8864s ][ Pedidos: 20 (0.7863s) ] |
