어제 유도 트리를 만들면서, 사용하지 않는 터미널을 제거하는 과정이다. 사용하지 않는 production Rules 제거 Non-Terminal 중에서, Terminal 로 갈 수 있는 것들을 Terminating Non-terminal 이라고 하고, 이 Termination Non-terminal을 제외하고 모두 제거해야한다. 그리고, 존재하지만 갈 수 없는 경우의 수가 있다. 접근 가능한 터미널들을 Accessible Symbol이라고 하고 해당하지 않는건 제거해야한다. Termination Non-terminal S -> A S -> B B -> a 이와 같은 식이 있다. 여기서 termination non-terminal은, 마무리가 terminal이 되야한다는 뜻이다. S -> B -> a 이기..

이번엔, analyzer를 통해 정제된 데이터중 ID를 Finite Automata로 변환해 보자. ID (변수명)은 첫번째가 letter이여야 하고 그 이후에는 Digit 또는 letter이여야 한다. ID to Automata 이를 오토마타로 바꾸면, 가 된다. 식으로 나타내기 위해 편의상 letter는 l로 digit은 d로 표기하도록 하자 S = lA A = lA + dA + epsilon 이 된다. A로 묶으면 A = (l + d)A + epsilon이 되고, 정리하면 A = (l + d)* 가 된다. A를 S식에 대입하면 최종으로 S = l(l + d)* 이 된다. 해석해보면 처음엔 letter, 그 이후로는 l 또는 d가 무작위로 나올 수 있다는 뜻이다. Integer to Automata ..

이번엔 DFA에서 State를 줄여나가는 방법이다. 먼저 state를 2개로 만든 모양이다. 빨간색 부분을 1구역, 파란색 부분을 2구역 이라고 보자. 1구역에는 A, B, D가 있고 2구역에는 C,E가 있다. ABD는 각각 a 일때 1구역에 머물러있고, b 일때는 A는 1로, 나머지는 2구역으로 이동한다. 표로 정리하면 이렇게 된다. a일 경우와 b가 같아야 한 state로 묶을 수 있으며, 현재 ABD state는 B,D경우가 다르므로 하나의 state로 만들 수 없다. 그러면 좀 더 쪼개서 3개의 state로 만들어보자. 구역을 3개로 나누어 보았다. 이렇게 되면 각 구역에서 선택지에 따라 일정한 곳으로 이동하게 된다. 이러한 식으로 정리가 가능하다. 그럼 각각 1, 2, 3을 다시 오토마타로 만들..

오토마타 경우의 수중에 ε는 아무 조건 없이 갈 수 있는 경우를 말한다. 이 경우를 묶어서 ε-closure라고 부른다. ε - NFA 예시 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으로 갈 수 있는 터미널들을 정의하고 직접 가보..

Non-Deterministic Finite Automata(NFA) 는 어디로 갈지 확실하게 정해지지 않은 오토마타이다. q0에서 선택지가 a일때 , q1일수도 있고 q2일수도 있다는 이야기이다. 그래서 이러한 NFA를 Deterministic Finite Automata(DFA)로 바꾸어야 하는게 목표이다. NFA의 예시 이와 같은 그림으로 나타낼 수 있다. 근데 경우의 수에 따라 화살표가 정해지지 않으니 좀 헷갈리는 부분들이 많이 있다. 이 오토마타에 1001을 입력하면 어떻게 될까?δ∪ 먼저 q0 에서 시작하기 때문에 δ({q0}, 1011) 에서 시작한다. 시작에서 1이면 q1또는 q3으로 갈 수 있다. δ({q1,q3}, 011) 가 된다. 이는 δ(q1, 11) ∪ δ(q2, 11)로도 표기..