나름 개발자의 IT블로그

Pigeonhole Principle (비둘기집 원리) Pumping Lemma를 위해 Pigeonhole Principle을 먼저 소개한다. $N+1$개의 변수를 $N$개의 공간에 넣으면 적어도 하나의 공간에 $2$개의 변수가 있다. 너무 당연한 말이라 직관적으로 생각하기 쉽고 간단한 원리이다. 위에서는 $N+1$개의 변수라고 했는데 이를 일반화 할 수 있다. 증명은 여기 Pumping Lemma (for DFA) 여러 종류의 머신에 대한 Pumping Lemma가 있는데 지금 우리는 DFA만 알고 있으니까 DFA용 Pumping Lemma를 알아보자. (튜링머신은 너무 복잡해서 Pumping Lemma를 적용하기 힘들다.) $N$개의 상태를 가지는 어떤 DFA M이 길이가 $N$인 String을 AC..

DFA (Deterministic Finite Automata) 이제부터 전자계산기의 동작을 알아보도록 하자. DFA는 이름에서 알 수 있듯 "결정적인 유한 오토마타"이다. 상태는 유한하고 어떤 상태에서 어떤 입력이 들어오면 이동하는 상태가 정해져있다는 뜻이다. DFA 는 다음으로 이루어져있다. $M = (Q, \Sigma, q, F, s)$ $Q$ : DFA상태들의 집합 $\Sigma$ : 입력받은 String $q$ : 초기상태 ($q \in Q$) $F$ : AC를 받는 상태들의 집합 ($F \in Q$, 여러개 가능) $s$ : Transition Function 표기법은 책, 자료마다 다르지만 의미는 같다. 지난시간에 본 Problem X1을 DFA로 나타내면 다음과 같다. 여기에서 각 노드(..

지난시간은 집합을 배우고 이젠 또 이상한걸 배우네요. 암호는 언제 배우죠? 암호랑 상관이 없어보이는 내용이 이어지는 것 같다. 하지만 이 모든 것들이 암호의 본질에 대해 필요한 내용들이니 알아보도록 하자. Language 튜링머신(컴퓨터)이 해결하는 문제를 나타낸다. 용어부터 정의하고 가자. Symbol : 단순 문자 (0,1,a,b,c, ...) String : 길이가 유한한 Symbol의 배열 (01010, ababc, 00a1b, ...) $\lambda$ : 길이가 0인 String Alphabet : 길이가 유한한 Symbol 집합이고 $\Sigma$로 나타낸다. ({0,1}, {a,b,c, ..., z}) Language : String들의 집합 ({$\lambda$, 0, 1, 01, 10,..