Operaciones con cadenas

En informática , en el área de teoría de lenguajes formales , se utilizan con frecuencia diversas funciones de cadena ; sin embargo, la notación utilizada es diferente a la que se utiliza en programación informática , y algunas funciones de uso común en el ámbito teórico rara vez se utilizan en la programación. En este artículo se definen algunos de estos términos básicos.

Cadenas y lenguajes

Una cadena es una secuencia finita de caracteres. La cadena vacía se denota por . La concatenación de dos cadenas y se denota por , o más corta por . La concatenación con la cadena vacía no hace ninguna diferencia: . La concatenación de cadenas es asociativa : . ${\displaystyle \varepsilon }$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s\cdot t}$ ${\displaystyle st}$ ${\displaystyle s\cdot \varepsilon =s=\varepsilon \cdot s}$ ${\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 conjunto habituales, como unión, intersección, etc., la concatenación se puede aplicar a los lenguajes: si tanto y son lenguajes, su concatenación se define como el conjunto de concatenaciones de cualquier cadena de y cualquier cadena de , formalmente . Nuevamente, el punto de concatenación se omite a menudo por razones de brevedad. ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S\cdot T}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S\cdot T=\{s\cdot t\mid s\in S\land t\in T\}}$ ${\displaystyle \cdot }$

El lenguaje que consiste únicamente en la cadena vacía debe distinguirse del lenguaje vacío . La concatenación de cualquier lenguaje con el primero no produce ningún cambio: , mientras que la concatenación con el segundo siempre produce el lenguaje vacío: . La concatenación de lenguajes es asociativa: . ${\displaystyle \{\varepsilon \}}$ ${\displaystyle \{\}}$ ${\displaystyle S\cdot \{\varepsilon \}=S=\{\varepsilon \}\cdot S}$ ${\displaystyle S\cdot \{\}=\{\}=\{\}\cdot S}$ ${\displaystyle S\cdot (T\cdot U)=(S\cdot T)\cdot U}$

Por ejemplo, al abreviar , el conjunto de todos los números decimales de tres dígitos se obtiene como . El conjunto de todos los números decimales de longitud arbitraria es un ejemplo de un lenguaje infinito. ${\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 \}}$ ${\displaystyle D\cdot D\cdot D}$

Alfabeto de una cadena

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

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

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

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

Sustitución de cadenas

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

f (ε)=ε

para la cadena vacía ε, y

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

para la cadena s ∈ L y el carácter a ∈ Σ. Las sustituciones de cadenas se pueden extender a idiomas enteros como ^[1]

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

Los lenguajes regulares están cerrados a 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 están cerrados a 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 lenguajes, tenemos por ejemplo

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

Homomorfismo de cuerdas

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 es reemplazado por una sola cadena. Es decir, , donde es una cadena, para cada carácter . ^{[nota 2] [4]} ${\displaystyle f(a)=s}$ ${\displaystyle s}$ ${\displaystyle a}$

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

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

Mientras que la imagen homomórfica inversa de una lengua se define como ${\displaystyle L}$

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

En general, si bien uno tiene ${\displaystyle f(f^{-1}(L))\neq L}$

${\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 está cerrada bajo homomorfismos y homomorfismos inversos. ^[5] De manera similar, los lenguajes libres de contexto están cerrados bajo homomorfismos ^{[nota 3]} y homomorfismos inversos. ^[6]

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

También se puede obtener un ejemplo de homomorfismo de cadenas g _uc definiendo una sustitución similar a la anterior: g _uc (‹a›) = ‹A›, ..., g _uc (‹0›) = ε, pero dejando que g _uc no esté definido en los 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 el último lenguaje, g _uc ( g _uc ⁻¹ ({ ‹A›, ‹bb› })) = g _uc ({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› }. El homomorfismo g _uc no es ε-libre, ya que asigna, por ejemplo, ‹0› a ε.

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

Proyección de cuerdas

Si s es una cadena y 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 . Se escribe como . Se define formalmente mediante la eliminación de caracteres del lado derecho: ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle \pi _{\Sigma }(s)\,}$

${\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í se denota la cadena vacía . La proyección de una cadena es esencialmente la misma que una proyección en álgebra relacional . ${\displaystyle \varepsilon }$

La proyección de cadenas puede convertirse en la proyección de un lenguaje . Dado un lenguaje formal L , su proyección está dada por

${\displaystyle \pi _{\Sigma }(L)=\{\pi _{\Sigma }(s)\ \vert \ s\in L\}}$^{[ cita requerida ]}

Cociente derecho e izquierdo

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

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

El cociente de la cadena vacía se puede tomar:

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

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

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

Los cocientes izquierdos se pueden definir de manera similar, con operaciones que tienen lugar a la izquierda de una cadena. ^{[ cita requerida ]}

Hopcroft y Ullman (1979) definen el cociente L ₁ / L ₂ de los idiomas 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 implicaproduciendo {}, en lugar de { ε }.

El cociente izquierdo (cuando se define de forma similar a Hopcroft y Ullman 1979) de un lenguaje singleton L ₁ y un lenguaje arbitrario L ₂ se conoce como derivada de Brzozowski ; si L ₂ está representado por una expresión regular , también puede serlo el cociente izquierdo. ^[8]

Relación sintáctica

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

${\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 sólo si el cociente de derechos de la familia es finito; 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 . ^{[ cita requerida ]}

Derecho de cancelación

La cancelación correcta 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 y se define recursivamente como ${\displaystyle s\div a}$

${\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, la cancelación correcta y la proyección conmutan :

${\displaystyle \pi _{\Sigma }(s)\div a=\pi _{\Sigma }(s\div a)}$^{[ cita requerida ]}

Prefijos

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

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

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

El prefijo de cierre de una lengua 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 idioma se llama 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 tal que si y sólo si . Esta relación es un ejemplo particular de un orden de prefijo . ^{[ cita requerida ]} ${\displaystyle \sqsubseteq }$ ${\displaystyle s\sqsubseteq t}$ ${\displaystyle s\in \operatorname {Pref} _{L}(t)}$

Véase también

• Comparación de lenguajes de programación (funciones de cadena)
• Lema de Levi
• Cadenas (informática) : definición e implementación de operaciones más básicas en cadenas

Notas

1. Aunque cada lenguaje regular también es libre de contexto, el teorema anterior no está implícito en el actual, ya que el primero produce un resultado modelador para los lenguajes regulares.
2. Estrictamente formalmente, un homomorfismo produce un lenguaje que consiste en una sola cadena, es decir . ${\displaystyle f(a)=\{s\}}$
3. Esto se desprende del cierre mencionado anteriormente bajo sustituciones arbitrarias.

Referencias

• 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.)

1. Hopcroft, Ullman (1979), Sección 3.2, pág. 60
2. Hopcroft, Ullman (1979), Sección 3.2, Teorema 3.4, pág. 60
3. Hopcroft, Ullman (1979), Sección 6.2, Teorema 6.2, pág. 131
4. Hopcroft, Ullman (1979), Sección 3.2, págs. 60-61
5. Hopcroft, Ullman (1979), Sección 3.2, Teorema 3.5, pág. 61
6. Hopcroft, Ullman (1979), Sección 6.2, Teorema 6.3, pág. 132
7. Hopcroft, Ullman (1979), Sección 3.2, pág. 62
8. Janusz A. Brzozowski (1964). "Derivadas de expresiones regulares". J ACM . 11 (4): 481–494. doi : 10.1145/321239.321249 . S2CID  14126942.