11 - Automata <-> Regular Expression

이번엔 오토마타에서 Reqular Expression으로 변환하는 과정을 알아보도록 하자

 

바로 바꾸기 보다는 Formal language로 바꾼 뒤 변환하는게 이해하기가 더 쉽기 때문에 

Formal language로 변환하는 과정 먼저 알아보자

 

 

이 오토마타를 Regular Expression으로 변환해보자

 

먼저 Formal Language로 변환하면 이러한 모양이 된다.

 

p -> 0q | 1p
q -> 0r | 1p
r -> 0r | 1r | epsilon

이를 Regular Expression으로 변환하면

[1] p = 0q + 1p
[2] q = 0r + 1p
[3] r = 0r + 1r + epsilon

이 된다. 먼저 [3]을 정리하면 r = (0+1)r + epsilon = (0+1)* 이 되고,

이를 [2]에 대입하면

q = 0r + 1p = 0(0 + 1)* + 1p

이 되는데, 0(0 + 1)* + 1p를 다시 [1]에 대입하면

p = 0q + 1p = 0(0(0 + 1)* + 1p) + 1p

가 된다. 분배해서 풀면

00(0 + 1)* + 01p + 1p

가 되고, p로 묶으면

(01 + 1)p + 00(0 + 1)*

가 된다. 

결국 p는 자기 자신에게 돌아오기 때문에 * 전체로 표기할 수 있으며 총 정리하면

 

L(M) = (01 + 1)*00(0 + 1)*이 된다.