Operaciones de cadena

En informática , en el área de la teoría del lenguaje formal , se hace uso frecuente de una variedad de funciones de cadena ; sin embargo, la notación utilizada es diferente de la utilizada para la programación de computadoras , y algunas funciones comúnmente utilizadas en el ámbito teórico rara vez se usan al programar. Este artículo define algunos de estos términos básicos.

Cadenas e idiomas

Una cadena es una secuencia finita de caracteres. La cadena vacía se indica con . La concatenación de dos cadenas y se denota por , o más brevemente por . Concatenar 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 idiomas: si ambos y son idiomas, 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 a menudo se omite por motivos 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 consta únicamente de una cadena vacía debe distinguirse del lenguaje vacío . Concatenar cualquier idioma con el primero no genera ningún cambio: , mientras que concatenar con el segundo siempre produce el idioma vacío: . La concatenación de lenguas 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, abreviando , el conjunto de todos los números decimales de tres cifras 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 en particular. 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 sea Σ su alfabeto. Una sustitución de cadena o simplemente una sustitución es una asignació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 Δ. Este mapeo 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 se pueden extender a idiomas completos como ^[1]

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

Los lenguajes regulares se cierran bajo sustitución de cadenas. Es decir, si cada carácter del alfabeto de un idioma normal se sustituye por otro idioma normal, el resultado sigue siendo un idioma normal. ^[2] De manera similar, los lenguajes libres de contexto se cierran bajo 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 cuerdas, 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 idiomas, 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 se reemplaza por una sola cadena. Es decir, donde hay una cadena para cada carácter . ^{[nota 2] [4]} ${\displaystyle f(a)=s}$ ${\displaystyle s}$ ${\displaystyle a}$

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

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

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

${\displaystyle f^{-1}(L)=\{s|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 lenguas 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 cadena es libre de ε (o libre de e) si es para todo a en el alfabeto . Los cifrados de sustitución de una sola letra simples son ejemplos de homomorfismos de cadenas (libres de ε). ${\displaystyle f(a)\neq \varepsilon }$ ${\displaystyle \Sigma }$

También se puede obtener un ejemplo de homomorfismo de cadena 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 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 idioma, g _uc ( g _uc ⁻¹ ({ ‹A›, ‹bb› })) = g _uc ({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› } . El homomorfismo g _uc no está libre de ε, ya que asigna, por ejemplo, ‹0› a ε.

Un ejemplo de homomorfismo de cadena muy simple que asigna cada carácter a solo un carácter es la conversión de una cadena codificada con 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 . Está escrito como . Se define formalmente eliminando los 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í denota la cadena vacía . La proyección de una cuerda es esencialmente la misma que una proyección en álgebra relacional . ${\displaystyle \varepsilon }$

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

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

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. De este modo: ${\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, realizando operaciones a la izquierda de una cadena. ^{[ cita necesaria ]}

Hopcroft y Ullman (1979) definen el cociente L ₁ / L ₂ de las lenguas L ₁ y L ₂ sobre el mismo alfabeto como L ₁ / L ₂ = { s | ∃ t ∈ L ₂ . st ∈ L ₁ } . ^[7] Esta 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 manera 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. esta dado 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 los cocientes de derechos familiares son finitos; 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 necesaria ]}

Cancelación del derecho

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 es cancelable:

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

Claramente, cancelación correcta y conmutación de proyección :

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

Prefijos

Los prefijos de una cadena es 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 cerrado de un idioma 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 orden de prefijo . ^{[ cita necesaria ]} ${\displaystyle \sqsubseteq }$ ${\displaystyle s\sqsubseteq t}$ ${\displaystyle s\in \operatorname {Pref} _{L}(t)}$

Ver también

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

Notas

1. Aunque todo lenguaje regular también está libre de contexto, el teorema anterior no está implícito en el actual, ya que el primero produce un resultado más modelador para los lenguajes regulares.
2. Estrictamente formalmente, un homomorfismo produce un lenguaje que consta de 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, los Lenguajes y la Computación de Autómatas . Reading, Massachusetts: Addison-Wesley Publishing. ISBN 978-0-201-02988-8. Zbl  0426.68001. (Ver capítulo 3.)

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