Operaciones de cadena

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

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 corto 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 idioma es un conjunto finito o infinito de cadenas. Además de las operaciones de conjuntos habituales como unión, intersección, etc., la concatenación se puede aplicar a los lenguajes: si ambos 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 a menudo se omite por 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}$