DFA지난 글에서 오토마톤에 대해 정리하면서 오토마톤은 다양한 기준으로 분류할 수 있다고 하였다.그 중에서 이번 글에는 DFA 오토마톤에 대해 정리해보려고 한다. DFA (Deterministic Finite Accepter)는 지난 내용에 따라 다음과 같이 이해할 수 있다. - 결정적이며 (Deterministic, 각 상태에서 주어진 입력에 대해 갈 수 있는 경로가 유일하다.)- 유한한 (Finite, 메모리 == 저장공간이 유한하다.)- Accepter (기계의 output 이 yes(accept) / no(reject) 로 이진적이다.) DFA는 오토마톤의 일종이지만, 특이하게 temporary storage 가 없다.그렇다고 저장공간이 없는 것은 아니고, control unit 에 마치 플립플..
오토마톤은 디지털 컴퓨터에 대한 추상적인 모델이다.디지털 컴퓨터는 기본적으로 입력이 주어지면 저장공간을 활용하여 이를 적절히 처리한 뒤 결과물을 내보낸다. 이때 입력 데이터는 수학적 편의를 위해서 '알파벳 심볼에 의해 정의된 문자열' 이라고 정의한다. (꼭 이래야만 하는 것은 아니다)그리고 인풋 파일은 무한한 길이의 테이프로부터 문자열을 읽어들일 수 있다고 생각한다.이 테이프는 여러개의 셀로 구성되어 있으며, 각 셀에는 알파벳 심볼 하나가 저장된다. 디지털 컴퓨터는 내부적으로 연속된 시간이 아니라, 이산적인 시간 체계로 동작하며,각 시간마다 인풋 파일의 왼쪽에서 오른쪽을 향해 한번에 하나의 셀(심볼)을 읽어들인다.그리고 End-Of-File (EOF) 신호를 통해 문자열의 끝을 감지할 수 있도록 기계가 ..
Language우리가 사용하는 자연어나 프로그래밍 언어에는 공통점이 있지만, 이를 명확하게 규정하는 것이 쉽지 않다.따라서 우리가 사용하는 언어를 더 쉽고 엄밀하게 다루기 위해서, 언어를 수학을 통해 추상화 해보려고 한다.그리고 이렇게 추상화된 언어를 Formal Language 라고 한다. alphabet 알파벳 ∑ = symbols 로 구성된 공집합이 아닌 유한집합 ∑ = {a, b} => 이 알파벳을 사용하여 만드는 언어는 a, b 로만 구성될 수 있다.∑ = {0, 1} => 이 알파벳을 사용하여 만드는 언어는 0, 1 로만 구성될 수 있다. String유한한 길이를 갖는 symbols의 나열 (무한히 나열한 것은 아니다.)위 예시에서의 알파벳을 사용하여 문자열을 구성한다면 다음과 같은 문자열을 ..
오토마타를 공부할 때는 집합, 그래프, 증명 기법과 관련된 기본적인 이산 수학 지식이 필요하다.관련된 수학 지식을 가볍게 정리하는 것으로 정리를 시작해본다. (정리 예정.. 사실 정리하다가 브라우저가 갑자기 꺼져서 날아감 ㅠㅠ)
