이번엔 오토마타에서 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)* 이 되고..

처음에 배웠던 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 사실 Automata Design에서 Formal language로 바꾸는데에는 바로 보고 바꿀수 있다. 그림에서 p가 1일때 q로 가고 하는 걸 쭉 정리하면 formal lang이 되기 때문이다. 그래서 전부..

Formal Language는 4가지 구성요소로 이루어져 있다. 구성요소 Vn - 생성 규칙을 나타내며 알파벳 대문자로 나타낸다. Vt - 실제로 나타내는 string을 나타내며 알파벳 소문자로 나타낸다. P - 생성 규칙 전체를 말한다. S - Starting Symbol, 시작을 나타낸다. 예제 1) P : S -> aA A -> 1 A -> k A -> _3 a(Vt) 는 실제로 나타내는 언어이기 때문에 그대로 둔다. A(Vn)은 생성 규칙으로 1이나 k, _3으로 치환될 수 있다. 즉 S는 a1, ak, a_3이 될 수 있다. A에 관한 식들은 A -> 1 | k | _3 으로도 표현이 가능하다. 2) P: S -> aA | bB | ε A -> bS B -> aS Vn = {S, A, B} Vt..