operaciones de cadena

En ciencias de la computación , 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 de uso común en el ámbito teórico rara vez se usan cuando se programa. 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 . La concatenación de dos cadenas y se denota por , o más corta por . Concatenar con la cadena vacía no hace ninguna diferencia: . La concatenación de cadenas es asociativa : . ${\ estilo de visualización \ varepsilon}$ ${\ estilo de visualización}$ ${\ estilo de visualización t}$ $s\cdot t$ ${\ Displaystyle st}$ $s\cdot \varepsilon =s=\varepsilon \cdot s$ $s\cdot (t\cdot u)=(s\cdot t)\cdot u$

Por ejemplo, . $(\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 habituales de conjuntos 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 desde y cualquier cadena desde , formalmente . Nuevamente, el punto de concatenación a menudo se omite por brevedad. ${\ estilo de visualización S}$ ${\ estilo de visualización T}$ $S\cdot T$ ${\ estilo de visualización S}$ ${\ estilo de visualización T}$ $S\cdot T=\{s\cdot t\mid s\in S\land t\in T\}$ ${\ estilo de visualización \ cdot}$