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.
Cadenas e idiomas
Una cadena es una secuencia finita de caracteres. La cadena vacía se denota por. La concatenación de dos cuerdas 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 :.
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 idiomas, su concatenación se define como el conjunto de concatenaciones de cualquier cadena de y cualquier cadena de , formalmente . De nuevo, el punto de concatenación a menudo se omite por brevedad.
El idioma que consiste solo en la cadena vacía se debe distinguir del lenguaje vacío . Concatenar cualquier idioma con el primero no supone ningún cambio:, mientras que la concatenación con este último siempre produce el lenguaje vacío: . La 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.
Alfabeto de una cadena
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 un idioma es el conjunto de todos los caracteres que aparecen en cualquier cadena de , formalmente: .
Por ejemplo, el conjunto es el alfabeto de la cuerda , y lo anterior es el alfabeto del idioma anterior así como del idioma de todos los números decimales.
Sustitución de cadenas
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
- 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 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,
- 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›, ‹¡Vamos!›}) = {‹STRASSE›} ∪ {‹U›} ∪ {} = {‹STRASSE›, ‹U›}.
Homomorfismo de cuerdas
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,, dónde es 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 llama la imagen homomórfica de. La imagen homomórfica inversa de una cuerda Se define como
mientras que la imagen homomórfica inversa de una lengua Se define como
En general, , mientras que 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 cuerdas está libre de ε (o libre de e) si para todos una 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
- g uc −1 ({‹SSS›}) = {‹sss›, ‹sß›, ‹ßs›}, ya que g uc (‹sss›) = g uc (‹sß›) = g uc (‹ßs›) = ‹SSS›, y
- g uc −1 ({‹A›, ‹bb›}) = {‹a›}, ya que g uc (‹a›) = ‹A›, mientras que ‹bb› no puede ser alcanzado por g uc .
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 .
Proyección de cuerdas
Si s es una cadena yes un alfabeto, la proyección de cadena de s es la cadena que resulta de eliminar todos los caracteres que no están en. Esta 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
- [ cita requerida ]
Cociente derecho
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:
Del mismo modo, 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 } ceder {}, 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]
Relación sintáctica
El cociente correcto de un subconjunto de un monoide 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 ]
Cancelación correcta
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 como y se define recursivamente como
La cadena vacía siempre se puede cancelar:
Claramente, la cancelación correcta y la proyección se desplazan al trabajo :
- [ cita requerida ]
Prefijos
Los prefijos de una cadena es el conjunto de todos los prefijos de una cadena, con respecto a un idioma determinado:
dónde .
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 ]
Ver también
- Comparación de lenguajes de programación (funciones de cadena)
- Lema de Levi
- Cadena (informática) : definición e implementación de operaciones más básicas en cadenas
Notas
- ^ Aunque todos los lenguajes regulares también están libres de contexto, el teorema anterior no está implícito en el actual, ya que el primero produce un resultado modelador para los lenguajes regulares.
- ^ Estrictamente formalmente, un homomorfismo produce un lenguaje que consta de una sola cadena, es decir.
- ^ Esto se desprende delcierre 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 los autómatas . Reading, Massachusetts: Addison-Wesley Publishing. ISBN 978-0-201-02988-8. Zbl 0426.68001 . (Ver capítulo 3.)
- ↑ Hopcroft, Ullman (1979), Sección 3.2, p.60
- ^ Hopcroft, Ullman (1979), Sección 3.2, Teorema 3.4, p.60
- ^ Hopcroft, Ullman (1979), Sección 6.2, Teorema 6.2, p.131
- ^ Hopcroft, Ullman (1979), Sección 3.2, p.60-61
- ^ Hopcroft, Ullman (1979), Sección 3.2, Teorema 3.5, p.61
- ^ Hopcroft, Ullman (1979), Sección 6.2, Teorema 6.3, p.132
- ↑ Hopcroft, Ullman (1979), Sección 3.2, p.62
- ^ Janusz A. Brzozowski (1964). "Derivadas de expresiones regulares". J ACM . 11 (4): 481–494. doi : 10.1145 / 321239.321249 .