9.6: Alfabetos y palabras
- Page ID
- 118183
cualquier conjunto puede considerarse un alfabeto
los elementos de un conjunto de alfabeto
una lista ordenada de letras de longitud finita
el conjunto de palabras usando alfabeto conjunto\(\Sigma\)
Incluso si el conjunto del alfabeto\(\Sigma\) es el alfabeto habitual en inglés, no nos limitamos a palabras reales en inglés; se permiten palabras sin sentido.
Uso de\(\Sigma = \Sigma = \{a, b, \ldots, y, z\} \text{,}\) palabras
\ begin {ecuation*}\ mathrm {math},\;\ mathrm {qwerty},\;\ mathrm {aabbccddijzuuu}\ end {equation*}
son ejemplos de elementos en\(\Sigma^{\ast}\text{.}\) Entonces, ignorando la puntuación, la división de palabras y las mayúsculas, el idioma inglés es un subconjunto apropiado de\(\Sigma^{\ast}\text{.}\)
Usando el alfabeto\(\Sigma = \{ 0,\, 1,\, 2,\, \dotsc,\, 9 \}\text{,}\) entonces\(\mathbb{N} \subsetneqq \Sigma^{\ast}\text{.}\)
¿Por qué está\(\mathbb{N} \neq \Sigma^{\ast}\) en Ejemplo\(\PageIndex{2}\)?
En la informática, un cierto conjunto de palabras es de particular importancia.
una palabra usando alfabeto\(\{0,1\}\)
sinónimo de palabra binaria
¡El orden importa! Por ejemplo, usando el alfabeto
\ begin {ecuación*}\ Sigma =\ {a, b,\ ldots, y, z\}\ text {,}\ end {ecuación*}
las palabras\(\mathrm{ab}\) y\(\mathrm{ba}\) son palabras diferentes en\(\Sigma^{\ast}\text{.}\)
dada\(w \in \Sigma^{\ast}\text{,}\) la longitud de\(w\) es el número de elementos\(\Sigma\) utilizados para formar repetición de\(w\text{,}\) conteo
longitud de la palabra\(w \in \Sigma^{\ast}\)
Usando el alfabeto\(\Sigma = \Sigma = \{a, b, \ldots, y, z\}\text{,}\) tenemos
\ begin {align*}\ vert\ mathrm {qwerty}\ vert & = 6\ text {,} &\ vert\ mathrm {aabab}\ vert & = 5\ text {.} \ end {align*}
El concepto de longitud nos permite identificar algunos subconjuntos especiales y un elemento especial de\(\Sigma^{\ast}\text{.}\)
para\(n \in \mathbb{N}\text{,}\) el subconjunto de\(\Sigma\) que consta de todas las palabras de longitud\(n\)
dado un alfabeto siempre\(\Sigma\text{,}\) consideramos\(\Sigma^{\ast}\) que contiene una palabra única de longitud\(0\)
la palabra vacía