10. Regular Expressions

1. Regular Expressions(REs)

 

Resular Expression은 특정한 문자열 집합을 표현한다.

 

이메일인지 여부, 올바른 전화번호인지 여부 등 입력값이 올바른 형태인지를 검증할 때 쓰인다. 집합의 요소가 무한할 경우 모든 문자열들을 저장해놓고 모든 케이스에 대해 비교를 하는것은 불가능하므로, Regular Expression은 유용하다.

 

Regular Expression을 작성하기 위한 operation 종류는 다음과 같다.

operation	order	example RE	matches
concatenattion	3	AABAAB	AABAAB
or	4	AA | BAAB	AA, BAAB
closure	2	AA*A	AA, ABBBBBA
parentheses	1	A(A|B)AAB	AAAAB, ABAAB
at least 1	2	A(BC)+DE	ABCDE, ABCBCED
wildcard		.U.U.U.	CUMULUS, JUGULUM
character class		[A-Za-z][a-z]*	word, Capitalized
exactly k		[0-9]{5}-[0-9]{4}	01023-1234, 22389-1234

 

REs는 매우 강력하지만, 실제로 그것을 쓰는것은 복잡하고 에러에 취약하다.

 

2. REs and DFAs

 

특정한 문자열이 패턴으로 주어졌을 때, 우리는 KMP알고리즘에서 DFA라는 machine을 이용하여 문자열을 인식하였다.

 

Kleene's theorem은 DFA와 RE의 존재성에 관한 것인데, 다음과 같다.

임의의 DFA에 대해, 같은 문자열 집합을 묘사하는 하나의 RE가 존재한다.

임의의 RE에 대해, 같은 문자열 집합을 인식하는 하나의 DFA가 존재한다.

 

따라서, 우리가 RE로 표현한다면, DFA가 반드시 존재하고, DFA로 인식가능하다면 RE가 반드시 존재한다.

 

그렇다면, DFA로 표현한다고 해보자. 가능한가? 아마 불가능할 것이다. 문자열이 아닌 문자열 집합을 표현하므로 DFA가 너무나 많은 상태를 가지게 될 것이다.

 

따라서 우리는 NFA(Nondeterministic finite state automata)를 사용한다. 

DFA와는 다르게 비교하는 입력문자에 따라 진행하는 경로가 정해져있지 않다.

 

NFA의 규칙은 다음과 같다.

- RE를 parentheses로 둘러싸여 있는 것으로 본다.

- RE character당 하나의 상태가 있고, 맨 마지막 accept state까지 해서 M+1개의 상태가 존재한다.

- 두가지 state transition이 존재한다.

1) character를 scan하지않고, state를 바꾸는 ε-transition, 2) character를 scan하고 state를 바꾸는 black match transition

- transition이 accept state에서 끝나면, 패턴에 일치하는 문자열로 본다.

 

출처 : coursera, Princeton University Algorithm part2 lecture

 

3. NFA Simulation

 

NFA는 방향성이 존재하므로 Digraph로 표현할 수 있다. 그리고 특정한 state들에에 대해 바로 다음 시점에 도달 가능한 상태들은 DFS(Depth-first-search)의 reachability를 이용하면된다. 실행시간은 DFS의 실행시간인 E+V 이다. 

 

그런데 NFA는 아무런 문자 scan없이도 상태를 바꿀 수 있는 ε-transition이 존재하므로, 특정시점에 여러가지 존재가 가능한 상태들이 존재한다. 예를 들어, i번째 character를 scan한 후 현재 시점에 도달가능한 상태집합 A가 있다고 해보자. i+1번째 character를 scan한 후 transition하는 상태들은 상태집합 A의 부분집합 A'가 될 것이고, black match transition하게 될 것이다. 그런데, 이후에 ε-transition이 가능하므로, black match transition되어 변경된 상태들은  ε-transition하여 추가적으로 여러 상태들에 도달가능하다. 따라서 i+1번째 scan에서 reachable한 state는 black match transition이후의 상태들과,이후에  ε-transition한 가능하여 도달가능한 상태들의 합집합이 된다. 

 

출처 : coursera, Princeton University Algorithm part2 lecture

 

예를 들어, 입력문자열이 AABC이고, REs가 ((A*B|AC)D)라고 해보자. NFA는 위와 같이 표현된다.

Scan전 ε-transition으로 도달가능한 상태들은 (0, 1, 2, 3, 4, 6)이다.

첫번째 입력인 A를 scan한다. A가 2개 있으므로, 2개 모두 Black transition한다.

이후  ε-transition으로 도달가능한 상태까지 고려한다. 도달가능한 상태들은 (2, 3, 4, 7)이다. 

두번째 입력인 A를 scan한다. A가 1개 있으므로, Black transition한다. 도달가능한 상태들은 (2, 3, 4)이다.

세번째 입력인 B를 scan한다. B가 1개 있으므로, Black transition한다. 도달가능한 상태들은 (5, 8, 9)이다.

네번째 입력인 C를 scan한다. C가 없으므로 더 이상 진행할 수 없고 해당 문자열은 허용되지 않는다.

만약, AABC가 아니고 입력문자열이 AABD라면 어떻게 될까?

네번째 입력인 D를 scan한다. D가 1개 있으므로, Black transition한다. 도달가능한 상태들은 (10, 11)이다. 

전부 scan했음을 확인하고 상태들을 확인한다. accept state인 11을 포함하고있으므로, 해당 문자열은 허용된다.

 

NFA simulation의 실행시간은 worst case에서 MN을 보장한다. 이는 특정시점에 도달가능한 상태가 최대 M으로 제한되어있기 때문이다. 놀랍게도 이는 집합이 아닌 하나의 문자열에 대해서 Brute-force로 패턴을 찾을 때 걸리는 시간복잡도와 동일하다. 집합의 요소가 무한할수도 있다는 것을 고려하면 매우 놀랍다.

게다가 실제응용에서, 도달가능한 상태의 갯수는 M보다 훨씬 작기 때문에 선형인 N에 가깝게 동작하게 된다.

 

4. NFA construction

 

NFA로 패턴의 일치를 찾아내는 것까지는 위의 방법대로 할 수 있다.

그렇다면 주어진 RE로 NFA를 어떻게 생성해 낼까?

예를 들어, RE가  ((A*B|AC)D)라고 하자. Accept state의 character를 E라고 해보자.

Alphabet  -> next state인 경우를 black match transition으로 설정한다. 이 경우는  A*, AC, C), D) 이다.

Parentheses -> next state인 경우를  ε-transition로 설정한다. 여기서는 ((, (A, )D, )E

그렇다면, or인 | 기호는 어떻게 처리할까? 이것은 stack을 이용하여 처리할 수 있다.

왼쪽끝에서 오른쪽방향으로 RE를 scan해보자.

(, | 를 만나면 stack에 push한다. ) 를 만나면 pop한다.

만약, pop을 했을 때 나오는 기호가 | 이라면, 총 2개의 left parentheses -> | +1 ,  | -> right parentheses를 ε-transition으로 추가한다.

closure인 *은 black match transition이후 *이라면, 총 3개의 ε-transition을 추가한다.

결과는 아까 위에서 보았던 NFA가 된다.

 

NFA의 생성시간과 공간비용은 모두 M에 비례한다. 실행시간의 경우, RE의 모든 문자를 한번씩만 방문하고, ε-transition의 추가는 한 문자당 최대 3번이고, Stack operation도 기껏해야 2번이기 때문이다. 공간비용의 경우 Edge, State, Stack을 위한 공간이 필요한데, 이것도 모두 최대값이 제한되어 있다.

 

5. Applications

 

우리가 흔히 아는 grep의 경우도 RE의 응용이다. 입력값을 이용해 RE를 만들어내고, 특정 텍스트의 라인마다 검증하여 통과한 경우 출력한다. 

java에서도 input.matches(re)로 입력값 검증 할 수 있다.

 

참고로 RE의 사용을 우리는 주의해야한다.

grep, java, perl, python 등으로 구현된 RE는 실행시간을 보장하지 않는다고 한다.

(우리가 작성한 RE가 NFA로 구현되지 않았다는 의미일 거 같다... 즉  NFA의 존재성을 보장하지 못하고, MN의 실행시간을 보장하지 못할 것이다. 하지만 우리가 작성한 RE로 NFA를 직접 구현하여 Kleene's theorm을 증명하고 MN의 실행시간을 보장하도록 할 수 있을 것이다...!) 

또한, Regular하지 않은 표기법을 이용하여 RE를 작성한 경우 Kleen's theorem을 만족하지 못하므로, 성능을 보장하지 못한다. 특히 back-reference의 경우 다루기가 매우 힘들다.만약, Kleen's theorem을 만족하지 않는 RE를 작성하여 프로그램을 구현했을 경우, 이것은 SpamAssasin공격과 같은 형태에 취약할 수 있다. 입력값에 대해, 실행시간은 Exponentional하게 늘어날 수 있다.

 

이것은 또한, 컴퓨터 이론에 있어서 하나의 중요한 추상화을 보여주는데,KMP는 string => DFA,grep은 RE => NFA,java compiler는 java language => java byte code

java compiler는 program이라는 pattern을 JVM이라는 simulator로 실행하여 legal한지 여부를 체크하여 byte code라는 Machine을 만드는 것으로 볼 수 있다.

즉, 위의 세가지는 모두 pattern을 simulation하여 legal여부를 파악하고 machine을 만드는 것으로 추상화 시킬 수 있다.