En la informática teórica , en particular en la teoría del lenguaje formal , la derivada de Brzozowski u −1 S de un conjunto S de cadenas y una cadena u se define como el conjunto de todas las cadenas que se pueden obtener de una cadena en S cortando un prefijo u , formalmente: u −1 S = { v ∈ Σ * : uv ∈ S }, cf. imagen. 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 lenguajes formales arbitrarios. Dado cualquier lenguaje formal S sobre un alfabeto Σ y cualquier cadena u ∈ Σ * , la derivada de S con respecto a u se define como: [5]
- u −1 S = { v ∈ Σ * : uv ∈ S }
Una forma equivalente de decir esto es, para todo u , v ∈ Σ * :
- v ∈ u −1 S si si uv ∈ S
lo que proporciona cierta intuición para la notación.
De la definición, para todo u , v , w ∈ Σ * :
- v ∈ ( uw ) −1 S iff uwv ∈ S iff wv ∈ u −1 S iff v ∈ w −1 ( u −1 S )
entonces ( uw ) −1 S = w −1 ( u −1 S ).
La derivada con respecto a una cadena arbitraria se reduce a derivadas sucesivas sobre los símbolos de esa cadena porque, para un ∈ Σ, u ∈ Σ * :
( ua ) −1 S = a −1 ( u −1 S ) ε −1 S = S
Un lenguaje L ⊆ Σ * se llama anulable si contiene la cadena vacía, es decir, varepsilon ∈ L . Cada lenguaje S está determinado de forma única por la nulabilidad de sus derivados:
- w ∈ S si ε ∈ w −1 S
Un lenguaje puede verse como un árbol etiquetado booleano (potencialmente infinito) (ver también árbol (teoría de conjuntos) y autómata de árbol infinito ). Cada posible cadena w ∈ Σ * denota una posición en el árbol, con la etiqueta binario verdadero cuando w ∈ S y falsa cuando w ∉ S . En esta interpretación, la derivada con respecto a un símbolo a corresponde a calcular el subárbol obtenido siguiendo el borde a . La descomposición del árbol en la raíz y los subárboles a −1 S corresponde a la siguiente igualdad, que se cumple para todos los lenguajes formales S ⊆ Σ * :
- S = ({ ε } ∩ S ) ∪ ⋃ a ∈Σ a ( a −1 S ) .
Derivadas de expresiones regulares generalizadas
Cuando un lenguaje viene dado por una expresión regular, el concepto de derivadas conduce a un algoritmo para decidir si una palabra determinada pertenece a la expresión regular.
Dado un finito alfabeto A de símbolos, [6] una expresión regular generalizada denota un conjunto posiblemente infinito de cadenas finitas de longitud de los símbolos de A . Puede estar construido con:
- ∅ (que denota el conjunto vacío de cadenas),
- ε (que denota el conjunto singleton que contiene solo la cadena vacía),
- un símbolo a de A (que denota el conjunto singleton que contiene la cadena de un solo símbolo a ),
- R ∨ S (donde R y S son, a su vez, expresiones regulares generalizadas; denota la unión de su conjunto),
- R ∧ S (que denota la intersección de los conjuntos de R y S ),
- ¬ R (que denota el complemento del conjunto de R con respecto al conjunto de todas las cadenas de símbolos de A ),
- RS (que denota el conjunto de todas las posibles concatenaciones de cadenas del conjunto de R y S ),
- R * (que denota el conjunto de n repeticiones de cadenas del conjunto de R , para cualquier n ≥0, incluida la cadena vacía).
En una expresión regular ordinaria, no se permiten ni ∧ ni ¬. El conjunto de cadenas denotado por una expresión regular generalizada R se llama su lenguaje , denotado como L ( R ).
Cálculo
Para cualquier expresión regular generalizada R dada y cualquier cadena u , la derivada u −1 R es nuevamente una expresión regular generalizada. [7] Puede calcularse de forma recursiva de la siguiente manera. [8]
( ua ) −1 R = a −1 ( u −1 R ) para un símbolo de una y una cadena u ε −1 R = R
Usando 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 . Este último se puede calcular de la siguiente manera: [9]
a −1 a = ε a −1 b = ∅ para cada símbolo b ≠ a a −1 ε = ∅ a −1 ∅ = ∅ a −1 ( R * ) = ( a −1 R ) R * a −1 ( RS ) = ( a −1 R ) S ∨ ν ( R ) a −1 S a −1 ( R ∧ S ) = ( a −1 R ) ∧ ( a −1 S ) a −1 ( R ∨ S ) = ( a −1 R ) ∨ ( a −1 S ) a −1 (¬ R ) = ¬ ( a −1 R )
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]
ν ( a ) = ∅ para cualquier símbolo a ν ( ε ) = ε ν (∅) = ∅ ν ( R * ) = ε ν ( RS ) = ν ( R ) ∧ ν ( S ) ν ( R ∧ S ) = ν ( R ) ∧ ν ( S ) ν ( R ∨ S ) = ν ( R ) ∨ ν ( S ) ν (¬ R ) = ε si ν ( R ) = ∅ ν (¬ R ) = ∅ si ν ( R ) = ε
Propiedades
Una cadena u es un miembro del conjunto de cadena denotada por una expresión generalizada regular de R si y sólo si ε es un miembro del conjunto de cadena denotada por el derivado u -1 R . [11]
Si se consideran todas las derivadas de una expresión regular generalizada fija R, solo se obtienen un número finito de lenguajes diferentes. Si su número se denota por d R , todos estos idiomas se pueden obtener como derivados de R con respecto a la cadena de longitud por debajo 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 lo establece el teorema de Myhill-Nerode .
Derivados de lenguajes libres de contexto
Las derivadas también son efectivamente computables para ecuaciones definidas de forma recursiva con operadores de expresión regular, que son equivalentes a gramáticas libres de contexto . Esta información se utilizó para derivar algoritmos de análisis para lenguajes sin contexto. [13] La implementación de tales algoritmos ha demostrado tener complejidad cúbica, [14] correspondiente a la complejidad del analizador sintáctico Earley en gramáticas generales libres de contexto.
Ver también
Referencias
- ^ George N. Raney (abril de 1958). "Funciones secuenciales" . Revista de la ACM . 5 (2): 177–180. doi : 10.1145 / 320924.320930 . S2CID 1611992 .
- ^ Dana Scott y Michael Rabin (abril de 1959). "Autómatas finitos y sus problemas de decisión" (PDF) . Revista de investigación y desarrollo de IBM . 3 (2): 114-125. doi : 10.1147 / rd.32.0114 .
- ^ CC Elgot y JD Rutledge (octubre de 1961). "Operaciones sobre autómatas finitos". En Robert S. Ledley (ed.). Proc. AIEE 2nd Ann. Symp. en Conmutación, Teoría de Circuitos y Diseño Lógico (SWCT), Detroit . págs. 129-132. doi : 10.1109 / FOCS.1961.26 .
- ^ Janusz A. Brzozowski (1964). "Derivadas de expresiones regulares". J ACM . 11 (4): 481–494. doi : 10.1145 / 321239.321249 . S2CID 14126942 .
- ^ Janusz A. Brzozowski (1964). "Derivadas de expresiones regulares". J ACM . 11 (4): 481–494. doi : 10.1145 / 321239.321249 . S2CID 14126942 .
- ↑ Brzozowski (1964), p. 481, requería que A constara de las 2 n combinaciones de n bits , para algunos n .
- ↑ Brzozowski (1964), p. 483, Teorema 4.1
- ↑ Brzozowski (1964), p. 483, Teorema 3.2
- ↑ Brzozowski (1964), p. 483, Teorema 3.1
- ↑ Brzozowski (1964), p. 482, Definición 3.2
- ↑ Brzozowski (1964), p. 483, Teorema 4.2
- ↑ Brzozowski (1964), p. 484, Teorema 4.3
- ^ Matthew Might; David Darais; Daniel Spiewak (2011). Analizando con derivados: 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 .
- ^ Michael D. Adams; Celeste Hollenbeck; Matthew Might (2016). Sobre la complejidad y el rendimiento del análisis sintáctico con derivados . Actas de la 37ª Conferencia de ACM SIGPLAN sobre diseño e implementación de lenguajes de programación (PLDI). págs. 224-236. doi : 10.1145 / 2908080.2908128 .