본문 바로가기

학교 공부/계산이론7

Introduction to Theory of Computation 2장_9 정리/설명 우리가 앞 전 시간에 Regular Language는 Union Operation, Computination Operation, Star Operation에 대해서 폐쇄성을 지닌다고 이야기했다. 그리고 그것들은 NFA와 DFA로 표현되고 또한 정규표현식으로도 표현할 수 있었다. 그러면 모든 Language들은 Regular Language일까? 정답은 "아니다". 따라서 이번 시간에는 Pumping Lemma 이론으로 Regular Language가 아님을 증명하는 시간을 가질 것이다. (Pumping Lemma) : Regular Language의 일반적인 성질을 기술한 이론이다. -> Regular language의 필요조건을 담고 있음. >> 비둘기 집의 원리를 이용 & state의 개수보다 긴 s.. 2019. 10. 11.
Introduction to Theory of Computation 2장_7,8 정리/설명 Introduction to Theory of Computation 2장_7,8 정리/설명 **정규식은 패턴을 의미하는 것. (0∪1) 01* : 첫 글자는 0 또는 1이 나와야 하며, 두 번째 글자는 0, 그 이후로는 1이 0번 이상 연속되는 string을 의미한다. - 피연산자 : 0, 1 - symbols - 연산자 : ∪(또는), *, 각각에 붙어 있는 글자들의 concatenation 연산 (ex) 00, 10, 001, 101, 001111 etc. Q. The language {w : w contains exactly two 0s} is described by the expression. A. 1*01*01* >> 0이 정확히 두 개만 존재해야 하기 때문에 두 개의 0의 맨 앞/중간/맨 뒤에.. 2019. 10. 10.
Introduction to Theory of Computation 2장_6 정리/설명 Introduction to Theory of Computation 2장_6 정리/설명 - Retular Operation의 폐쇄성 - Theorem 2.6.1 Union 연산에 대한 폐쇄성 같은 알파벳 ∑에 대한 A1과 A2가 regular language라면 A1∪A2도 regular language이다. (설명) 위쪽의 네모 박스를 M1, 아래쪽의 네모 박스를 M2라고 두고, 각각의 M1, M2가 합집합 연산을 하기 위해서는 q0라는 start state에서 ε을 입력받아서 M1, M2 양쪽으로 갈 수 있는 NFA M을 만든다. (※ ε 심벌을 통해서 입력값에 영향을 받지 않도록 한다.) Theorem 2.6.2 Concatenation 연산에 대한 폐쇄성 같은 알파벳 ∑에 대한 A1과 A2가 re.. 2019. 10. 10.
Introduction to Theory of Computation 2장_4,5 용어/개념정리 Introduction to Theory of Computation 2장_4,5 용어/개념 정리 : Nondeterministic Finite Automata. 여태 보았던 DFA Diagram과 다른 점 세 가지가 있을 것이다. 1. q₁으로 가는 옵션이 0과 1 두 가지가 있다. 2. q₂에서 q₃로 가는 symbol 중에서 λ(empty string)가 보인다. 3. q₃에서 symbol 0을 읽지 못한다. (※ λ란? empty string, 길이가 0인 문자열 // 공집합과는 다름. ) 위의 State Digram에서 010110을 Input 한 다음의 트리 구조를 봐보자. **이제부터 q₁, q₂, q₃, q₄를 1,2,3,4로 쉽게 나타낼 것임. >> accept string은 '11', '.. 2019. 9. 29.
Introduction to Theory of Computation 2장_1,2,3 용어/개념정리 Introduction to Theory of Computation 2장_1,2,3 용어/개념정리 Chapter 2. Finite Automata and Regular Languages p.30 자판기 오토마타 설명 p.31 q₁ : start state q₂ : accept state (ex) 1101은 accept 된다. / 000110은 reject 된다. >> w : 1로 끝나는 스트링은 accept 된다. / 0이 짝수개가 나오는 스트링은 accept 된다. : Deterministic Finite Automata (정의) A dif is a 5-tuple M = (Q, ∑, δ, q, F) //원소가 5개인 순서쌍 - Q : set of states / 유한 상태의 집합 - ∑ : alphab.. 2019. 9. 29.
Introduction to Theory of Computation 1장_2 문제풀이 문제 1.1 Use induction to prove that every integer n≥2 can be written as a product of prime numbers. - 해석 : n≥2인 모든 정수는 소수의 곱으로 이루어져 있음을 증명하라. - 증명 : 2≤n≤k 에서 자연수 k가 소수들의 곱으로 표현되어 있다고 가정한다. ⅰ) n이 소수이면, 2 ≤ n(소수) * 1 ≤ k 이므로 증명이 종료된다. ⅱ) n이 소수가 아니라면, n 역시 1을 제외한 약수 중에서 가장 작은 약수를 소수로 갖게 될 것이다. n=n₁ x p₁ x p₂ 처럼 n이 소수만 남을 때까지 이 과정이 반복되기에 ∴ 따라서 n≥2인 모든 정수는 소수의 곱으로 이루어져있다. 문제 1.2 For every prime number.. 2019. 9. 14.

티스토리툴바