형식 언어(Formal Language)는 알파벳 기호들로 구성된 문자열의 집합을 수학적으로 정의한 것이다. 촘스키 계층(Chomsky Hierarchy)으로 언어 클래스를 분류한다.
촘스키 계층
| 타입 | 언어 | 문법 | 오토마타 |
|---|
| 타입 0 | 귀납적 열거 언어 | 무제한 문법 | 튜링 기계 |
| 타입 1 | 문맥의존 언어 | 문맥의존 문법 | 선형 한정 오토마타 |
| 타입 2 | 문맥자유 언어 | 문맥자유 문법 | 푸시다운 오토마타 |
| 타입 3 | 정규 언어 | 정규 문법 | 유한 오토마타 |
정규 언어(Regular Language)
정규 표현식으로 표현 가능한 가장 단순한 언어 클래스.
정규 표현식 기본 연산:
- 연결(Concatenation): ab
- 합집합(Union): a|b
- 클리니 스타(Kleene Star): a*
- 플러스: a+ = aa*
예: 이메일 주소 패턴 (단순화)
[a-z]+ @ [a-z]+ . [a-z]+
문맥자유 언어(Context-Free Language)
프로그래밍 언어의 구문 분석에 사용된다.
BNF 문법 예 (산술식):
<expr> ::= <expr> '+' <term> | <term>
<term> ::= <term> '*' <factor> | <factor>
<factor> ::= '(' <expr> ')' | NUMBER
생성 규칙: S → aSb | ε → {aⁿbⁿ | n ≥ 0}
펌핑 보조 정리
언어가 특정 클래스에 속하지 않음을 증명하는 도구.
정규 언어 펌핑 보조 정리:
정규 언어 L에서 충분히 긴 문자열 w ∈ L에 대해
w = xyz 로 분해 가능, 여기서:
- |xy| ≤ p
- |y| ≥ 1
- 모든 k ≥ 0에 대해 xyᵏz ∈ L
반례로 {aⁿbⁿ}은 정규 언어가 아님을 증명 가능
언어 연산
- 합집합: L₁ ∪ L₂
- 교집합: L₁ ∩ L₂ (정규 언어는 닫혀있음, CFL은 아님)
- 연결: L₁L₂ = {uv | u ∈ L₁, v ∈ L₂}
- 보수: Σ* - L
- 클리니 스타: L* = {ε} ∪ L ∪ LL ∪ ...
관련 개념
