GDSC Ewha 아침 스터디 TIL 7일차 💛

오늘 GDSC 아침 스터디 시간에는 1. 오토마타 및 형식언어 강의(영어강의)를 수강했습니다!

수업의 전반부에서는 finite automata 의 두 종류인 Deterministic Finite Acceptor 와 Nondeterministic Finite Accepter 의 equivalence 를 학습하였고 후반부에서는 지금까지 배운 개념을 활용해 예제를 풀어 보았습니다. (강의 자료는 저작권 문제로 업로드 하지 않았습니다!!) 먼저 교수님께서 지난 수업 시간에 배운 NFA 에 대해 간단히 recap 해 주셨습니다. NFA 의 Formal definition 은 DFA 와 거의 모든 부분에서 동일하나 델타값이 의미하는 바가 NFA에서는 function 이 아닌 transition relation 이라는 차이가 있었습니다. Formal Defitnition 에서의 차이 외의 DFA에는 없는 NFA 의 특징으로는 첫째, NFA 는 multiple transtion이 가능하다는 것, 즉 델타의 값이 single state 가 아닌 2^q개가 될 수 있다는 점, 둘째, 람다 transition이 가능하다는 것, 즉 화살표의 이동 없이 state 를 변경하는 것이 가능하다는 점, 셋째 no transition 인 상태를 만드는 것이 가능하다는 것, 즉 state 가 다른 state 를 가리킬 의무가 없다는 점이었습니다. 본격적인 수업으로 Equivalence of Machines 에 대해 학습했습니다. NFA DFA 여부에 관계없이 두 머신이 같다는 것은 L(M1) = L(M2) 를 뜻합니다. 예를 들어 NFA 로 이루어진 M1의 output 이 {10}* 이고 DFA 로 이루어진 M2의 output 이 {10}*으로 서로 같다면 M1과 M2는 서로 equivalent 합니다. 증명 과정은 모든 DFA 가 작게 쪼개면 NFA 가 된다는 것을 보여줌과 동시에 어떠한 NFA 도 동일한 DFA 로 바뀔 수 있음을 보여줌으로써 진행됩니다. 이를 위해 NFA 를 DFA 로 바꾸는 방법에 대해 학습하였습니다. NFA 를 DFA 로 변환하는 방법은 첫째, initial state of NFA 를 initial state of DFA 로 바꾸기, 둘째, NFA의 모든 state 들을  compute 해서 하나의 single state 로 바꾸어 주기, 셋째 NFA 의 final state 에 있는 qj 에 대해 DFA 의 qj를 포함하고 있는 state 를 모두 final state 로 지정하기 입니다. 이러한 일련의 증명 과정을 통해 도출해낸 결과는 DFA가 accept 하는 regular language 를 NFA 역시 똑같이 accept 할 수 있다는 것입니다.