Brzozowski导数

定义. 一个语言是一个字符串的集合, 一个字符串是一个字符的有限序列.

记号.

ε

代表空字符串 (显然只有一个).

0 ≔ \emptyset

1 ≔ {ε}

. 对于字符

c

c ≔ {c}

(注意到我们将字符

c

当成字符串

c

, 这有些模糊, 却是数学实践的惯例).

定义. 对于字符

c

和语言

L

L

相对于

c

的Brzozowski导数

D_{c} (L)

是一个语言, 其是

L

中所有以

c

开头的字符串去掉开头的

c

得到的.

定义. 给定语言

L_{1}

和

L_{2}

L_{1} + L_{2} ≔ L_{1} \cup L_{2}

L_{1} \times L_{2} ≔ {w_{1} w_{2} | w_{1} \in L_{1}, w_{2} \in L_{2}}

定义. 根据乘法的定义, 我们可以递归地定义语言的幂. 对于语言

L

L^{0} ≔ 1

L^{i + 1} ≔ L \times L^{i}

定义. 根据幂的定义, 我们可以定义Kleene星号. 对于语言

L

L^{⁎} ≔ ⋃_{i \in ℕ} L^{i}

, 注意这里的

ℕ

包括自然数

0

定义. 正则语言可以递归地被定义

$0$ 是一个正则语言;
$1$ 是一个正则语言;
如果 $L_{1}$ 和 $L_{2}$ 是正则语言, 那么 $L_{1} + L_{2}$ 是正则语言;
如果 $L_{1}$ 和 $L_{2}$ 是正则语言, 那么 $L_{1} \times L_{2}$ 是正则语言;
如果 $L$ 是一个正则语言, 那么 $L^{⁎}$ 是一个正则语言.

定义. 正则表达式是描述正则语言的表达式, 其可以由以下的BNF定义

<exp> ::= zero
       |  one
       |  <char>
       |  (plus <exp> <exp>)
       |  (times <exp> <exp>)
       |  (star <exp>)

定理. Brzozowski导数具有以下性质

$D_{c} (0) = 0$ ;
$D_{c} (1) = 0$ ;
$D_{c} (c) = 1$ ;
$D_{c} (c^{'}) = 0$ , 如果 $c \neq c^{'}$ ;
$D_{c} (L_{1} + L_{2}) = D_{c} (L_{1}) + D_{c} (L_{2})$ ;
$D_{c} (L_{1} \times L_{2}) = D_{c} (L_{1}) \times L_{2}$ , 如果 $ε \notin L_{1}$ ;
$D_{c} (L_{1} \times L_{2}) = (D_{c} (L_{1}) \times L_{2}) + D_{c} (L_{2})$ , 如果 $ε \in L_{1}$ ;
$D_{c} (L^{⁎}) = D_{c} (L) \times L^{⁎}$ .

其中

c, c^{'}

是字符,

L, L_{1}, L_{2}

是语言.
实际上, 这给我们提供了计算正则语言的Brzozowski导数的递归方法.

程序. 以下过程D可以计算Brzozowski导数.

(define (D exp c)
  (match exp
    (zero zero)
    (one zero)
    (,c^
     (guard (char? c^))
     (if (char=? c^ c) one zero))
    ((plus ,e1 ,e2)
     (plus (D e1 c) (D e2 c)))
    ((times ,e1 ,e2)
     (define e3
       (times (D e1 c) e2))
     (if (delta? e1)
         (plus e3 (D e2 c))
         e3))
    ((star ,e)
     (times (D e c) (star e)))))

其中

(define zero 'zero)
(define one 'one)
(define (plus e1 e2)
  (cond ((eq? e1 zero) e2)
        ((eq? e2 zero) e1)
        (else `(plus ,e1 ,e2))))
(define (times e1 e2)
  (cond ((eq? e1 zero) zero)
        ((eq? e2 zero) zero)
        ((eq? e1 one) e2)
        ((eq? e2 one) e1)
        (else `(times ,e1 ,e2))))
(define (star exp)
  (cond ((eq? exp zero) one)
        ((eq? exp one) one)
        (else `(star ,exp))))
(define (delta? exp)
  (match exp
    (zero #f)
    (one #t)
    (,c (guard (char? c)) #f)
    ((plus ,e1 ,e2)
     (or (delta? e1) (delta? e2)))
    ((times ,e1 ,e2)
     (and (delta? e1) (delta? e2)))
    ((star ,e) #t)))

定理. 对于字符

c

和字符串

w

, 对于语言

L

c w \in L

当且仅当

w \in D_{c} (L)

程序. 以上定理给我们提供了一个判断字符串是否在语言之中的方法, 根据过程D, 我们可以编写一个判断字符串是否在 (由正则表达式刻画的) 正则语言之中的谓词in?.

(define (in? str exp)
  (define l (string-length str))
  (let iter ((i 0) (exp exp))
    (cond ((= i l) (delta? exp))
          ((eq? exp zero) #f)
          (else
           (iter (+ i 1)
                 (D exp (string-ref str i)))))))

例子. 以下是简单的例子, 刻画了in?的用法

> (define L-pair-elim
    (times #\c
           (times (plus #\a #\d)
                  (times (star (plus #\a #\d))
                         #\r))))
> (in? "cadar" L-pair-elim)
#t
> (in? "cr" L-pair-elim)
#f
> (in? "cada" L-pair-elim)
#f
> (in? "cader" L-pair-elim)
#f

附录: Standard ML实现的版本

鉴于有的读者可能看不得Lisp, 我也准备了Standard ML的版本.

datatype exp = Zero | One | Char of char | Plus of exp * exp | Times of exp * exp | Star of exp fun deltap(Zero) = false | deltap(One) = true | deltap(Char(c)) = false | deltap(Plus(e1,e2)) = deltap(e1) orelse deltap(e2) | deltap(Times(e1,e2)) = deltap(e1) andalso deltap(e2) | deltap(Star(e)) = true fun ZeroC() = Zero; fun OneC() = One; fun PlusC(Zero,e2) = e2 | PlusC(e1,Zero) = e1 | PlusC(e1,e2) = Plus(e1,e2) fun TimesC(Zero,e2) = Zero | TimesC(e1,Zero) = Zero | TimesC(One,e2) = e2 | TimesC(e1,One) = e1 | TimesC(e1,e2) = Times(e1,e2) fun StarC(Zero) = One | StarC(One) = One | StarC(exp) = Star(exp) fun D(Zero,c) = Zero | D(One,c) = Zero | D(Char(c0),c) = if (c0 = c) then One else Zero | D(Plus(e1,e2),c) = PlusC(D(e1,c),D(e2,c)) | D(Times(e1,e2),c) = let val e3 = TimesC(D(e1,c),e2) in if deltap(e1) then PlusC(e3,D(e2,c)) else e3 end | D(Star(e),c) = TimesC(D(e,c),StarC(e)) fun matchp(str,exp) = let val l = size(str) fun iter(i,exp) = if (i = l) then deltap(exp) else if (exp = Zero) then false else iter(i+1,D(exp,String.sub(str,i))) in iter(0,exp) end val L_pair_elim = Times(Char(#"c"), Times(Plus(Char(#"a"),Char(#"d")), Times(Star(Plus(Char(#"a"),Char(#"d"))), Char(#"r"))))

并请读者阅读以下交互.

- D(L_pair_elim,#"c"); val it = Times (Plus (Char #"a",Char #"d"), Times (Star (Plus (Char #"a",Char #"d")),Char #"r")) : exp - D(it,#"a"); val it = Times (Star (Plus (Char #"a",Char #"d")),Char #"r") : exp - D(it,#"d"); val it = Times (Star (Plus (Char #"a",Char #"d")),Char #"r") : exp - D(it,#"r"); val it = One : exp