[Automata Theory] Regular Expression

What is Regular Expression?

정규식(Regular Expression, 일명 Regex)은 웹개발을 해보았거나 코딩을 어느정도 해보았다면 익숙한 개념일 것이다. 이번에는 가장 기초적인 정규식을 정의해보고, 이로 인해 만들어지는 정규언어에 대해 알아보자. 

 

엄밀히, 정규식은 언어를 식으로 표현하는 방법이다. $\Sigma$상의 정규식 $r$이 표현하는 언어를 $L(r)$이라고 하면 정규식은 다음과 같이 귀납적(inductive)하게 정의할 수 있다.

 

1. $\boldsymbol{\phi}$는 정규식이고 $L(\boldsymbol{\phi})=\phi$이다.
2. $\boldsymbol{\epsilon}$은 정규식이고, $L(\boldsymbol{\epsilon})=\{\epsilon\}$이다.
3. 모든 $a\in \Sigma$에 대해 $\boldsymbol{a}$는 정규식이고 $L(\boldsymbol{a})=\{a\}$이다.
4. $r, s$가 정규식이면 $r+s$도 정규식이고 $L(r+s)=L(r)\cup L(s)$이다.
5. $r, s$가 정규식이면 $rs$도 정규식이고 $L(rs)=L(s)\cdot L(s)$이다. (Concatenation)
6. $r$이 정규식이면 $r^*$도 정규식이고 $L(r^*)=L(r)^*$이다. (Kleene Star)
7. $r$이 정규식이면 $r^k$도 정규식이고 $L(r^k)=L(r)^k$이다. 

Note

• 원칙상 정규식은 알파벳의 문자와 구별하기 위해 볼드체로 쓰는 것이 맞지만, 문맥상 구별할 수 있기에 주로 생략한다.
• 4번의 '+' 연산자는 흔히 사용하는 정규식에서의 '|'와 같다.
• 편의를 위해 연산의 순서는 '*', '$\cdot$', '+' 순으로 한다.

Examples

이제 $\Sigma=\{0,1\}$상에서의 정규식을 예와 함께 살펴보자.

 

1. $L(01^*)=\{0, 01, 011, 0111, \cdots\}$
2. $L((01)^*=\{\epsilon, 01, 0101, 010101, \cdots\}$
3. $L(10+01^*)=\{0, 01, 10, 011, 0111, \cdots\}$

위처럼 정규식을 이용하면 특정 알파벳에서 많은 언어를 간단히 표현할 수 있다. 이를 잘 가지고 놀아보길 바란다.

 

 

 

* 이 글은 서울대학교 박근수 교수님의 '오토마타이론' 강의자료에 기반을 두고 있고, 교수님의 허락을 받고 포스팅을 진행함을 밝힌다.