[THEO] TIL 1

[THEO] TIL (1)

1. 기본 언어 연산과 속성

언어는 문자열의 집합이며, 집합 연산과 고유한 언어 연산을 가집니다.

클레이니 스타(*)와 클레이니 플러스(+)

두 연산은 문자열의 반복을 나타내지만, 공백 문자열(ε) 포함 여부에서 결정적인 차이가 있습니다.

• 클레이니 스타 (*): 0번 이상의 반복. 결과에 항상 공백 문자열(ε)이 포함됩니다.
  • 예: L = {a}일 때, L* = {ε, a, aa, aaa, ...}
• 클레이니 플러스 (+): 1번 이상의 반복.
  • 예: L = {a}일 때, L+ = {a, aa, aaa, ...}
• 중요한 예외: 둘의 관계식 L⁺ = L* \ {ε}는 원래 언어 L이 ε을 포함하지 않을 때만 성립합니다. 만약 ε ∈ L이라면 L⁺에도 ε이 포함되므로 위 관계는 성립하지 않습니다.

공백 문자열(ε)과 공집합 언어(∅)

‘비어있음’을 나타내는 두 개념은 역할이 완전히 다릅니다.

구분	공백 문자열 (ε)	공집합 언어 (∅)
정체	하나의 문자열 (원소)	하나의 언어 (집합)
비유	내용물 없는 상자	상자 자체가 없음
연결 연산	L ⋅ {ε} = L (항등원, 숫자 1 역할)	L ⋅ ∅ = ∅ (영원, 숫자 0 역할)

언어의 분배 법칙

언어의 연결(Concatenation) 연산은 다른 집합 연산과 결합될 때 다음과 같은 특징을 가집니다.

• 합집합(Union)에 대해 분배 법칙 성립 ✅
  • A(B ∪ C) = AB ∪ AC
• 교집합(Intersection)에 대해 분배 법칙 성립 안 함 ❌
  • A(B ∩ C) ≠ AB ∩ AC
• 언어의 크기(Cardinality)는 곱셈이 아님 ❌
  • |AB| ≠ |A| ⋅ |B| (연결 시 중복된 문자열이 발생할 수 있기 때문)

---

2. 문법과 정규 표현식

언어를 생성하는 규칙(문법)과 언어를 표현하는 패턴(정규 표현식)입니다.

정규 표현식 (Regular Expressions)

특정 패턴을 가진 문자열의 집합을 간결하게 표현하는 방법입니다. 문자열이 주어진 정규 표현식에 속하는지 판별하는 것은 중요한 문제입니다.

• 예시: 문자열 abba는 정규 표현식 L((a|b)*ab(a|b)*)에 속합니다. 이 표현식은 ‘ab’를 부분 문자열로 포함하는 모든 문자열을 의미하기 때문입니다.

문법의 종류 (Types of Grammars)

• 우측 선형 문법 (Right-Linear Grammar): 규칙이 A → aB 또는 A → a 형태로, 규칙 우변의 가장 오른쪽에 최대 하나의 변수만 허용합니다. 정규 언어를 생성합니다.
• 촘스키 정규형 (Chomsky Normal Form): 규칙이 A → BC 또는 A → a 형태로, 문맥 자유 언어를 위한 표준 형식입니다.

두 문법은 규칙의 형태가 다르므로, 우측 선형 문법은 촘스키 정규형이 아닙니다.

---

3. 유한 오토마타와 전이 함수

유한 오토마타(DFA)는 언어를 인식하는 추상 기계이며, 그 움직임은 전이 함수로 정의됩니다.

기본 전이 함수(δ) vs. 확장 전이 함수($\hat{\delta}$)

두 함수는 오토마타의 상태 변화를 기술하지만, 처리 단위가 다릅니다. 지하철 노선도에 비유하면 가장 이해하기 쉽습니다.

구분	기본 전이 함수 (δ)	확장 전이 함수 ($\hat{\delta}$)
비유	역무원 (한 정거장 안내)	여행 플래너 앱 (전체 경로 안내)
처리 단위	심볼 1개	문자열 전체
역할	δ(현재역, 노선하나) → 다음역	$\hat{\delta}$(출발역, 전체경로) → 최종역

두 함수의 공식 관계

확장 전이 함수($\hat{\delta}$)는 기본 전이 함수($\delta$)를 이용해 재귀적으로 정의됩니다.

1. 기초: $\hat{\delta}$(q, ε) = q (입력이 없으면 상태 변화 없음)
2. 재귀: $\hat{\delta}$(q, wa) = δ($\hat{\delta}$(q, w), a)
   • 의미: wa를 처리하려면, w를 먼저 처리한 중간 상태($\hat{\delta}$(q, w))에서 마지막 심볼 a를 δ를 통해 한 번 더 처리하면 된다.

수학적 귀납법을 이용한 증명 (Case Study)

• 문제: $\hat{\delta}$(q, uv) = $\hat{\delta}(\hat{\delta}(q, u), v)임을 증명하라.
  • 의미: “문자열 u 처리 후 v 처리” = “문자열 uv 한번에 처리”
• 증명 전략: 문자열 u의 길이에 대한 수학적 귀납법
  1. 귀납의 기초 (Base Case): |u|=0 (즉, u=ε)일 때 성립함을 보인다.
  2. 귀납 가정 (Inductive Hypothesis): |u|=n일 때 성립한다고 가정한다.
  3. 귀납 단계 (Inductive Step): |u|=n+1일 때도 성립함을 보인다. (이때 u를 wa 형태로 쪼개어 가정을 활용)
• 증명 중 핵심 원리: $\hat{\delta}$(q, awv) = $\hat{\delta}$(δ(q, a), wv)
  • 의미: “전체 경로(awv)를 따라가는 것”은 “a만큼 가서 도착한 새 위치에서 나머지 경로(wv)를 가는 것”과 같다. 이는 $\hat{\delta}$의 기본적인 작동 방식입니다.