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: tú − 1 S {\displaystyle u^{-1}S} S {\estilo de visualización S} tú {\estilo de visualización u} S {\estilo de visualización S} tú {\estilo de visualización u}

tú − 1 S = { en ∈ Σ ∗ ∣ tú en ∈ S } {\displaystyle u^{-1}S=\{v\en \Sigma ^{*}\mid uv\en S\}} .

Por ejemplo,

do − 1 { gato , vaca , perro } = { en , Ay } . {\displaystyle c^{-1}\{{\text{gato}},{\text{vaca}},{\text{perro}}\}=\{{\text{a}},{\text{abajo}}\}.}

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] S {\estilo de visualización S} Σ {\estilo de visualización \Sigma} tú ∈ Σ ∗ {\displaystyle u\in \Sigma ^{*}} S {\estilo de visualización S} tú {\estilo de visualización u}

tú − 1 S = { en ∈ Σ ∗ ∣ tú en ∈ S } {\displaystyle u^{-1}S=\{v\en \Sigma ^{*}\mid uv\en S\}}

La derivada de Brzozowski es un caso especial de cociente izquierdo por un conjunto singleton que contiene sólo : . tú {\estilo de visualización u}   tú − 1 S = { tú } ∖ S {\displaystyle \ u^{-1}S=\{u\}\;\barra invertida \;S}

De manera equivalente, para todos : tú , en ∈ Σ ∗ {\displaystyle u,v\en \Sigma ^{*}}

en ∈ tú − 1 S ⇔ tú en ∈ S . {\displaystyle v\en u^{-1}S\;\Leftrightarrow \;uv\en S.}

De la definición, para todos : tú , en ∈ Σ ∗ {\displaystyle u,v\en \Sigma ^{*}}

( tú en ) − 1 S = en − 1 ( tú − 1 S ) {\displaystyle (uv)^{-1}S=v^{-1}(u^{-1}S)}

ya que para todos , tenemos . el ∈ Σ ∗ {\displaystyle w\in \Sigma ^{*}} el ∈ ( tú en ) − 1 S ⇔ tú en el ∈ S ⇔ en el ∈ tú − 1 S ⇔ el ∈ en − 1 ( tú − 1 S ) {\displaystyle w\in (uv)^{-1}S\Flecha izquierda derecha uvw\in S\Flecha izquierda derecha vw\in u^{-1}S\Flecha izquierda 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 : a ∈ Σ , tú ∈ Σ ∗ {\displaystyle a\en \Sigma ,u\en \Sigma ^{*}} ( tú a ) − 1 S = a − 1 ( tú − 1 S ) mi − 1 S = S {\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: S ⊆ Σ ∗ {\displaystyle S\subseteq \Sigma ^{*}} mi {\estilo de visualización \varepsilon} S {\estilo de visualización S}

el ∈ S   ⇔   mi ∈ el − 1 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 : el ∈ Σ ∗ {\displaystyle w\in \Sigma ^{*}} el ∈ S {\displaystyle w\in S} a {\estilo de visualización a} a {\estilo de visualización a} a − 1 S estilo de visualización a^{-1}S} S ⊆ Σ ∗ {\displaystyle S\subseteq \Sigma ^{*}}

S = ( { mi } ∩ S ) ∪ ⋃ a ∈ Σ a ( a − 1 S ) . {\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 −1 R es nuevamente una expresión regular generalizada (que denota el lenguaje u −1 L ( R )). [7] Puede calcularse recursivamente de la siguiente manera. [8]

( ua ) −1 R= a −1 ( u −1 R )      para un símbolo a y una cadena u
ε −1 R= R

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]

un −1 un= ε
a -1 b= ∅para cada símbolo b ≠ a
a -1 ε= ∅
un −1 ∅= ∅
a −1 ( R *)= ( a − 1R ) R *
a −1 ( RS )= ( a −1 R ) S ∨ ν( R ) a −1 S
a −1 ( R ∧ S )= ( a − 1R )∧( a − 1S )
a −1 ( R ∨ S )= ( a − 1R )∨( a − 1S )
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]

v( a )= ∅para cualquier símbolo a
ν( ε )= ε
ν(∅)= ∅
v( R *)= ε
v( 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 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 −1 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

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 n 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.
Obtenido de "https://es.wikipedia.org/w/index.php?title=Derivado_de_Brzozowski&oldid=1210423419"