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 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 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 . Concatenando con la cadena vacía no hace ninguna diferencia: . Concatenación de cadenas es asociativa : .
Por ejemplo ,.
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.
El idioma que consiste solo en la cadena vacía debe distinguirse del idioma vacío . La concatenación de cualquier idioma con el que el primero no hacer ningún cambio: mientras que la concatenación con este último siempre produce el lenguaje vacío: . Concatenación de idiomas es asociativa: .
Por ejemplo, abreviando , 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.
El alfabeto de una cadena es el conjunto de todos los caracteres que ocurren en una cadena en particular. Si s es una cadena, su alfabeto se denota por
El alfabeto de una lengua es el conjunto de todos los caracteres que se producen en cualquier cadena de , formalmente: .
Por ejemplo, el conjunto es el alfabeto de la cadena y lo anterior es el alfabeto del idioma anterior , así como el idioma de todos los números decimales.
Sea L un idioma y Σ su alfabeto. Una sustitución de cadena o simplemente una sustitución es un mapeo f que mapea caracteres en Σ a idiomas (posiblemente en un alfabeto diferente). Así, por ejemplo, dado un carácter a ∈ Σ, uno tiene f ( a ) = L a donde L a ⊆ Δ * es algún idioma cuyo alfabeto es Δ. Este mapeo puede extenderse a cadenas como
para la cadena vacía ε, y
para la cadena s ∈ L y el carácter a ∈ Σ. Las sustituciones de cadenas se pueden extender a idiomas completos como [1]
Los lenguajes regulares se cierran bajo sustitución de cadenas. Es decir, si cada carácter del alfabeto de un idioma regular se sustituye por otro idioma regular, el resultado sigue siendo un idioma regular. [2] De manera similar, los lenguajes libres de contexto se cierran bajo sustitución de cadenas. [3] [nota 1]
Un ejemplo simple es la conversión f uc (.) A mayúsculas, que se puede definir, por ejemplo, de la siguiente manera:
personaje | mapeado al idioma | observación |
---|---|---|
X | f uc ( x ) | |
< Un > | {< A >} | Asignar caracteres en minúscula al carácter en mayúsculas correspondiente |
< Un > | {< A >} | mapear caracteres en mayúsculas a sí mismo |
‹ Ss › | {‹ SS ›} | no hay caracteres en mayúsculas disponibles, se asignan a una cadena de dos caracteres |
‹0› | {ε} | Asignar dígito a cadena vacía |
‹!› | {} | prohibir la puntuación, mapear a un idioma vacío |
... | similar para otros caracteres |
Para la extensión de f uc a cadenas, tenemos, por ejemplo,
Para la extensión de f uc a idiomas, tenemos, por ejemplo,
Un homomorfismo de cadena (a menudo denominado simplemente homomorfismo en la teoría del lenguaje formal ) es una sustitución de cadena de modo que cada carácter es reemplazado por una sola cadena. Es decir, donde hay una cadena para cada carácter . [nota 2] [4]
Los homomorfismos de cadena son morfismos de monoide en el monoide libre , conservando la cadena vacía y la operación binaria de concatenación de cadenas . Dado un idioma , el conjunto se denomina imagen homomórfica de . La imagen homomórfica inversa de una cadena se define como
mientras que la imagen homomórfica inversa de una lengua se define como
En general, si bien uno tiene
y
para cualquier idioma .
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 cadena está libre de ε (o libre de e) si es para todo a en el alfabeto . Los cifrados de sustitución de una sola letra son ejemplos de homomorfismos de cadenas (libres de ε).
También se puede obtener un ejemplo de homomorfismo de cadenas g uc definiendo similar a la sustitución 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
Para el último idioma, g uc ( g uc −1 ({‹A›, ‹bb›})) = g uc ({‹a›}) = {‹A›} ≠ {‹A›, ‹bb›} . El homomorfismo g uc no está libre de ε, ya que mapea, por ejemplo, ‹0› a ε.
Un ejemplo de homomorfismo de cadena muy simple 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 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 mediante la eliminación de caracteres del lado derecho:
Aquí denota la cadena vacía . La proyección de una cuerda es esencialmente la misma que una proyección en álgebra relacional .
La proyección de cuerdas se puede promover a la proyección de un lenguaje . Dado un lenguaje formal L , su proyección viene dada por
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 un en el lado derecho, el resultado es la cadena vacía. Por lo tanto:
El cociente de la cadena vacía se puede tomar:
De manera similar, dado un subconjunto de un monoide , se puede definir el subconjunto del cociente como
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 1 / L 2 de las lenguas L 1 y L 2 sobre el mismo alfabeto que L 1 / L 2 = { s | ∃ t ∈ L 2 . st ∈ L 1 }. [7] Esta no es una generalización de la definición anterior, ya que, para una cadena sy caracteres distintos a , b , la definición de Hopcroft y Ullman implica { sa } / { b} produciendo {}, en lugar de {ε}.
El cociente izquierdo (cuando se define de forma similar a Hopcroft y Ullman 1979) de un lenguaje singleton L 1 y un lenguaje arbitrario L 2 se conoce como derivado de Brzozowski ; si L 2 está representado por una expresión regular , también puede ser el cociente izquierdo. [8]
El cociente derecho de un subconjunto de un monoid define una relación de equivalencia , llamado el derecho relación sintáctica de S . Es dado por
La relación es claramente de índice finito (tiene un número finito de clases de equivalencia) si y sólo si los cocientes del derecho de familia son finitos; eso es, si
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 estado finito . Esto se discute con mayor detalle en el artículo sobre monoides sintácticos . [ cita requerida ]
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 por el lado derecho. Se denota y se define recursivamente como
La cadena vacía siempre se puede cancelar:
Claramente, cancelación correcta y conmutación de proyección :
Los prefijos de una cadena es el conjunto de todos los prefijos de una cadena, con respecto a un idioma determinado:
donde .
El prefijo de cierre de un idioma es
Ejemplo:
Un idioma se llama prefijo cerrado si .
El operador de cierre de prefijo es idempotente :
La relación de prefijo es una relación binaria tal que si y solo si . Esta relación es un ejemplo particular de orden de prefijo . [ cita requerida ]