Operaciones con cadenas

En informática , específicamente en el área de la teoría de lenguajes formales , se utilizan con frecuencia diversas funciones de cadena ; sin embargo, la notación empleada difiere de la utilizada en la programación , y algunas funciones comunes en el ámbito teórico rara vez se emplean en la programación. Este artículo define algunos de estos términos básicos.

Una cadena es una secuencia finita de caracteres. La cadena vacía se denota por${\displaystyle \varepsilon }$La concatenación de dos cadenas${\displaystyle s}$y${\displaystyle t}$se denota por${\displaystyle s\cdot t}$, o más corto por${\displaystyle st}$Concatenar con la cadena vacía no supone ninguna diferencia:${\displaystyle s\cdot \varepsilon =s=\varepsilon \cdot s}$La concatenación de cadenas es asociativa :${\displaystyle s\cdot (t\cdot u)=(s\cdot t)\cdot u}$.

Por ejemplo,${\displaystyle (\langle b\rangle \cdot \langle l\rangle )\cdot (\varepsilon \cdot \langle ah\rangle )=\langle bl\rangle \cdot \langle ah\rangle =\langle blah\rangle }$.

Un lenguaje es un conjunto finito o infinito de cadenas. Además de las operaciones de conjuntos habituales como la unión, la intersección, etc., la concatenación se puede aplicar a los lenguajes: si ambos${\displaystyle S}$y${\displaystyle T}$son los lenguajes, su concatenación${\displaystyle S\cdot T}$se define como el conjunto de concatenaciones de cualquier cadena de${\displaystyle S}$y cualquier cadena de${\displaystyle T}$formalmente${\displaystyle S\cdot T=\{s\cdot t\mid s\in S\land t\in T\}}$. Nuevamente, el punto de concatenación${\displaystyle \cdot }$A menudo se omite por brevedad.

El idioma${\displaystyle \{\varepsilon \}}$Consistir únicamente en la cadena vacía debe distinguirse del lenguaje vacío.${\displaystyle \{\}}$Concatenar cualquier idioma con el anterior no produce ningún cambio:${\displaystyle S\cdot \{\varepsilon \}=S=\{\varepsilon \}\cdot S}$, mientras que al concatenar con este último siempre se obtiene el lenguaje vacío:${\displaystyle S\cdot \{\}=\{\}=\{\}\cdot S}$La concatenación de lenguajes es asociativa:${\displaystyle S\cdot (T\cdot U)=(S\cdot T)\cdot U}$.

Por ejemplo, abreviar${\displaystyle D=\{\langle 0\rangle ,\langle 1\rangle ,\langle 2\rangle ,\langle 3\rangle ,\langle 4\rangle ,\langle 5\rangle ,\langle 6\rangle ,\langle 7\rangle ,\langle 8\rangle ,\langle 9\rangle \}}$, el conjunto de todos los números decimales de tres dígitos se obtiene como${\displaystyle D\cdot D\cdot D}$El conjunto de todos los números decimales de longitud arbitraria es un ejemplo de lenguaje infinito.

El alfabeto de una cadena es el conjunto de todos los caracteres que aparecen en una cadena particular. Si s es una cadena, su alfabeto se denota por

${\displaystyle \operatorname {Alph} (s)}$

El alfabeto de un idioma${\displaystyle S}$es el conjunto de todos los caracteres que aparecen en cualquier cadena de${\displaystyle S}$, formalmente: ${\displaystyle \operatorname {Alph} (S)=\bigcup _{s\in S}\operatorname {Alph} (s)}$.

Por ejemplo, el conjunto${\displaystyle \{\langle a\rangle ,\langle c\rangle ,\langle o\rangle \}}$es el alfabeto de la cadena${\displaystyle \langle cacao\rangle }$y lo anterior${\displaystyle D}$es el alfabeto del idioma mencionado anteriormente${\displaystyle D\cdot D\cdot D}$así como del lenguaje de todos los números decimales.

Sea L un lenguaje y Σ su alfabeto. Una sustitución de cadenas , o simplemente una sustitución , es una función f que asigna caracteres de Σ a lenguajes (posiblemente con un alfabeto diferente). Así, por ejemplo, dado un carácter a ∈ Σ, se tiene f ( a )= L _a donde L _a ⊆ Δ ^* es algún lenguaje cuyo alfabeto es Δ. Esta función puede extenderse a cadenas como

f (ε)=ε

para la cadena vacía ε, y

f ( sa )= f ( s ) f ( a )

para cadena s ∈ L y carácter a ∈ Σ. Las sustituciones de cadenas pueden extenderse a lenguajes completos como ^{[ 1 ].}

${\displaystyle f(L)=\bigcup _{s\in L}f(s)}$

Los lenguajes regulares son cerrados bajo la sustitución de cadenas. Es decir, si cada carácter del alfabeto de un lenguaje regular se sustituye por otro lenguaje regular, el resultado sigue siendo un lenguaje regular. ^{[ 2 ]} De manera similar, los lenguajes libres de contexto son cerrados bajo la sustitución de cadenas. ^{[ 3 ] [ nota 1 ]}

Un ejemplo sencillo es la conversión de f _uc (.) a mayúsculas, que puede definirse, por ejemplo, de la siguiente manera:

Para la extensión de f _uc a cadenas, tenemos, por ejemplo:

• f _uc (‹Straße›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹STRASSE›},
• f _uc (‹u2›) = {‹U›} ⋅ {ε} = {‹U›}, y
• f _uc (‹¡Vamos!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}.

Para la extensión de f _uc a los idiomas, tenemos, por ejemplo:

• f _uc ({ ‹Straße›, ‹u2›, ‹Go!› }) = { ‹STRASSE› } ∪ { ‹U› } ∪ { } = { ‹STRASSE›, ‹U› }.

Un homomorfismo de cadenas (a menudo denominado simplemente homomorfismo en la teoría del lenguaje formal ) es una sustitución de cadenas tal que cada carácter se reemplaza por una sola cadena. Es decir,${\displaystyle f(a)=s}$, dónde${\displaystyle s}$es una cadena, para cada carácter${\displaystyle a}$. ^{[ nota 2 ] [ 4 ]}

Los homomorfismos de cadenas son morfismos de monoides en el monoide libre , que preservan la cadena vacía y la operación binaria de concatenación de cadenas . Dado un lenguaje${\displaystyle L}$, el conjunto${\displaystyle f(L)}$se llama la imagen homomórfica de${\displaystyle L}$La imagen homomórfica inversa de una cadena${\displaystyle s}$se define como

${\displaystyle f^{-1}(s)=\{w\mid f(w)=s\}}$

mientras que la imagen homomórfica inversa de un lenguaje${\displaystyle L}$se define como

${\displaystyle f^{-1}(L)=\{s\mid f(s)\in L\}}$

En general,${\displaystyle f(f^{-1}(L))\neq L}$, mientras que uno sí tiene

${\displaystyle f(f^{-1}(L))\subseteq L}$

y

${\displaystyle L\subseteq f^{-1}(f(L))}$

para cualquier idioma${\displaystyle L}$.

La clase de lenguajes regulares es cerrada bajo homomorfismos y homomorfismos inversos. ^{[ 5 ]} De manera similar, los lenguajes libres de contexto son cerrados bajo homomorfismos ^{[ nota 3 ]} y homomorfismos inversos. ^{[ 6 ]}

Se dice que un homomorfismo de cadenas es ε-libre (o e-libre) si${\displaystyle f(a)\neq \varepsilon }$para todas las a en el alfabeto${\displaystyle \Sigma }$Los cifrados simples de sustitución de una sola letra son ejemplos de homomorfismos de cadenas (libres de ε).

Un ejemplo de homomorfismo de cadenas g _uc también se puede obtener definiendo de forma similar a la sustitución anterior : g _uc (‹a›) = ‹A›, ..., g _uc (‹0›) = ε, pero dejando g _uc indefinido en caracteres de puntuación. Ejemplos de imágenes homomórficas inversas son

• g _uc ⁻¹ ({ ‹SSS› }) = { ‹sss›, ‹sß›, ‹ßs› }, ya que g _uc (‹sss›) = g _uc (‹sß›) = g _uc (‹ßs›) = ‹SSS›, y
• g _uc ⁻¹ ({ ‹A›, ‹bb› }) = { ‹a› }, ya que g _uc (‹a›) = ‹A›, mientras que ‹bb› no puede ser alcanzado por g _uc .

Para este último lenguaje, g _uc ( g _uc ⁻¹ ({ ‹A›, ‹bb› })) = g _uc ({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› }. El homomorfismo g _uc no es ε-libre, ya que mapea eg ‹0› a ε.

Un ejemplo muy simple de homomorfismo de cadenas que asigna cada carácter a un solo carácter es la conversión de una cadena codificada en EBCDIC a ASCII .

Si s es una cadena, y${\displaystyle \Sigma }$es un alfabeto, la proyección de cadena de s es la cadena que resulta de eliminar todos los caracteres que no están en${\displaystyle \Sigma }$. Está escrito como${\displaystyle \pi _{\Sigma }(s)\,}$Se define formalmente eliminando caracteres del lado derecho:

${\displaystyle \pi _{\Sigma }(s)={\begin{cases}\varepsilon &{\mbox{if }}s=\varepsilon {\mbox{ the empty string}}\\\pi _{\Sigma }(t)&{\mbox{if }}s=ta{\mbox{ and }}a\notin \Sigma \\\pi _{\Sigma }(t)a&{\mbox{if }}s=ta{\mbox{ and }}a\in \Sigma \end{cases}}}$

Aquí${\displaystyle \varepsilon }$denota la cadena vacía . La proyección de una cadena es esencialmente lo mismo que una proyección en álgebra relacional .

La proyección de cadenas puede promoverse a la proyección de un lenguaje . Dado un lenguaje formal L , su proyección viene dada por

${\displaystyle \pi _{\Sigma }(L)=\{\pi _{\Sigma }(s)\ \vert \ s\in L\}}$

El cociente derecho de un carácter a de una cadena s es la truncación del carácter a en la cadena s , desde el lado derecho. Se denota como${\displaystyle s/a}$Si la cadena no tiene un carácter en el lado derecho, el resultado es una cadena vacía. Por lo tanto:

${\displaystyle (sa)/b={\begin{cases}s&{\mbox{if }}a=b\\\varepsilon &{\mbox{if }}a\neq b\end{cases}}}$

Se puede tomar el cociente de la cadena vacía:

${\displaystyle \varepsilon /a=\varepsilon }$

De manera similar, dado un subconjunto${\displaystyle S\subset M}$de un monoide${\displaystyle M}$, se puede definir el subconjunto cociente como

${\displaystyle S/a=\{s\in M\ \vert \ sa\in S\}}$

Los cocientes izquierdos pueden definirse de forma similar, realizando las operaciones en el lado izquierdo de una cadena.

Hopcroft y Ullman (1979) definen el cociente L ₁ / L ₂ de los lenguajes L ₁ y L ₂ sobre el mismo alfabeto como L ₁ / L ₂ = { s | ∃ t ∈ L ₂ . st ∈ L ₁ } . ^{[ 7 ]} Esto no es una generalización de la definición anterior, ya que, para una cadena s y caracteres distintos a , b , la definición de Hopcroft y Ullman implicalo que produce {} , en lugar de { ε } .

El cociente izquierdo (cuando se define de forma similar a Hopcroft y Ullman 1979) de un lenguaje unitario L ₁ y un lenguaje arbitrario L ₂ se conoce como derivada de Brzozowski ; si L ₂ se representa mediante una expresión regular , también puede ser el cociente izquierdo. ^{[ 8 ]}

El cociente derecho de un subconjunto${\displaystyle S\subset M}$de un monoide${\displaystyle M}$define una relación de equivalencia , llamada relación sintáctica derecha de S. Está dada por

${\displaystyle \sim _{S}\;\,=\,\{(s,t)\in M\times M\ \vert \ S/s=S/t\}}$

La relación es claramente de índice finito (tiene un número finito de clases de equivalencia) si y solo si la familia de cocientes derechos es finita; es decir, si

${\displaystyle \{S/m\ \vert \ m\in M\}}$

es finito. En el caso de que M sea el monoide de palabras sobre algún alfabeto, S es entonces un lenguaje regular , es decir, un lenguaje que puede ser reconocido por un autómata de estados finitos . Esto se analiza con mayor detalle en el artículo sobre monoides sintácticos .

La cancelación derecha de un carácter a de una cadena s es la eliminación de la primera aparición del carácter a en la cadena s , comenzando desde el lado derecho. Se denota como${\displaystyle s\div a}$y se define recursivamente como

${\displaystyle (sa)\div b={\begin{cases}s&{\mbox{if }}a=b\\(s\div b)a&{\mbox{if }}a\neq b\end{cases}}}$

La cadena vacía siempre se puede cancelar:

${\displaystyle \varepsilon \div a=\varepsilon }$

Claramente, cancelación correcta y desplazamiento por proyección :

${\displaystyle \pi _{\Sigma }(s)\div a=\pi _{\Sigma }(s\div a)}$

Los prefijos de una cadena son el conjunto de todos los prefijos de una cadena, con respecto a un lenguaje dado:

${\displaystyle \operatorname {Pref} _{L}(s)=\{t\ \vert \ s=tu{\mbox{ for }}t,u\in \operatorname {Alph} (L)^{*}\}}$

dónde${\displaystyle s\in L}$.

El cierre de prefijo de un lenguaje es

${\displaystyle \operatorname {Pref} (L)=\bigcup _{s\in L}\operatorname {Pref} _{L}(s)=\left\{t\ \vert \ s=tu;s\in L;t,u\in \operatorname {Alph} (L)^{*}\right\}}$

Ejemplo:${\displaystyle L=\left\{abc\right\}{\mbox{ then }}\operatorname {Pref} (L)=\left\{\varepsilon ,a,ab,abc\right\}}$

Un lenguaje se denomina prefijo cerrado si${\displaystyle \operatorname {Pref} (L)=L}$.

El operador de cierre de prefijo es idempotente :

${\displaystyle \operatorname {Pref} (\operatorname {Pref} (L))=\operatorname {Pref} (L)}$

La relación de prefijo es una relación binaria.${\displaystyle \sqsubseteq }$de tal manera que${\displaystyle s\sqsubseteq t}$si y solo si${\displaystyle s\in \operatorname {Pref} _{L}(t)}$Esta relación es un ejemplo particular de un orden de prefijo .

• Comparación de lenguajes de programación (funciones de cadena)
• El lema de Levi
• Cadenas de caracteres (informática) : definición e implementación de operaciones más básicas con cadenas de caracteres.

• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introducción a la teoría de autómatas, lenguajes y computación . Reading, Massachusetts: Addison-Wesley Publishing. ISBN 978-0-201-02988-8. Zbl 0426.68001 . (Véase el capítulo 3.)