Finite-state 오토마타로부터 짧은 정규 표현식을 구하기 = Shorter Regular Expressions from Finite-state Automata

국문 초록 (Abstract)

State 제거법은 주어진 finite-state 오토마타로부터 정규 표현식을 구하는 매우 직관적이며 구현이 쉬운 효율적 방법이다. 이 방법의 한 가지 특성은 state 제거 순서에 따라 같은 오토마타(즉 같은 정규 언어)에 대해 길이가 다른 정규 표현식이 만들어진다는 점이다. 우리는 주어진 오토마타의 구조적 특성을 살펴보고 이를 이용해 state 제거 법을 통한 짧은 정규 표현식을 구하는 알고리즘을 개발하고 이를 구현한다. 좋은 state 제거 순서를 찾기 위해 bridge state를 정의하고 이를 이용한 vertical chopping, 오토마타 내 state의 독립된 그룹을 찾아내는 horizontal chopping 그리고 각 state의 transition 복잡도를 바탕으로 하는 state weight 이 세 가지 state 제거 방법을 이용한다. 이 세 가지 방법은 개별적으로 적용되었을 때 보다는 서로 함께 사용될 때 더 나은 state 제거 순서를 찾을 수 있다.

목차 (Table of Contents)

• 요약
• 1. 서론
• 2. 예비지식
• 3. 세로 쪼개기, 가로 쪼개기 및 State Weight
• 4. 결과 분석
• 5. 결론
• 참고문헌