Arden's Rule에 대하여

 

 

 

---

Arden's Rule에 대하여

---

 

 

 

오늘은 Arden's Rule에 대해서 알아보고, 직접 증명할 예정입니다.

Arden's Rule은 주로 DFA를 RE로 바꿀 때 주로 쓰인다고 합니다.

이 rule을 사용할 때 두 가지 표현방법이 있는데, 개인적으로 너무 헷갈려서 미리 작성하고 시작합니다.

고고

 

 

 

 

0. What is Arden's Rule?

 

일단 Arden's Rule 자체에 대해서 알아봅시다.

Arden's Rule에 대해서 간단히 알아봅시다.

 

Arden's rule states that the set A*⋅B is the smallest language that is a solution for the set X in the linear equation X = AX+B. i.e) X = AX + B, then X=A*⋅B X = XA + B, then X=B⋅A*

 

결론적으로 밑에 써져있는 두 식만 쓸 줄 알면 됩니다.

표현 자체는 음~그렇구나 하고 넘어갑시다. 증명은 뒤에서 할 예정입니다.

 

 

 

 

 

1. 두 가지 표현방법

 

위 Theorem에서 보이다시피 Arden's rule을 표현하는 방법은 총 2가지가 있습니다. 개인적으로 공부할때 너무 헷갈려서 따로 정리했습니다.

 

설명은 다음 dfa를 기준으로 작성할 것입니다. dfa 자체는 단순히 1의 odd parity check를 기능할 수 있는 dfa입니다.

 

 

1. Outgoing

 

말 그대로 '나가는'이라는 뜻입니다. 한 state를 기준으로 어떤 transition을 타면 어떤 state에 도달하는지를 중심으로 나타내는 방법입니다. 위의 dfa는 다음과 같이 표현됩니다.

 

A = 0A + 1B B = 0B + 1A + λ

 

이렇게 말로만 서술하면 와닿지 않으니 설명을 직접 봅시다.

 

이런 늑김

기호랑 같이 보시면 뜻이 잘 이해될 것 같습니당

 

 

2. Incoming

 

Outgoing과는 반대로, 기준 state에 도달하기 위해서 어떤 transition을 타야하는지 나타내는 방법입니다. 표현하면 다음과 같이 표기됩니다.

A = A0 + B1 B = A1 + B0 + λ

 

이것도 설명과 함께 봅시다

 

오키오키?

 

표기만 보면 자리만 바뀌어있고 뭐야 저게...싶어서 미리 설명합니다. 헷갈리지 말자!

 

 

 

 

 

 

 

2. Arden's Rule - Proof

 

그럼 본격적으로 증명을 해봅시다. 증명 자체는 첫 번째 수식(X = AX + B, then X=A*⋅B)을 통해서 증명하도록 하겠습니다.

별거 아닙니당 고고

 

Arden's Rule은 두 가지를 증명하면 끝입니다.

1. X=A*⋅B는 X = AX + B의 해이다.

2. X=A*⋅B는 X = AX + B의 해 중 유일하다. 즉, 가장 작다.

 

1번은 다음과 같이 증명됩니다.

 

2번은 다음과 같이 증명할 수 있습니다.

 

 

개인적으로 왜 2번 증명과정에서 갑자기 X=A*⋅B를 대입하는지는 잘 모르겠습니다.. 근데 뭐 유튜브 아조씨가 맞다니깐

두 번째 수식도 첫 번째 수식과 동일하게 증명하면 되겠죠?

 

Arden's Rule 끝!

 

참고 : www.youtube.com/watch?v=Idl_0mPzZjE