Alphabet, String

○Alphabet (Σ)

 ◎Σ = {0,1} /  Σ={a,b,c,d,e}

 ▷하나 이상의 Symbol들의 집합

 ▷Alphabet 내의 Symbol의 조합으로 만들어지는 symbol은 속할 수 없다. ( a,b가 있을때 ab는 있을 수 없음)

 

 ▶Powers of Σ

  ▷alphabet Σ와 1 이상의 자연수 n에 대해

  ▷Σ¹ = Σ

  ▷Σⁿ⁺¹ ={ xy | x ∈ Σ, y ∈ Σⁿ }

 

 ▶Cardinal Number of Σ

  ▷|Σⁿ| = |Σ|ⁿ

  ▷|Σ|: alphabet의 원소 개수

 

 

○String

 ▷Σ가 알파벳이라면, 

 ▷Σ⁺ 또는 Σ^*을 String이라고 한다.

 ▷ = word, sentence

 

 ▶Empty String (Σ⁰)

  ▷아무것도 들어있지 않은 String (Σ⁰ = {λ})

  ▷λ ≠ Σ, λ ≠ Φ(공집합), λ ≠ β(blank)

 

 ▶Length (||s||)

  ▷Σ+의 원소 w = x₁x₂...x_n일때 (xⁱ ∈ Σ, 1≤i≤n)

  ▷w의 Length (||w||): n

  ▷||λ|| = 0

 

 ▶Concatenation (연결)

  ▷x,y ∈ Σ⁺이고, x,y의 원소들 ∈ Σ 일 때 (x = x₁x₂...x_m, y = y₁y₂...y_n)

  ▷xy = x₁x₂...x_my₁y₂...y_n

  ▷||xy|| = ||x|| + ||y|| = m + n

 

 ▶Powers of String

  ▷x ∈ Σ⁺, x의 원소들 ∈ Σ, n ∈ N일 때

  ▷xⁱ = λ

  ▷x¹ = x

  ▷xⁿ⁺¹ = xxⁿ

 

 ▶Prefix, Suffix

  ▶문자열 w를 xy 두 개의 부분으로 나뉘었을때 (x, y ∈ ∑^*)

   ▷x: prefix, y: suffix

 

  ▷Prefix: 문자열의 앞부분

   ▷Proper prefix: x ≠ w인 prefix

  ▷Suffix: 문자열의 뒷부분

   ▷Proper suffix: y ≠ w인 suffix

 

 ▶Substring

  ▶문자열 w를 xyz 세 개의 부분으로 나뉘었을때 (x, y, z ∈ ∑^*)

   ▷y: Substring

 

  ▷Substring: 문자열의 일부

   ▷Proper substring: y ≠ w인 substring

 

 

○Language

 ▷Σ가 alphabet이라면, 

 ▷Σ^*의 subset을 language라고 한다.

 

 ▷Empty language (∅)를 포함한다.

 

 ▶Concatenation (연결)

  ▷A, B가 Language일때

  ▷AB = { ab | a ∈ A, b ∈ B }

 

 ▶연산 법칙

  ▷Identity - Concatenation

  ▷Associative - Concatenation

  ▷Distribution - 합집합, 곱집합

   ▷곱집합은 = 가아닌 ⊆임에 주의

 ▶Kleene Closure

  ▷Language A ( ⊆ Σ^* )에 대해서, 이를 이용해 다른 Language를 정의 가능하다.

 

  ▷A⁰ = {λ}, A¹ = A

  ▷Aⁿ⁺¹ = { ab | a∈A, b∈Aⁿ } (n∈Z⁺)

  ▷A⁺ = ∪_n∈Z⁺ Aⁿ -> positive closure

  ▷A^* = A⁺ ∪ A⁰ = A⁺ ∪ {λ} -> kleene closure

  

  ▶활용

 

 ▶Theorem