10 - Convert Grammer <-> Finite Automata

 

처음에 배웠던 Formal Language 에서 Finite Automata로 변환하는 방법을 알아보자.

 

Formal -> Automata

---

S -> 0S
S -> 1B
S -> 1
B -> 0S
B -> 1

앞의 0과 1이 선택지이고, 뒤에 문자가 도착지 이므로, automata 표로 이렇게 나타낼 수 있다.

해당 automata를 그림으로 표현하면 이와 같이 표현할 수 있다.

f는 S->1과 같이 선택지가 더이상 없을경우 finish이기 때문에 f가 되는것이다.

 

 

Automata -> Formal

---

이 오토마타를 formal lang으로 바꿔보자

 

사실 Automata Design에서 Formal language로 바꾸는데에는 바로 보고 바꿀수 있다.

그림에서 p가 1일때 q로 가고 하는 걸 쭉 정리하면 formal lang이 되기 때문이다.

그래서 전부 바꾸면

 

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

이 된다. 

r은 finish 이기 때문에 epsilon(finish)라는 식도 적어 주어야 한다.