티스토리

머리가 개꾸리

검색하기

블로그 홈

머리가 개꾸리

swko.tistory.com/m

개꾸리 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

computation theory (9) - P, NP P는 deterministic Turing machine을 이용해서 polynomial time에 풀 수 있는 문제들의 집합이다.NP는 nondeterministic Turing machine을 이용해서 polynomial time에 풀 수 있는 문제들의 집합이다.또한 NP는 deterministic Turing machine으로 polynomial time에 주어진 답이 맞는지 확인(verify)할 수 있는 문제들의 집합이다. 공감수 0 댓글수 0 2018. 10. 9.
computation theory (8) -Turing machine Turing machine은 무한한 tape와 오른쪽/왼쪽으로 움직이며 tape를 읽고 쓰기가 가능한 head로 이루어진 계산 모델이다. Turing machine은 7-tuple로 다음과 같이 정의한다. Turing machine T = (Q, Σ, Γ, δ, q0, qaccept, qreject) Q 는 states의 집합Σ 는 ⌊⌋(blank symbol)을 포함하지 않는 input alphabet Γ 는 tape alphabet ( ⌊⌋ ∈ Γ and Σ ⊆ Γ )δ 는 Q x Γ -> Q x Γ x {R, L} 인 transition functionq0 는 start stateqaccept 는 accept stateqreject 는 reject state Turing machine이 recogn.. 공감수 0 댓글수 0 2018. 9. 15.
computation theory (7) - pumping lemma for CFL CFL을 위한 pumping lemma는 RL을 위한 pumping lemma와 유사하지만 약간 다른 점이 있다. Language A가 context-free lanugage라면 pumping length p가 있으면 p보다 긴 string s를 s=uvwxyz로 다음을 만족하도록 나눌 수 있다. 1. for each i >= 0, u(v^i)x(y^i)z 는 language A에 포함된다.2. |uv| > 03. |uxy| 0이 성립하며 |V| + 1의 높이를 가진 parse tree의 최대 children의 수는 b^(|V| + 1) = p이므로 |uxy| < p가 성립한다. //사지방 컴퓨터가 flash 안되는 컴퓨터여서 나중에 추가 모든 CFG는 pumping lemma를 만족한다. 공감수 0 댓글수 0 2018. 9. 1.
computation theory (6) - equivalence of CFG and PDA CFG와 PDA가 equivalence함을 보이기 위해서 CFL와 pushdown automata가 recognize하는 것이 필요충분조건임을 보이면 된다.Pushdown automata가 recognize하는 language는 context-free이다.Language가 context-free이면 pushdown automata가 recognize한다.//증명추가 공감수 0 댓글수 0 2018. 9. 1.
computation theory (5) - context-free grammar and pushdown automata context-free grammar(CFG)는 DFA나 RE보다 더 강력한 descriptive power를 가진 모델이다. CFG는 4-tuple로 정의한다. context-free grammar V : variables의 집합: terminals의 집합 R : rules의 집합 S : 인 start variable CFG로 들어지는 language를 context-free language라고 한다. Chomsky normal form은 CFG의 간단하고 유용한 form으로 모든 rule이 의 형태를 가진 CFG이다. 모든 CFG는 CNF으로 변환가능하다. Pushdown atomata(PDA)는 stack을 가진 finite automata이다. PDA는 CFG와 descriptive power면에.. 공감수 0 댓글수 0 2018. 8. 27.
computation theory (4) - pumping lemma for regular language pumping lemma는 langauge가 nonregular함을 보일 때 자주 이용하는 lemma이다. pumping lemma는 다음과 같다. 증명은 비둘기집 원리(pigeonhole principle)를 이용해 증명한다. 따라서 모든 regular language는 pumping lemma를 만족한다. 공감수 0 댓글수 0 2018. 8. 26.
computation theory (3) -regular expression Regular expression(RE)은 다음과 같이 정의한다. R is regular expression if R is Regular expression은 circular definition이라고 오해할 수 있지만 R은 R1, R2보다 항상 크기 때문에 귀납적으로 증명할 수 있다.Regular expression은 DFA와 language를 recognize하는 descriptive power가 같다. (RE를 DFA로 변환하는 것으로 증명한다.) 따라서 DFA, NFA, RE 모두 동일한 descriptive power를 가지고 있다. 공감수 0 댓글수 0 2018. 8. 26.
computation theory (2) - Equivalence of NFAs and DFAs 이전 포스팅에서 DFA와 NFA에 대해서 알아보았다. DFA와 NFA에 관한 재미있는 사실은 둘 모두 recognize하는 class of language는 equivalence하다는 점이다. 증명은 language A를 recognize하는 NFA N이 있을 때 같은 language를 recognize하는 DFA를 construct하는 것으로 증명할 수 있다. 일 때 DFA 을 construct하면 으로 construct 할 수 있다. 따라서 DFA와 NFA와 regular language가 recognize하는 class of languages는 동일하다는 것을 알 수 있다. 공감수 0 댓글수 0 2018. 8. 26.
computation theory (1) -DFA, NFA Finite Automaton은 states와 input을 이용해 계산을 수행하며 극도로 제한된 메모리를 가진 컴퓨터가 사용하기에 좋은 수학모델이다. Finite Automaton은 다음과 같이 5-tuple로 정의한다. finite automaton M = (Q, Σ, δ, q0, F) Q : states의 집합Σ : alphabets의 집합δ : Q X Σ -> Q인 transition functionq0 : start stateF : accept states의 집합 하나의 finite automaton은 one language만을 accept(recognize)할 수 있으며 finite automaton이 recognize하는 language를 regular language라고 정의한다.Finite.. 공감수 0 댓글수 0 2018. 8. 25.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.