수학정리(Complexity Theory)

계산복잡도 수업 내용 정리

*Def

-FA(finite automata): FA are finite collections of states(Q) with transition rules that take you from one state to another.

-apb(alphabet):apb is any finite set of symbols

-str over apb:apb에 속한 원소들의 lists(juxtapositions)

-apb^*, the set of all strs over apb with empty string eps

-eps:empty string

-L(over apb)(language):a subset of apb^*

-DFA(deterministic finite automata): FA(5, Q,Σ,δ,q0,F)

with input apb(Σ), start states(q0), final states(F⊆Q), 이때 transition function δ은 domain이 (state, symbol), extend하면 (state, string)까지도 됨

-L(A):the set of all strs s.t. δ(q0,str) is in final states for some DFA A

-L is regular if L=L(A) for some DFA A.

-NFA(Nondeterministic finite automata):FA(5, Q,Σ,δ,q0,F) with δ(q,a) is a set of states

특히 NFA에서는 a string w is accepted if δ(q0,w) contains at least one final state.

-TM(Turing machine):(7, Q,Σ,Γ,δ,q0,Β,F), Γ:tape apb set(읽고 쓰기가 가능, 쓸대는 Σ에 없는 것도 사용 가능, Σ<Γ)

(input의 양옆에는 blank로 채워서 들어가는 infinite tape)

(δ(state,tape symbol)=(변경 후 state, 변경 후 tape symbol, head이동방향))

(algorithm이 없는 language를 보이기 위해서 TM다룸, C program보다 simple하면서도 powerful함)

-ㅏ:TM에 input 한개 계산

-ㅏ*:TM에 input 모두 계산

-L(TM):the set of all strs w s.t. q0wㅏ* in final

-L=L(TM)이면 L을 recursively enumerable languages라 한다.

-Algorithm:=TM s.t. 어느 input이어도 halt할지 안할지 guaranteed된 TM을 가리킨다.

-L=L(TM) with algorithm TM이면 L을 recursive language라 한다.

-CFG(Context-free grammar): CFG(4, V,Σ,R,S)

with V:variables, Σ:terminals, R:rules(variable넣으면 variable과 terminal의 조합으로 이루어진 string이 output인 rule), S(in V):start variable

-L(CFG):the set of all strs w s.t. Sㅏ*w(즉 start variable S로부터 시작해서 나올 수 잇는 모든 strings with only terminals)

*Thm

the reverse of a regular language is also regular

Equivalence of DFA and NFA using subset construction

(NFA, DFA모두 the same language를 갖게 만들 수 있고, NFA가 state개수가 exponentially 적게 가능하지만, 구현가능 한 것은 DFA뿐)

가능한 L over {0,1}의 개수는 uncountable(임의의 language는 infinitely binary seq로 만들 수 있고, infinitely binary seq의 개수는 uncountable이므로)

Language가 program보다 많다는 것을 가리킴, 즉 There are languages with no membership algorithm(w in L인지 아닌지 판단하는 것을 membership algorithm), 이러한 류의 증명 방식을 Hungarian Arguments라 한다. 가능한 총 개수가 더 많음을 보여서 무언가 존재하는지 안존재하는 지 보이는 방식을(존재성은 알지만 particular language를 제시하는 데에 어려움(with no membership algorithm인 language를 건설하기 어렵다)

DFA->TM(DFA꺼 그대로 하고 방향도 R만 쓰고 tape write안하면 됨)

모든 Data type은 integer로 변환 가능

Binary strings to Integer는 Binary sting마다 앞에 1 붙여서 순서매기면 된다. 101->1101 =  13번쨰 integer, 0101->10101 = 21번째 integer

GIF는 ASCII string으로 구성, ASCII string을 binary string으로 바꾸고 integer로 바꾸면 됨, 따라서 i번째 image라는 걸 생각 가능

*Example

(Non-regular language)

L={0^n1^n|n>=1}, a^i means a가 i개 병렬나열

L={0^n1^n|n>=1}={01,0011,000111,...}, finite state을 가지는 DFA로는 얻을 수 없다. 따라서 non-regular

TM으로는 가능

L={01*0}={00,010,0110,...}을 TM으로 묘사하기

 

(Mortality of matrices)S:given finitely generated submonoid of nxn matrices from MT(nxn)(Z)

Determine whether there exists a seq of matrices M1,M2,...,Mk in S s.t. M1M2...Mk = 0(link1)(link2)(link3)(link4)

===========================================================

CFG이후의 내용 쭉 읽어서 PDA까지도 이해하기

수업내용 이해하기

undeciable관련해서 이해하기