학교 과제로 정규표현식을 문자열로 미분시켜서 매칭시키는 알고리즘을 짜라고 던져줬다.


https://en.wikipedia.org/wiki/Brzozowski_derivative



위에 따르면 "정규표현식"을 "문자열"로 미분한 값 또한 정규표현식이다.

어떤 문자열을 정규표현식에 매칭시키고 싶다면, 그 정규표현식을 시험하고 싶은 문자열로 "미분"한 결과로 나온 정규표현식에 빈 문자열(ε)을 매칭할 수 있는지 보면 된다.


예시로 정규표현식 a를 문자열 "a"로 미분하면 d(a) / d"a" = ε 이어서 성공하고 "b"로 미분하면 d(a) / d"b" = false 여서 실패한다.



이게 뭔 헛소리냐고 묻기 전에 미분을 해보자. "abcx"를 a(b|c)*x에 매칭시켜보기로 한다.


미분 룰에 의해 d(a(b|c)*x) / d"abcx" = d(d(d(d(a(b|c)*x) / d"a") / d"b") / d"c") / d"x" 이므로 안쪽부터 미분값을 구한다.



1) d(a(b|c)*x) / d"a"

일반적인 미분의 곱셈공식에 따르면 d(fg)/dx = f*dg/dx + df/dx * g가 나와야 할 것 같다. 비슷하다.


정규표현식 AB에 "x"가 매칭된다면 "x"가 A에 매칭된 경우 or A를 스킵하고 B에 매칭된 경우, 2개 중 하나일 텐데

A를 스킵했다는 것은 A가 빈 문자열일 수 있어서 "x"가 B에 매칭되었다는 소리다.


어떤 정규식이 빈 문자열을 포함할 수 있는지 없는지를 검사하는 함수 nu(x)를 만든다.


nu(ε) = true

nu(a) = false     (a: Char)

nu(A*) = true

nu(A | B) = nu(A) || nu(B)

nu(AB) = nu(A) && nu(B)


이를 사용하면 정규표현식 미분의 곱셈공식은 다음과 같다. (편의상 문자열 concat을 . 로 쓰겠다.)


d(AB) / d"x" = (d(A)/d"x" . B) | (nu(A) . d(B)/d"x")


(nu 함수가 정규표현식에 끼어들어갈 때, nu 함수의 결과값이 true면 빈 문자열이 되고 false면 그 정규표현식은 아무 문자열도 매칭할 수 없다.)



위 공식을 따르면 다음 계산을 할 수 있다.


d(a(b|c)*x) / d"a"

= (d(a)/d"a" . (b|c)*x) | (nu(a) . d((b|c)*x) / d"x")

= d(a) / d"a" . (b|c)*x            (nu(a) = false 이므로 | 뒤의 정규식은 아무 문자열도 매칭할 수 없어서 버린다)
= (b|c)*x (d(a) / d"a" = ε)



2) d((b|c)*x) / d"b"


d(A|B)/d"x" 는 A, B 둘 중 하나에 "x"를 매칭시킬지를 검사하는 것이므로 공식은 다음과 같다.


d(A|B)/d"x" = d(A)/d"x" | d(B)/d"x"


쉽게 말해 | 를 사칙연산의 + 와 같다고 보고 미분하면 된다.



다음으로 정규표현식 A*을 풀어써보면 A* = ε | A | AA | AAA | AAAA | AAAAA | .... 인데 앞에서 배운 룰들을 적절히 조합 후 계산하면 다음을 보일 수 있다.


d(A*)/d"x" = d(A)/d"x" | d(A)/d"x" . A | d(A)/d"x" . AA | d(A)/d"x" . AAA | ... | nu(A) . d(A)/d"x" | nu(A) . nu(A) . d(A) / d"x" | ...

= d(A)/d"x" . A*

(nu(A)는 어차피 시험함수이므로 앞의 식들과 통합할 수 있음)


그러므로


d((b|c)*x) / d"b" 

= (d((b|c)*) / d"b" . x) | nu((b|c)*) . d(x) / d"b"

= d((b|c)*) / d"b" . x        (d(x) / d"b" = false)

= d(b|c)/d"b" . (b|c)*x

= ε . (b|c)*x

= (b|c)*x


마찬가지로


d((b|c)*x) / d"c" = (b|c)*x


d((b|c)*x) / d"x" 

= (d((b|c)*) / d"x" . x) | nu((b|c)*) . d(x) / d"x"

= d(b|c)/d"x" . (b|c)*x | true . ε

= false . (b|c)*x | ε

= ε


결과값이 ε가 나왔으므로 매칭에 성공했다.



한줄 요약: 오토마타 그거 왜 배움?