Turing Machines 튜링 기계 - Cell들로 구성된 Tape(1D Array)를 Temporary Storage로 하는 Automata이다. - 각 Cell에는 하나의 Symbol을 저장할 수 있다. - Tape는 양쪽으로 무한히 확장될 수 있어 무한한 양의 정보(Symbol)을 저장할 수 있다. - Symbol을 임의의 순서로 Read/Write할 수 있다. The Standard Turing Machine (표준 튜링 기계) Definition 9.1 Turing Machine \(M = (Q, \Sigma, \Gamma, \delta, q_0, \Box, F)\) Elements Description \(Q\) Internal State들의 집합 \(\Sigma\) Input Alphab..
Properties of Context-Free Languages 문맥-자유 언어의 성질들 Two Pumping Lemmas (두 펌핑 보조 정리들) Theorem 8.1 A Pumping Lemma for CFL Infinite CFL \(L\)이 있다하자. \(|w| \geq m\) 인 모든 \(w \in L\)에 대해, \(|vxy| \leq m, |vy| \geq 1\)인 \(m\)에 대해 \(w = uvxyz\) 로 나타낼 수 있고, (분할할 수 있고,) 모든 \(i = 0, 1, 2, \cdots\)에 대해, \(uv^ixy^iz \in L\) 이다. (\(v, y\)가 Pumping된다.) ※ 이 Pumping Lemma는 어떠한 Language가 CFL군에 속하지 않음을 입증하는데 유용하다..
Pushdown Automata 푸시다운 오토마타 * Pushdown Automata (PDA) - Stack을 저장장치로 갖는 Finite Automata이다. - Stack은 무한한 크기(Unbounded)를 갖는다 가정하기 때문에, 이를 통해 제한된 메모리로부터 나오는 한계를 극복할 수 있다. - Finite Automata는 유한한 메모리 크기로 인해, Context-Free Language를 인식할 수 없다. - Nondeterministic PDA는 Context_Free Language를 인식할 수 있다. - Deterministic PDA는 Deterministic Context-Free Language를 인식할 수 있다. Nondeterministic Pushdown Automata (비..
Simplification of Context-Free Grammars and Normal Forms 문맥-자유 문법의 단순화와 정규형 * Simplication for Context-Free Grammars (단순화) - 필요없는 변수와 생성규칙을 제거하는 과정을 의미한다. 1. \(\lambda\)-Production을 제거한다. (Theorem 6.3) 2. Unit-Production을 제거한다. (Theorem 6.4) 3. Useless Production을 제거한다. (Theorem 6.2) * 편의를 위해, 이 장에서는 Language \(L\)이 \(\lambda\)를 생성하지 않는다고 가정한다. - 만약 \(\lambda\)를 생성하는 경우를 고려해야 한다면, 기존의 생성규칙의 시작변수..
Context-Free Languages 문맥-자유 언어 * Parsing (파싱) - 문장을 문법적 유도를 통하여 설명하는 과정이다. - 문장의 구조를 표현하는 방법 중 하나이다. - \(L(G)\)에 속하는 \(w\)가 유도되는데 사용된 일련의 생성규칙들을 찾는 과정이다. Context-Free Grammars (문맥-자유 문법) Definition 5.1 CFG (Context-Free Grammar; 문맥-자유 문법) 문법 \(G = (V, T, S, P)\) 에서 모든 생성 규칙이 \(A \to x\) \((A \in V, x \in (V \cup T)^*)\) 의 형태를 가지면, \(G\)를 문맥-자유 문법(CFG)이라 한다. ※ CFG의 생성규칙에서 왼쪽항엔 하나의 변수, 오른쪽 항에는 Sy..
Properties of Regular Languages 정규 언어의 성질 - 어떤 언어가 Regular Language가 아님을 입증하기 위해서는, 해당 언어가 Regular Language의 성질을 만족하지 않음을 보여야 한다. Closure Properties of Regular Languages (정규 언어의 폐포 성질) Example. 어떤 Regular Language \(L_1, L_2\)가 있으면, \(L_1\)과 \(L_2\)의 합집합 또한 Regular Language이다. 이를 두고, "The Family of Regular Language is Closed under Union."라 표현한다. ("정규 언어군은 합집합에 대해 폐포되어 있다."라 표현한다.) Closure under ..
Regular Languages and Regular Grammars 정규 언어와 정규 문법 Regular Expression (정규 표현) * Definition 3.1 (The Primitive Regular Expression; 기본 정규 표현) 주어진 알파벳 \(\sum\)에 대해, \(\phi, \lambda, a \in \sum\)는 모두 정규 표현이다. (이들을 Primitive Regular Expression이라 부른다.) \(r_1\)과 \(r_2\)가 정규표현이면, \(r_1 + r_2, \quad r_1 \cdot r_2, \quad r_{1}^{*}, \quad (r_1)\) 등은 모두 정규 표현이다. 특정 문자열이 정규 표현이 되기 위해서는, 기본 정규 표현에서 시작하여 위 규칙..
Finite Automata 유한 오토마타 * Finite Accepter (유한 인식기) - 유한 개수의 State를 가지며, Temporary Storage를 가지지 않는 오토마타를 의미한다. - 유한 인식기는 Input File을 수정/저장할 수 없어, 계산 중 필요한 정보를 저장하는 데 제한을 가진다. - String(문자열)을 Accept(승인) 혹은 Reject(거부)하기 때문에 Accepter(인식기)라 부른다. - 유한 인식기는 간단한 패턴 인식 메커니즘으로 볼 수 있다. * DFA (Deterministic Finite Accepter; 결정적 유한 인식기) - Regular Language(정규 언어)를 정의하기 위해 사용하는 오토마타이다. - Deterministic(결정적)이란, 하..
