Derivado de Brzozowski

Función definida en lenguajes formales en informática

Derivada de Brzozowski (sobre fondo rojo) de un conjunto de cadenas de diccionario con respecto a la cadena "con"

En informática teórica , en particular en teoría del lenguaje formal , la derivada de Brzozowski de un conjunto de cadenas y una cadena es el conjunto de todas las cadenas que se pueden obtener a partir de una cadena en cortando el prefijo . Formalmente: ${\displaystyle u^{-1}S}$ ${\displaystyle S}$ ${\displaystyle u}$ ${\displaystyle S}$ ${\displaystyle u}$

${\displaystyle u^{-1}S=\{v\in \Sigma ^{*}\mid uv\in S\}}$.

Por ejemplo,

${\displaystyle c^{-1}\{{\text{cat}},{\text{cow}},{\text{dog}}\}=\{{\text{at}},{\text{ow}}\}.}$

La derivada de Brzozowski se introdujo con varios nombres diferentes desde finales de la década de 1950. ^{[1] [2] [3]} Hoy lleva el nombre del científico informático Janusz Brzozowski , quien investigó sus propiedades y dio un algoritmo para calcular la derivada de una expresión regular generalizada . ^[4]

Definición

Aunque originalmente se estudió para expresiones regulares, la definición se aplica a cualquier lenguaje formal. Dado cualquier lenguaje formal sobre un alfabeto y cualquier cadena , la derivada de con respecto a se define como: ^[5] ${\displaystyle S}$ ${\displaystyle \Sigma }$ ${\displaystyle u\in \Sigma ^{*}}$ ${\displaystyle S}$ ${\displaystyle u}$

${\displaystyle u^{-1}S=\{v\in \Sigma ^{*}\mid uv\in S\}}$

La derivada de Brzozowski es un caso especial de cociente izquierdo por un conjunto singleton que contiene sólo : . ${\displaystyle u}$ ${\displaystyle \ u^{-1}S=\{u\}\;\backslash \;S}$

De manera equivalente, para todos : ${\displaystyle u,v\in \Sigma ^{*}}$

${\displaystyle v\in u^{-1}S\;\Leftrightarrow \;uv\in S.}$

De la definición, para todos : ${\displaystyle u,v\in \Sigma ^{*}}$

${\displaystyle (uv)^{-1}S=v^{-1}(u^{-1}S)}$

ya que para todos , tenemos . ${\displaystyle w\in \Sigma ^{*}}$ ${\displaystyle w\in (uv)^{-1}S\Leftrightarrow uvw\in S\Leftrightarrow vw\in u^{-1}S\Leftrightarrow w\in v^{-1}(u^{-1}S)}$

La derivada con respecto a una cadena arbitraria se reduce a derivadas sucesivas sobre los símbolos de esa cadena, ya que para todo : ${\displaystyle a\in \Sigma ,u\in \Sigma ^{*}}$ $${\displaystyle {\begin{aligned}(ua)^{-1}S&=a^{-1}(u^{-1}S)\\\varepsilon ^{-1}S&=S\end{aligned}}}$$

Un lenguaje se considera nulo si y solo si contiene la cadena vacía . Cada lenguaje se determina de forma única por la nulidad de sus derivados: ${\displaystyle S\subseteq \Sigma ^{*}}$ ${\displaystyle \varepsilon }$ ${\displaystyle S}$

${\displaystyle w\in S\ \Leftrightarrow \ \varepsilon \in w^{-1}S}$

Un lenguaje puede ser visto como un árbol (potencialmente infinito) etiquetado con booleanos (ver también árbol (teoría de conjuntos) y autómata de árbol infinito ). Cada cadena posible denota un nodo en el árbol, con etiqueta verdadera cuando y falsa en caso contrario. En esta interpretación, la derivada con respecto a un símbolo corresponde al subárbol obtenido al seguir la arista desde la raíz. Descomponer un árbol en la raíz y los subárboles corresponde a la siguiente igualdad, que se cumple para cada lenguaje : ${\displaystyle w\in \Sigma ^{*}}$ ${\displaystyle w\in S}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle a^{-1}S}$ ${\displaystyle S\subseteq \Sigma ^{*}}$

${\displaystyle S=(\{\varepsilon \}\cap S)\cup \bigcup _{a\in \Sigma }a(a^{-1}S).}$

Derivadas de expresiones regulares generalizadas

Cuando un idioma se da mediante una expresión regular, el concepto de derivadas conduce a un algoritmo para decidir si una palabra dada pertenece a la expresión regular.

Dado un alfabeto finito A de símbolos, ^[6] una expresión regular generalizada R denota un conjunto posiblemente infinito de cadenas de longitud finita sobre el alfabeto A , llamado el lenguaje de R , denotado L ( R ).

Una expresión regular generalizada puede ser una de las siguientes (donde a es un símbolo del alfabeto A , y R y S son expresiones regulares generalizadas):

• "∅" denota el conjunto vacío: L (∅) = {},
• "ε" denota el conjunto singleton que contiene la cadena vacía: L (ε) = {ε},
• " a " denota el conjunto singleton que contiene la cadena de un solo símbolo a : L ( a ) = { a },
• " R ∨ S " denota la unión de R y S : L ( R ∨ S ) = L ( R ) ∪ L ( S ),
• " R ∧ S " denota la intersección de R y S : L ( R ∧ S ) = L ( R ) ∩ L ( S ),
• "¬ R " denota el complemento de R (con respecto a A *, el conjunto de todas las cadenas sobre A ): L (¬ R ) = A *\ L ( R ),
• " RS " denota la concatenación de R y S : L ( RS ) = L ( R ) · L ( S ),
• " R *" denota el cierre de Kleene de R : L ( R *) = L ( R )*.

En una expresión regular ordinaria, no se permiten ni ∧ ni ¬.

Cálculo

Para cualquier expresión regular generalizada dada R y cualquier cadena u , la derivada u ⁻¹ R es nuevamente una expresión regular generalizada (que denota el lenguaje u ⁻¹ L ( R )). ^[7] Puede calcularse recursivamente de la siguiente manera. ^[8]

Utilizando las dos reglas anteriores, la derivada con respecto a una cadena arbitraria se explica por la derivada con respecto a una cadena de un solo símbolo a . Esta última se puede calcular de la siguiente manera: ^[9]

Aquí, ν( R ) es una función auxiliar que produce una expresión regular generalizada que se evalúa como la cadena vacía ε si el lenguaje de R contiene ε , y de lo contrario se evalúa como ∅. Esta función se puede calcular mediante las siguientes reglas: ^[10]

Propiedades

Una cadena u es un miembro del conjunto de cadenas denotado por una expresión regular generalizada R si y solo si ε es un miembro del conjunto de cadenas denotado por la derivada u ⁻¹ R . ^[11]

Si se consideran todas las derivadas de una expresión regular generalizada fija R, se obtiene un número finito de lenguajes diferentes. Si su número se denota por d _R , todos estos lenguajes se pueden obtener como derivados de R con respecto a cadenas de longitud menor que d _R . ^[12] Además, existe un autómata finito determinista completo con d _R estados que reconoce el lenguaje regular dado por R , como se indica en el teorema de Myhill–Nerode .

Derivados de lenguajes libres de contexto

Las derivadas también son efectivamente computables para ecuaciones definidas recursivamente con operadores de expresión regular, que son equivalentes a gramáticas libres de contexto . Esta idea se utilizó para derivar algoritmos de análisis para lenguajes libres de contexto . ^[13] La implementación de tales algoritmos ha demostrado tener una complejidad de tiempo cúbico , ^[14] correspondiente a la complejidad del analizador de Earley en gramáticas generales libres de contexto.

Véase también

• Cociente de un lenguaje formal

Referencias

1. George N. Raney (abril de 1958). "Funciones secuenciales". Revista de la ACM . 5 (2): 177–180. doi :10.1145/320924.320930. S2CID  1611992.
2. Dana Scott y Michael Rabin (abril de 1959). "Autómatas finitos y sus problemas de decisión" (PDF) . IBM Journal of Research and Development . 3 (2): 114–125. doi :10.1147/rd.32.0114.
3. CC Elgot y JD Rutledge (octubre de 1961). "Operaciones en autómatas finitos". En Robert S. Ledley (ed.). Proc. AIEE 2nd Ann. Symp. on Switching, Circuit Theory, and Logical Design (SWCT), Detroit. págs. 129-132. doi :10.1109/FOCS.1961.26.
4. Janusz A. Brzozowski (1964). "Derivadas de expresiones regulares". J.ACM . 11 (4): 481–494. doi : 10.1145/321239.321249 . S2CID  14126942.
5. Janusz A. Brzozowski (1964). "Derivadas de expresiones regulares". J.ACM . 11 (4): 481–494. doi : 10.1145/321239.321249 . S2CID  14126942.
6. Brzozowski (1964), p.481, requirió que A consistiera en las 2 ⁿ combinaciones de n bits , para algún n .
7. Brzozowski (1964), p.483, Teorema 4.1
8. Brzozowski (1964), p.483, Teorema 3.2
9. Brzozowski (1964), p.483, Teorema 3.1
10. Brzozowski (1964), p.482, Definición 3.2
11. Brzozowski (1964), p.483, Teorema 4.2
12. Brzozowski (1964), p.484, Teorema 4.3
13. Matthew Might; David Darais; Daniel Spiewak (2011). Análisis sintáctico con derivadas: una perla funcional . Actas de la 16.ª conferencia internacional ACM SIGPLAN sobre programación funcional (ICFP). págs. 189–195. doi :10.1145/2034773.2034801.
14. Michael D. Adams; Celeste Hollenbeck; Matthew Might (2016). "Sobre la complejidad y el rendimiento del análisis sintáctico con derivadas". Actas de la 37.ª Conferencia ACM SIGPLAN sobre diseño e implementación de lenguajes de programación . Actas de la 37.ª Conferencia ACM SIGPLAN sobre diseño e implementación de lenguajes de programación (PLDI). pp. 224–236. arXiv : 1604.04695 . doi : 10.1145/2908080.2908128 . ISBN 9781450342612.