혼자 정리

finite accepter의 equivalence는 두 accepter가 accept하는 set이 동일하고, reject하는 set이 동일하다고 정의. def) Two finite accepters, $M_{1}$ and $M_{2}$, are said to be equivalent if $$ L(M_{1}) = L(M_{2}), $$ that is, if they both accept the same language. Theorem) Let $L$ be the language accepted by a nondeterministic finite accepter $M_{N} = (Q_{N}, \Sigma, \delta_{N}, q_{0}, F_{N} )$. Then there exists a determ..

Nondeterministic Finite Accepter def) A nondeterministic finite accepter or nfa is defined by the quintuple $$ M = (Q, \Sigma, \delta, q_{0}, F) , $$ where $Q$, $\Sigma$, $q_{0}$, $F$ are defined as for deterministic finite accepters, but $$ \delta : Q \times ( \Sigma \cup { \lambda } ) \rightarrow 2^{Q}. $$ DFA와의 차이 $\delta$의 range(치역)가 $2^{Q}$의 powerset. 여러 state로 이동 가능 공집합도 가능 input으로 $\lambd..

오토마타의 한 종류인 finite accepter의 특징은 다음과 같다. 임시 storage를 갖지 않음 input 파일의 내용을 수정할 수 없기 때문에 계산 과정에서 무언가를 '기억'하는 것에는 한계를 가짐. 제한된 정보는 control unit의 state를 조정하는 것을 통해서만 기억될 수 있다. 그런데 그러한 state 수는 유한하므로 finite 오토마타는 특정 시점에 저장되는 정보가 엄격하게 제한되는 상황만 처리 가능하다. Deterministic Finite Accepters def) A deterministic finite accepter or dfa is defined by the quintuple $$ M = (Q, \Sigma, \delta, q_{0}, F), $$ where $Q$..

Automata 디지털 컴퓨터의 추상화된 모델. input file에 기록된 alphabet들로 이루어진 string을 input으로 입력받는다고 가정. (수정 불가) input file은 cell로 구분되고, 각 cell은 하나의 symbol을 담고 있다. input 메커니즘은 왼쪽에서 오른쪽으로 input string의 symbol을 한 번에 하나씩 읽어들이고 EOF 조건을 인식하여 input string의 끝을 감지할 수 있다. 기계는 output을 생성할 수도 있다. cell 갯수 제한이 없는 임시 storage 장치를 가질 수 있고 하나의 cell은 하나의 symbol만 가질 수 있다. 기계는 storage cell의 내용을 읽고 수정할 수 있다. 오토마타는 control unit을 가지고 이는..

Language alphabet : 하나 이상의 symbol의 finite set string : alphabet에 속하는 symbol의 finite sequence ex) alphabet $\Sigma = { a, b }$이면 $abab$, $aaabbba$ 는 $\Sigma$의 string concatenation of two strings $w$ $v$ : $v$의 symbol들을 $w$의 오른쪽 끝에 붙이는 것. ex) $w = a_{1}a_{2}a_{3}$ and $v = b_{1}b_{2}b_{3}$ 이면, $wv = a_{1}a_{2} \cdots a_{n}b_{1}b_{2} \cdots b_{m}$. reverse of a string $w$ : $w^{R} = a_{n} \cdots a_..