computation theory (3) -regular expression

    Regular expression(RE)은 다음과 같이 정의한다.

R is regular expression if R is

   Regular expression은 circular definition이라고 오해할 수 있지만 R은 R1, R2보다 항상 크기 때문에 귀납적으로 증명할 수 있다.

Regular expression은 DFA와 language를 recognize하는 descriptive power가 같다. (RE를 DFA로 변환하는 것으로 증명한다.) 따라서 DFA, NFA, RE 모두 동일한 descriptive power를 가지고 있다.