[암호학] DFA

아직 '암호' 의 기본기를 다루는 내용이다.

• Symbol : 단순 문자 (0,1,a,b,c, ...)
• String : 길이가 유한한 Symbol의 배열 (01010, ababc, 00a1b, ...)
• λλ : 길이가 0인 String
• Alphabet : 길이가 유한한 Symbol 집합이고 ΣΣ로 나타낸다. ({0,1}, {a,b,c, ..., z})
• Language : String들의 집합 ({λλ, 0, 1, 01, 10, ...})
• Problem : 어떤 조건을 만족하는 Language

problem = language 이다. 

problem(language)에 들어있는 원소 x는 그 problem의 정답이다. 

problem x1: 입력은 짝수인가?
L1 = {00,10,010, 100, 110 …}
problem x2: 입력은 0으로 끝나는가?
L2 = {00,10,010, 100, 110 …}
L1 = L2

두 문제가 같으려면 두 문제의 정답집합이 같아야 한다.

---

Alphabet(Σ)은 길이가 유한한 Symbol 집합 ->  Alphabet 집합의 크기는 |Σ| (유한한 Symbol 집합의 크기이니 finite set)로 표현

String은 위의 Alphabet의 원소들을 유한개 나열하여 나타낼 수 있는 문자열의 집합이고 Σ^∗로 나타낸다.

그렇다면 String의 크기는 |Σ^∗| (alphabet 원소들을 자연수에 대응가능한countable set 무한집합으로 나타낼 수 있음)로 나타남

Language(Problem)은 String의 부분집합이므로 |2^|Σ^∗||가 된다.

집합론에서 배웠듯이 countable의 power set이 되므로 language는 uncountable 무한집합이다.

---

DFA (deterministic finite automata)

DFA 는 다음으로 이루어져있다.

M=(Q,Σ,q,F,s)

• Q : DFA상태들의 집합
• Σ : 입력받은 String
• q : 초기상태 (q∈Q)
• F : AC를 받는 상태들의 집합 (F∈Q, 여러개 가능)
• s : Transition Function

0으로 끝나는가

101을 포함하는가

위 문제는 DFA 로 못품(i 값이 무한히 커지면 상태의 수도 같이 무한히 커짐)

연습문제
Problem X4 : L4={x|x=0i1j,0≤i,j}L4={x|x=0i1j,0≤i,j}, 여기서 a2=aaa2=aa이다.
Problem X4를 AC하는 DFA는 존재하는가?
존재한다면 그 DFA를 그려보자!

L5의 이유:

아래거 다시 이해!

https://riroan.tistory.com/101

[암호학] 8. Pumping Lemma, Pigeonhole Principle

 

DFA  M 이 적어도 n개 길이의 문자열을 accept 한다면,  n+1개의 상태를 가져야해서 pigeonhole 원리에 의해 모순이다.