8 - Regular Expression (ε-NFA)

오토마타 경우의 수중에 ε는 아무 조건 없이 갈 수 있는 경우를 말한다.

이 경우를 묶어서 ε-closure라고 부른다.

 

 

 

ε - NFA 예시

---

ε기호를 넣을 수 없어 e로 대체합니다

 

1에서 epsilon을 통하여 무조건 갈 수 있는 경우를

e-closure(1)이라고 표현합니다.

 

closure(1)일때 a가 주어지면 2로 가게되고 2에서는 epsilon으로 갈 수 있는 곳이 없기 때문에

자기 자신 closure(2)가 됩니다.

c가 주어진다면 3으로 이동하게 되고 3에서는 epsilon으로 4로 이동할 수 있기 때문에

closure(3)이 되고 자기 자신과 4를 포함한 [3,4]가 됩니다.

 

이 방법은 DFA로 변환할 때 2의 n승 만큼 터미널을 만드는게 아니라 e-closure를 통해 epsilon으로 갈 수 있는 

터미널들을 정의하고 직접 가보면서 DFA를 정의하는 개념이다.