nulabilidad (Las expresiones regulares)

Question

En "Derivados de las expresiones regulares" de Brzozowski y en otros lugares, el δ función (R) devolver λ si un R es anulable, y ∅ otra cosa, incluye cláusulas tales como los siguientes:

δ(R1 + R2) = δ(R1) + δ(R2) 
δ(R1 · R2) = δ(R1) ∧ δ(R2) 

Claramente, si tanto R1 y R2 son anulable entonces (R1 · R2) es anulable, y si cualquiera de R1 o R2 es anulable entonces (R1 + R2) es anulable. Sin embargo, no está claro para mí lo que se supone que significan las cláusulas anteriores. Mi primer pensamiento, el mapeo de (+), (·), o las operaciones booleanas a conjuntos regulares no tiene sentido, ya que en el caso base,

δ(a) = ∅ (for all a ∈ Σ) 
δ(λ) = λ 
δ(∅) = ∅ 

y λ no es un conjunto (ni es un conjunto el tipo de retorno de δ, que es una expresión regular). Además, este mapeo no está indicado, y hay una notación separada para él. Comprendo nulability, pero estoy perdido en la definición de suma, producto y operaciones booleanas en la definición de δ: cómo son λ o ∅ devueltos de δ (R1) ∧ δ (R2), por ejemplo , en la definición de δ (R1 · R2)?

Answer 1

Creo que te atrapan las libertades notacionales tomadas por el autor. El tipo de retorno de δ (R) es sin duda un conjunto, o más bien un lenguaje. Si nos fijamos en la definición:

se puede ver que hay una inconsistencia en el tipo de retorno, formalmente λ es un elemento, pero ∅ es el lenguaje vacío ... lo que debería decir es:

el hecho de que el autor utiliza λ tanto para la cadena vacía, así como el lenguaje que contiene sólo la cadena vacía se evidencia aún más por la definición del operador de Kleene estrella:

Claramente, la última parte debe ser si queremos ser pedantes.

Dado que el tipo de retorno de δ (R) es un conjunto, o más bien un idioma, las ecuaciones que proporcione tienen perfecto sentido y expresan exactamente lo que usted describió.

Answer 2

Creo que tenía razón al mapear + y ^ a boolean or y and respectivamente. Parece que las dos líneas que citó trato con alternancia (suma) y concatenación (producto):

δ(R1 + R2) = δ(R1) + δ(R2) 

El alternancia de R1 y R2 es anulable si R1 es anulable, R2 es anulable, o ambos R1 y R2 son nulables.

δ(R1 · R2) = δ(R1) ∧ δ(R2) 

La concatenación de R1 y R2 sólo es anulable si ambos R1 y R2 son anulables.

Consulte here para obtener una implementación de Haskell de estas reglas.

Answer 3

(No puedo ver el artículo de Brzozowski para entender mejor lo que se quiere decir), pero puedo sugerir 2 maneras de interpretar esta notación (además de ver cómo funciona la notación, veo, no hay pregunta: el sentido intencionado de esta definición es bien entendido):

1) A la izquierda de la definición, tenemos solo patrones "sintácticos" para las expresiones regulares. A la derecha, producimos conjuntos; recuerde que una expresión regular es una manera de denotar un idioma (un conjunto), por lo que esta forma de escribir la definición se vuelve comprensible: a la derecha, simplemente usamos algunas expresiones regulares (simples) como una forma breve de referirnos a conjuntos. Es decir, ∅ significa el idioma vacío (el conjunto vacío) y λ (si interpreta como expresión regular) significa el idioma que contiene solo la palabra vacía (el conjunto con este elemento).

Las operaciones son simplemente operaciones en conjuntos: probablemente unión e intersección.

Si la notación se interpreta de esta manera, no hay contradicción con la notación utilizada para defian el caso base: de nuevo, "a" es una expresión regular que significa el idioma con la palabra "a".

2) Construimos expresiones regulares a la derecha, en primer lugar, pero el autor ha ampliado las operaciones que crean expresiones regulares con la cuña, que tiene la semántica de intersección de idiomas.