Finite Automaton의 각 State에서 Accept State까지 갈 수 있는 String의 집합을 변수로 두면 Language Equation을 만들 수 있다. Arden’s Theorem은 반복 구조가 포함된 이 방정식을 푸는 도구이다.

Theorem

Language , , 미지 Language 에 대해

이고 이면 유일한 해는

이다.

오른쪽 반복이 나타나는 형태

의 해는

이다.

왜 인가

식에 반복 대입해 본다.

계속 반복하면

가 된다. 반복 부분을 모두 모으면

이다.

조건

이면 를 만족하는 해가 여러 개일 수 있다. 예를 들어 , 이면 방정식은 가 되어 모든 Language가 해이다. 따라서 유일성을 위해 조건이 필요하다.

State Equation 작성법

DFA의 각 State 에 대해 변수 를 둔다. 는 State 에서 시작하여 Accept State에 도달하게 하는 String의 Language이다.

State 에서 Symbol 로 로 간다면 가 식에 포함된다. 자체가 Accept State라면 도 포함한다.

예제

두 State , 이 있고

  • 에서 0은 , 1은 로 이동한다.
  • 에서 0과 1은 모두 에 남는다.
  • 이 Accept State이다.

State Equation은

이다.

두 번째 식에 Arden’s Theorem을 적용하면

이다. 첫 번째 식은

이므로

이다. 이는 적어도 하나의 1을 포함하는 Binary String의 Language이다.

다른 변환 방법

  • Thompson Construction은 RE를 ε-NFA로 바꾼다.
  • Subset Construction은 NFA를 DFA로 바꾼다.
  • State Elimination은 Automaton을 Generalized NFA로 보고 State를 제거해 RE를 구한다.
  • Arden’s Theorem은 State Equation을 대수적으로 해결한다.

정리

  • Arden’s Theorem은 꼴의 Language Equation을 푼다.
  • 이면 유일한 해는 이다.
  • Automaton의 State마다 Accept까지의 Language를 변수로 두면 RE를 계산할 수 있다.

연습 문제

1번

다음 Language Equation을 푼다.

2번

다음 연립 Language Equation을 순서대로 해결한다.

풀이

1번

이므로 Arden’s Theorem을 적용한다.

2번

먼저

이다. 이를 첫 식에 대입하면

이므로

이다.