Introduction to Theory of Computation 2장_7,8 정리/설명

Introduction to Theory of Computation 2장_7,8 정리/설명

<Regular Expression>
  **정규식은 패턴을 의미하는 것.

 (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의 맨 앞/중간/맨 뒤에는 1만 나와야 하며, 1이 몇 번 나와도 상관없으므로 1*으로 표현한다.

Q. The language {w : w contains at least two 0s } is described by the expression.
A. (0∪1)*0(0∪1)*0(0∪1)* 
   >> 0이 최소 2개 존재해야 하므로 두 개의 0의 맨 앞/중간/맨뒤에는 0 또는 1이 몇 번 나와도 상관없으므로 (0∪1)* 을 써준다.

Q. The language {w : 1011 is a substring of w} is described by the expression.
A. (0∪1)*1011(0∪1)* 
   >> 1011이라는 서브 스트링이 들어가기만 하면 되므로 1011 앞/뒤에는 (0∪1)*를 써준다.

Q. The language {w : the length of w is even} is described by the expression.
A. ((0∪1)(0∪1))* 
   >> string의 길이가 짝수이어야 하므로 두 개의 심벌을 묶어 star operation을 해주면 되는데 각각의 심벌은 (0∪1)로 표현할 수 있다.

Q. The language {w : the length of w is odd} is described by the expression.
A. ((0∪1)(0∪1)(0∪1))*
   >> 위의 짝수 설명과 동일(두 개의 심벌->세개의 심벌)


Definition 2.7.1
 1. ε is a R.E.               
 2. ∮ is a R.E.
 3. a ∈ ∑, a is a R.E.                  //1,2,3번 피연산자
 4. If R₁ and R₂ are REs, R₁∪R₂ is a R.E.
 5. If R₁ and R₂ are REs, R₁R₂ is a R.E.
 6. If R is a R.E, R* is R.E.              //4,5,6번 연산자

Definition 2.7.2
  // L(R) : the language described by a R.E.
 1. L(ε) : {ε}
 2. L(∮) : ∮
 3. L(a) : {a} for a ∈ ∑.   //피연산자 하나만 쓴 경우이며, 길이가 1이다.
 4. If R=R₁∪R₂, L(R) = L(R₁∪R₂) = L(R₁)∪L(R₂)
 5. If R=R₁R₂, L(R) = L(R₁R₂) = L(R₁)L(R₂)
 6. If R=R₁*, L(R) = L(R*) = (L(R))*


   >>예시. (0∪1)01* 의 string들의 의미를 알아보자
                = L(0∪1)L(01*)
                = (L(0)∪L(1))L(01*)
                = ({0}∪{1})L(0)L(1*)
                = {0, 1}({0}(L(1)*))
                = {0, 1}({0}{1}* )
                = {0, 1}{01, 011, 0111, 01111 ... }



 Theorem 2.8.1.
A language L is regular if and only if there exists a regular expression that describes L.
 >> L을 표현할 수 있는 정규 표현이 존재한다면, L은 정규 언어이다.

 ** if and only if : 필요 충분 조건

(proof) 귀납법, Every R.E describes a regular language.
 - base case
      1) If R = ε, then L(ε) = {ε}   
      2) If R = ∮, then L(∮) = ∮
      3) If R = {a}, then L(a) = {a}

 - Induction 
  : Let n be the number of operator in R. Assume that if n≥k for k≥0, "Every R.E describes a regular language" is true. Consider the case of n = k+1 ≥ 1.

    4) R=R₁∪R₂ 은 Thm 2.6.1에 의해 Regular Language. -> L(R) = L(R₁)∪L(R₂)
    5) R=R₁R₂ 은 Thm 2.6.2에 의해 Regular Language. ->  L(R) = L(R₁)L(R₂)
    6) R=R₁* 은 Thm 2.6.3에 의해 Regular Language -> L(R) = L(R*) = (L(R))*

 

L((0∪1)01*) 알고리즘
 L(0∪1)01*) = L(0∪1)L(01*) = (L(0)∪L(1))L(01*) = (L(0)∪L(1))L(0)L(1*)