1 Automata, The Methods and the Madness
1.1 Why Study Automata Theory
문제 해결 가능성 - 풀 수 있는 문제인지 판별하고, 풀이 불가능한 영역인지 판별
계산 효율성 - 문제를 해결하기 위한 자원 사용이 현실적인가?
위의 본질적 한계를 이해하며 이론적이고 추상적인 기계를 연구하는 것이 목적이다.
1.1.1 인식의 경계선
내가 어떤 것을 완전히 이해하고 설명할 수 있는가? 단순히 많이 배운다고 해결될 문제가 아니다. 나라는 체계가 그것을 어디까지 알고 있을까?
나는 내가 사용하는 논리 체계로 그 논리 체계 자체를 완전히 해석할 수 있을까? → 이는 자기참조의 한계다.
내가 모른다는 것을 아는가? 어떤 문제는 풀 수 없다. 어떤 문제는 증명할 수는 없지만 참이다. 어떤 문제는 계산이 너무 오래 걸리기 때문에 현실적으로 사용하기 어렵다. 정말로 풀 수 없기 때문에 모르는 것인지, 증명할 수 없기에 모르는 것인지, 방법은 알고 있지만 그를 보이는 시간이 너무 오래 걸려서 모르는 것인지
나는 내가 무엇을 모른다는 사실조차 인식하지 못할 수 있다. 그러나 그 무지는 내 사고의 바깥이 아니라 내부에 존재한다.
1.2 FA(Finite Automata)
유한 오토마타는 유한한 수의 상태를 가지는 결정적 또는 비결정적 계산 모델이다.
Q - 유한 상태 집합
Σ - 입력 집합
δ - 전이 함수: 현재 상태와 입력을 이용해 새로운 상태로 전이시키는 함수
q0 - 시작 상태
F - 최종 상태
1.3 DFA(Determinstic Finite Automata)
유한 오토마타의 한 종류로, 현재 상태에서 입력에 대해 전이 결과가 이미 결정되어 있는 모델이다. 현재 상태에서 두 개의 상태로 나뉘어지지 않는다.
DFA는 입력의 구조가 명확하고 상태의 개수가 유일할 때 표현가능하다. 예를 들어 q0 -> q1 -> q2 -> F처럼 상태 전이가 이미 결정되어 있는 경우 표현이 가능하다.
표현하기 어려운 예로는, a문자열 n개와 b문자열 n개로 구성된 입력을 판별하는 경우가 있다. a의 개수와 b의 개수를 비교하려면 상태를 n만큼 계속 늘려야 하므로, 이러한 언어는 유한 오토마타로는 표현할 수 없다.