✅ 무엇을 학습해야 할까?
🎯 학습 목표 요약
- 언어(Language)를 수학적으로 정의하고 다루는 기본 단위들을 이해
- 문자열, 길이, 공백 문자열, 클로저 연산 등의 형식적 정의 익히기
- 언어를 어떻게 표현할 것인가? 라는 질문에서 문법(Grammar)과 인식기(Recognizer)의 개념 도입
🔎 어떤 걸 중점적으로 공부해야 할까?
| 개념 |
중점 학습 포인트 |
| 알파벳 (Alphabet) |
기호의 유한 집합, 실생활 예시와 비교 |
| 문자열 (String) |
기호들의 순서 있는 열, 공백 문자열 포함 |
| 문자열의 길이 |
` |
| ε (epsilon) |
공백 문자열로서의 의미, 클로저와 관련됨 |
| T*, T⁺ |
클로저 연산의 의미와 차이점 |
| 언어 |
T*의 부분집합으로서 정의됨 |
| 문법 & 인식기 |
언어의 표현 방식, 생성/인식 관점 도입 |
| 유한 표현 가능성 |
모든 언어가 표현 가능한 건 아님. 불가능한 경우도 존재 |
언어의 기본 정의
1. Alphabet (알파벳)
- 정의: 유한한 기호들의 집합
- 예시:
- T₁ = { ㄱ, ㄴ, ㄷ, … }
- T₂ = { A, B, C, … Z }
- T₃ = { auto, break, case, … }
2. String (문자열, sentence, word)
- 알파벳으로부터 만들어진 기호들의 순서 있는 나열
- 예:
abc, while, 00
3. Length (문자열의 길이)
- 문자열에 포함된 기호 개수
- 표기:
|ω|
예: |abc| = 3
공백 문자열과 언어의 수학적 정의
4. Empty String (공백 문자열, ε 또는 λ)
- 아무 기호도 포함하지 않는 문자열 (길이 0)
- 예:
"" (빈 문자열)
5. T* 와 T⁺
- T*: 알파벳 T에서 만들어지는 모든 문자열의 집합 (공백 문자열 포함)
- T⁺: T* - {ε} → 공백 문자열 제외
- T*는 T-star, T⁺는 T-dagger라고도 부른다
6. Language (언어)
- T*의 부분집합
→ L ⊆ T*
즉, 언어는 특정 조건을 만족하는 문자열들의 집합
언어를 어떻게 표현할 것인가?
📌 문제 1: 언어를 어떻게 표현할까?
- 유한 언어: 직접 나열 가능 (간단)
- 무한 언어: 유한한 방식으로 표현 필요
대표 표현 방식
- Set Description: 집합 규칙으로 표현
- Grammar (문법): 생성 방식 (Generating Scheme)
- Recognizer (인식기): 인식 규칙 (Recognition Scheme)
📌 문제 2: 모든 언어를 표현할 수 있을까?
- NO!
- 모든 언어가 유한한 방식으로 표현 가능한 건 아님
✍️ 핵심 정리 문장
- 언어는 알파벳 T로부터 만들어진 문자열들의 집합이다.
- 문자열은 기호의 나열이며, 그 길이는
|ω|로 표현한다.
- 공백 문자열(ε)은 길이가 0인 문자열이며, 모든 문자열 집합(T*)에 포함된다.
- 언어는
L ⊆ T*로 표현되며, 규칙적으로 생성하거나 인식 가능한 경우가 중요하다.
- 문법(Grammar)과 인식기(Recognizer)는 언어를 정의하거나 처리하기 위한 두 가지 방식이다.
📚 예습/복습 팁
- 문자열 집합
T*, T⁺의 개념을 시각적으로 연습해보기
예: T = {a, b}일 때,
- T* = {ε, a, b, aa, ab, ba, bb, aaa, …}
- T⁺ = {a, b, aa, ab, …} (ε 없음)
ε와 λ는 같은 의미 → 시험에서 표기만 다를 수 있음 주의- “모든 언어가 유한하게 표현 가능하지 않다”는 점은 언어 계층 분류(Chomsky 계층)로 연결됨
✅ 이번에 학습해야 할 내용
📌 학습 목표
- 문자열과 언어의 기본 연산(결합, 반복, 역순)을 정확히 이해하기
- 언어 간의 곱셈, 멱집합, 클로저 연산(T⁺, T*) 개념 익히기
- 표현 형식과 수학적 기호에 익숙해지기
🔎 중점적으로 공부해야 할 포인트
| 주제 |
학습 포인트 |
| 문자열 연결(Concatenation) |
두 문자열을 하나로 붙이는 방식과 성질 |
| 문자열 반복 표현 |
aⁿ의 의미와 a⁰ = ε 개념 |
| 문자열 반전 |
역순(reversal)의 개념과 표기법 |
| 언어 곱(Language Product) |
두 언어의 문자열 조합으로 새로운 언어 생성 |
| 언어의 거듭제곱 |
L⁰ = {ε}, Lⁿ = L · Lⁿ⁻¹의 재귀 정의 |
| 클로저 연산 T⁺, T* |
반복 가능한 문자열 집합의 정의, 포함/제외 관계 구분 |
📚 학습자 중심 정리
문자열(String)의 연산 정의
1. Concatenation (문자열 결합)
- 문자열
u, v를 붙여 하나의 문자열 uv로 만든다.
- 예: u =
abc, v = de → uv = abcde
- 수학적 성질:
- uε = εu = u (ε는 결합에 영향 없음)
- u, v ∈ T* → uv ∈ T*
- |uv| = |u| + |v|
2. aⁿ: n개의 a
aⁿ은 a를 n번 반복한 문자열
- a⁰ = ε (공백 문자열)
3. Reversal (역순)
- 문자열을 뒤집은 결과
- ω =
abc → ωᴿ = cba
- 속성: (ωᴿ)ᴿ = ω
언어(Language)의 연산 정의
4. Language Product (곱)
- L, L' 두 언어가 있을 때
L·L' = {xy | x ∈ L, y ∈ L'}
- 예: L = {a, b}, L' = {x, y}
→ L·L' = {ax, ay, bx, by}
5. 언어의 거듭제곱
- L⁰ = {ε}
- Lⁿ = L · Lⁿ⁻¹ (n ≥ 1)
- 예: L = {a}
→ L¹ = {a}, L² = {aa}, L³ = {aaa}
6. L* (Reflexive Transitive Closure)
- L을 0번 이상 반복한 문자열 집합
- 정의: L* = L⁰ ∪ L¹ ∪ L² ∪ …
= ⋃ Lⁱ (i = 0 to ∞)
7. L⁺ (Transitive Closure)
- L을 1번 이상 반복한 문자열 집합
- 정의: L⁺ = L¹ ∪ L² ∪ … = L* - L⁰
✅ 핵심 정리
| 연산 |
의미 |
포함 여부 |
| L* |
0회 이상 반복 |
ε 포함 |
| L⁺ |
1회 이상 반복 |
ε 제외 |
| Lⁿ |
n회 반복 |
L⁰ = {ε} |
| Reversal |
문자열 역순 |
(ωᴿ)ᴿ = ω |
| Concatenation |
문자열 연결 |
|
✍️ 복습 팁
- 다음과 같은 연습으로 개념을 확실히 해두자:
- T = {a, b}일 때
- T* = {ε, a, b, aa, ab, ba, bb, aaa, …}
- T⁺ = T* - {ε}
- L = {a}, L² = {aa}, L³ = {aaa}, …
- ω =
abc → ωᴿ = cba
- 반복 연산과 클로저는 정규 표현식, DFA, PDA 정의에 자주 등장하므로 반드시 숙지해야 함!
✅ 이번에 학습해야 할 내용
📌 학습 목표
- 문법(Grammar)의 구성 요소와 역할 이해하기
- terminal / nonterminal 기호의 차이 이해
- 생성 규칙을 통해 문자열을 유도(derivation) 하는 방식 습득
- 문법 예제를 통해 형식 언어 표현 방법 연습하기
🔎 중점적으로 공부할 포인트
| 주제 |
학습 포인트 |
| 언어와 문법 |
문장을 생성하는 규칙의 집합으로서 문법 이해 |
| terminal / nonterminal |
각각의 의미와 표기법 구분 (알파벳 vs 중간 단계 기호) |
| 문법의 구성 G = (VN, VT, P, S) |
각 구성 요소의 정의와 역할 |
| 생성 규칙 P |
α → β 형식, 여러 규칙은 ` |
| 유도 예시 |
S ⇒ aAS ⇒ aSbA ⇒ … 식으로 유도 트리를 만들 수 있어야 함 |
📚 학습자 친화 정리
Language & Grammar
- Language
- 문장(문자열)들의 집합
- 우리가 다루는 언어는 컴퓨터가 인식하거나 생성할 수 있어야 함
- Grammar
- 언어를 생성하는 규칙의 집합
- terminal symbol (종결 기호): 실제 언어를 구성하는 기호 (예:
a, b)
- nonterminal symbol (중간 기호): 문장을 생성하는 도중에 사용되는 기호 (예:
S, A)
- grammar symbol V: terminal과 nonterminal의 전체 집합
문법의 형식 정의
문법 G는 다음 4가지로 구성:
G = (VN, VT, P, S)
| 구성 요소 |
의미 |
| VN |
Nonterminal 기호 집합 |
| VT |
Terminal 기호 집합 |
| P |
생성 규칙 집합 (production rules) |
| S |
시작 기호 (start symbol) |
- P의 형식: α → β
- α ∈ V⁺ (한 개 이상의 기호가 있어야 함)
- β ∈ V* (없을 수도 있음, 즉 ε 가능)
문법 예시
문법 G = ( {S, A}, {a, b}, P, S )
생성 규칙 P:
S → aAS | a
A → SbA | ba | SS
- 비단말 기호(nonterminal): S, A
- 단말 기호(terminal): a, b
- 시작 기호(start symbol): S
- 유도 예시:
- S ⇒ aAS ⇒ aSbAS ⇒ aabAS ⇒ …
- 축약 표기법:
- S → aAS | a
- A → SbA | ba | SS
→ 여러 규칙을 | 기호로 간단히 표현 가능
✍️ 핵심 요약 정리
| 개념 |
설명 |
| 문법 G |
문자열을 생성하는 규칙 시스템 |
| terminal 기호 |
실제 언어 기호 (출력에 나타나는 기호) |
| nonterminal 기호 |
생성 도중 사용하는 중간 단계 기호 |
| 생성 규칙 P |
α → β의 형식으로, 문자열을 유도하는 변환 |
| S (시작 기호) |
유도가 시작되는 출발점 |
| V⁺, V* |
V⁺는 길이 1 이상, V*는 ε 포함 가능 |
💡 참고 개념
🔸 α ∈ V⁺: 길이 1 이상의 문자열, 반드시 하나 이상의 기호 포함
🔸 β ∈ V*: ε 포함 가능 → 우변은 빈 문자열도 가능
🔸 문법은 언어 생성의 설계도이며, 생성 규칙은 유도 단계의 명세서
✅ 복습용 문장
- 문법은 언어를 생성하는 규칙의 모음이며, G = (VN, VT, P, S)의 4요소로 구성된다.
- terminal은 실제 기호이고, nonterminal은 중간 생성 기호이다.
- 생성 규칙은 α → β의 형식으로 구성되며, 여러 규칙은
|로 묶어 축약할 수 있다.
- 시작 기호 S에서 유도 규칙을 반복 적용해 문자열을 생성할 수 있다.
✅ 이번에 학습해야 할 내용
📌 학습 목표
- 유도(derivation)의 개념과 기호 사용법 이해
- 유도 기호(
⇒, ⇒*, ⇒+)의 의미 구분
- 문법으로부터 언어가 생성되는 과정을 단계별로 따라가기
- 문법 G가 생성하는 언어 L(G)의 정의를 이해하기
🔎 중점적으로 공부할 포인트
| 개념 |
학습 포인트 |
⇒ |
직접 유도: 한 번의 생성 규칙만 적용 |
⇒* |
0회 이상 유도: 생성 과정 전체 |
⇒+ |
1회 이상 유도 |
| L(G)의 정의 |
시작 기호 S에서 생성 규칙을 통해 유도된 모든 문자열의 집합 |
| sentence vs sentential form |
전자는 terminal만 포함, 후자는 중간 과정 문자열도 포함 |
| 유도 예제 |
실제 유도 과정을 따라가며 규칙 적용 순서를 익히기 |
📚 학습자 친화 정리
Derivation (유도)
1. 유도 기호의 정의
| 기호 |
의미 |
설명 |
⇒ |
directly derives |
단일 생성 규칙으로 바로 유도 가능 |
⇒* |
derives in 0 or more steps |
0회 이상 반복 유도 가능 (최종 결과 포함) |
⇒+ |
derives in 1 or more steps |
1회 이상 유도해야 함 (직접 유도 포함) |
- 예:
- S ⇒ aA (직접 유도)
- S ⇒* abba (여러 번의 유도 포함)
- S ⇒+ ε, aabb (단, S ≠ ε면 1회 이상 유도)
- ✔ 해당: S ⇒* S
- ❌ 해당 아님: S ⇒+ S
🔹 cf.
→는 생성 규칙 자체를 표현할 때 사용 (정의)⇒는 유도(변환) 과정에서 사용 (실행)
언어 L(G)의 정의 및 유도 예시
L(G): 문법 G가 생성하는 언어
L(G) = { ω ∈ VT* | S ⇒* ω }
- S에서 유도 규칙을 통해 terminal 기호만으로 구성된 문자열 ω를 생성한 경우, ω는 L(G)에 속한다.
문장의 종류
| 용어 |
정의 |
| sentential form |
유도 중간 단계에서 나타나는 문자열 (terminal + nonterminal 혼합 가능) |
| sentence (문장) |
최종적으로 생성된 문자열, terminal 기호만 포함 (즉, 완성된 결과) |
예시 분석 (S ⇒* abba)
문법:
S → aA | bB | ε
A → bS
B → aS
유도 과정:
S ⇒ aA (S → aA)
⇒ abS (A → bS)
⇒ abbB (S → bB)
⇒ abbaS (B → aS)
⇒ abba (S → ε)
- 결과적으로
abba는 S에서 유도된 terminal-only 문자열이므로
→ abba ∈ L(G)
✍️ 핵심 요약 정리
| 구분 |
정의 |
| 유도(⇒) |
생성 규칙 한 번 적용 |
| 유도(⇒*) |
여러 단계 유도 전체 |
| L(G) |
시작 기호 S에서 유도된 모든 terminal-only 문자열 집합 |
| sentence |
terminal 기호로만 구성된 완성된 문자열 |
| sentential form |
유도 중간 단계의 문자열 (nonterminal 포함 가능) |
💡 참고 개념 요약
S ⇒* ω이고 ω ∈ VT* → ω는 G가 생성한 문장(sentence)S ⇒* ω이고 ω ∈ V* → ω는 sentential form
✅ 실전 학습 팁
- 다음 문법이 주어졌을 때 어떤 문자열이 L(G)에 속하는지 직접 유도해보는 연습 필수!
- 좌변이 동일한 여러 생성 규칙을
|로 표현하는 표기법에 익숙해질 것.
- 비단말 기호가 모두 사라질 때까지 유도하는 것이 중요!
✅ 이번에 학습해야 할 내용
📌 학습 목표
- 문법을 구성하는 생성 규칙(P)을 활용해 특정한 패턴의 언어를 설계하는 방법을 이해
- 주어진 문법이 어떤 언어를 생성하는지 정확히 분석하는 능력 기르기
- 복잡한 문자열(예: aⁿbⁿcⁿ)을 단계별 유도로 생성해보기
🔎 중점적으로 공부할 포인트
| 주제 |
학습 포인트 |
| 문법 G의 구성 |
Nonterminal, Terminal, 생성 규칙, 시작기호 |
| L(G)의 해석 |
특정 조건을 만족하는 문자열 집합으로 표현 |
| 유도 과정의 추적 |
규칙을 순차적으로 적용하여 목표 문자열 생성 |
| 문법 설계 역방향 이해 |
언어 → 문법 생성 방향도 연습해야 함 |
| aⁿbⁿcⁿ 언어의 성질 |
정규 언어로 표현 불가, PDA로 인식 불가 (→ CSL) |
📚 학습자 친화 정리
단순 문법 G₁ 예시
문법 G₁ = ( {S}, {a}, P, S )
- 생성 규칙:
S → a | aS
- 언어: L(G₁) = { aⁿ | n ≥ 1 }
유도 예시:
S ⇒ a (n = 1)
S ⇒ aS ⇒ aa (n = 2)
S ⇒ aS ⇒ aS ⇒ aaa (n = 3)
→ 모든 유도는 terminal a만으로 구성된 길이 ≥ 1의 문자열을 생성한다.
핵심 개념:
- G₁은 매우 단순한 구조지만,
a의 개수를 제어하는 언어를 표현함.
- 정규 언어로 표현 가능 (정규 표현식:
a+)
복잡한 문법 G 예시
문법 G = ( {A, B, C}, {a, b, c}, P, A )
- 생성 규칙:
A → abc A → aBbc Bb → bB Bc → Cbcc bC → Cb aC → aaB aC → aa- 생성 언어: L(G) = { aⁿbⁿcⁿ | n ≥ 1 }
→ a, b, c의 개수가 모두 동일한 문자열을 생성
🎯 주어진 문자열 생성 예시: aa bb cc
과정 예시 (n=2):
A ⇒ aBbc (A → aBbc)
⇒ abBbc (Bb → bB)
⇒ abbBc (Bb → bB)
⇒ abbbcc (Bc → Cbcc)
⇒ abbCccc (Bc → Cbcc)
⇒ abCbccc (bC → Cb)
⇒ aCbCbcc (bC → Cb)
⇒ aaB bCbcc (aC → aaB)
⇒ aaB bbcc (bC → Cb → ε) ← 여기서부터 다시 정리 필요!
→ 이 과정은 조금 복잡하므로, 유도 트리를 통해 시각화하면 이해하기 쉬움
→ 핵심은 a를 늘리는 동시에 b, c도 동시에 조절하는 로직을 만들었다는 것
✍️ 핵심 요약 정리
| 구분 |
예시 |
비고 |
| 단순 반복 언어 |
`{ aⁿ |
n ≥ 1 }` |
| 동시 반복 언어 |
`{ aⁿbⁿ |
n ≥ 1 }` |
| 삼중 반복 언어 |
`{ aⁿbⁿcⁿ |
n ≥ 1 }` |
🧠 확장 학습 방향
- 이 문법은 문맥 자유 문법(CFG)보다 복잡하므로, 이 구조가 왜 CFG로는 표현 불가능한지를 다음에 펌핑 렘마(Pumping Lemma)와 함께 다루게 될 거야.
- 언어 생성이 가능한 문법을 직접 설계해보는 연습을 자주 해보면 좋아. 특히,
- 주어진 L(G)를 보고 규칙 만들기
- 규칙을 보고 유도 가능한 문자열 파악하기
✅ 이번에 학습해야 할 내용
📌 학습 목표
- 특정 언어를 생성할 수 있도록 문법을 설계하는 방법 익히기
- 주어진 언어 표현(L) → 적절한 생성 규칙(P) 구성 능력 기르기
- embedded 구조 등 문자열 패턴에 따른 유도 규칙 설계 능력 강화
- 일반적인 프로그래밍 언어 구문 구조에도 응용되는 재귀 패턴 이해하기
🔎 중점적으로 공부해야 할 포인트
| 핵심 포인트 |
공부해야 할 내용 |
| 언어의 구조 분석 |
반복, 중첩, 대칭 구조 등을 어떻게 문법으로 표현할지 |
| 문법 구성 전략 |
ε 사용 여부, 유도 방향, 재귀 방식 결정 |
| aⁿbⁿ 유형 |
개수 맞춤이 필요한 언어에 대한 기본 패턴 |
| embedded production |
구조 내부에 또 다른 구조가 들어간 형태 표현 |
| 0ⁱ1ʲ 유형 (i ≠ j) |
단순 패턴이 아닌 비대칭 조건을 어떻게 표현할지 고민해보기 |
📚 학습자 친화 정리
문법 예시 분석
ex1) L = { 0ⁿ1ⁿ | n ≥ 1 }
- 문법:
S → 0S1 | 01
- 아이디어: 0과 1을 짝 지어가며 생성
- DFA로는 표현 불가능, PDA로 인식 가능한 문맥 자유 언어
ex2) L = { aⁿ c b^n | n ≥ 1 }
- 문법:
S → aSb | c
- 중간 구조에서 점점 a와 b를 늘리며 마지막에 c로 닫음
- 역시 PDA로 인식 가능 (중간에 스택을 뒤집는 타이밍이 c)
ex3) L = { abⁿ | n ≥ 1 }
- 문법:
A → aB B → bB | b- 첫 글자
a 이후 b를 하나 이상 붙이는 구조
- DFA로도 표현 가능
ex4) L = { aⁿbⁿcⁿ | n ≥ 1 }
P:
A -> abc
A -> aBbc
Bb -> bB
Bc -> Cbcc
bC -> Cb
aC -> aaB
aC -> aa
- 문법: 앞서 봤던 복잡한 구조 (a, b, c의 개수 일치)
- 삼중 대응 구조
- 문맥 민감 문법 또는 튜링 기계 수준의 인식기가 필요
문법 설계 전략
✅ L = { aⁿ | n ≥ 0 }
✅ L = { aⁿ | n ≥ 1 }
✅ Embedded 구조
- 예:
L = { aⁿbⁿ | n ≥ 0 }
- 문법:
S → aSb | ε
→ 중첩 구조를 재귀로 표현
예시 정리:
| 예시 |
언어 L |
문법 |
| ex1 |
{ aⁿbⁿ |
n ≥ 0 } |
| ex2 |
{ 0ⁱ1ʲ |
i ≠ j } |
| ex3 |
Conventional PL Constructs |
(별도 정의 없음, 일반적인 구조 설계에 참고) |
✍️ 핵심 요약 정리
| 개념 |
설명 |
| 문법 설계(Grammar Design) |
특정한 패턴의 언어를 생성하는 문법 구성 |
| 재귀적 정의 |
aⁿbⁿ처럼 짝수 구조를 재귀로 표현 |
| ε 규칙 사용 |
반복 종료 지점을 나타내는 데 사용 |
| embedded production |
유도 중간에 다시 자기 자신을 호출하는 구조 |
| 패턴-문법 매핑 능력 |
언어의 구조적 조건을 규칙으로 바꾸는 훈련이 중요함 |
💡 연습 방향
- 다음과 같은 문법 설계 연습을 스스로 해보면 좋아:
| 목표 언어 |
설계 포인트 |
| `{ aⁿbᵐ |
n ≥ 1, m ≥ 2 }` |
| `{ w ∈ {a,b}* |
w는 팰린드롬 }` |
| `{ aⁱbʲcᵏ |
i = j or j = k }` |
✅ 이번에 학습해야 할 내용
📌 학습 목표
- Pascal과 C 언어의 선언 구문을 형식 언어 관점에서 분석하기
- identifier, terminal, nonterminal의 개념을 실제 문법에 적용해 보기
- 프로그래밍 언어의 문장을 문법 G = (VN, VT, P, S)로 표현하는 감각 익히기
- 문법 설계 시 nonterminal 이름 짓기의 중요성 이해하기
🔎 중점적으로 공부해야 할 포인트
| 개념 |
설명 |
| 문장 구조 분석 |
실제 코드(Pascal, C)의 형식을 형식 언어 관점에서 해석 |
| identifier 역할 |
변수명 등의 식별자를 terminal 또는 nonterminal로 어떻게 정의할지 |
| terminal vs nonterminal |
실제 출력될 기호 vs 유도 도중 사용되는 기호 |
| 문법 설계 시 명명법 |
nonterminal 이름은 그 구조를 설명할 수 있도록 명확하게 정하는 것이 좋음 |
📚 학습자 친화 정리
Pascal 언어의 상수 정의 구문 분석
예시:
CONST ON = TRUE;
OFF = FALSE;
EPSILON = 1.0E-10;
구조 분석:
- 시작 키워드:
CONST → terminal symbol
- 각 정의는:
a = b; 형태
a: identifier (예: ON, OFF, EPSILON)b: 상수 값 (TRUE, FALSE, 숫자 등);: 구분자
문법적으로 보면:
ConstDefList → CONST ConstDef { ConstDef }
ConstDef → identifier = constant ;
여기서:
identifier, constant는 terminalConstDefList, ConstDef는 nonterminal
C 언어의 정수 선언 구문 분석
예시:
int i, j;
int sum;
구조 분석:
- 시작 키워드:
int → terminal
- 변수 목록:
a, a, a 형태로 나열
- 각 선언은
;로 끝남
문법적으로 보면:
DeclList → Decl { Decl }
Decl → int IdList ;
IdList → identifier | identifier , IdList
여기서:
identifier: 식별자 (예: i, j, sum)int, ,, ;: terminal symbol- 나머지 구조(IdList, Decl 등)는 nonterminal
✅ 문법 설계 시 유의사항
nonterminal의 이름은 해당 구조를 설명할 수 있게 짓는 것이 좋다.
identifierList → 식별자 목록ConstDefList → 상수 정의들Statement, Expr, Decl 같은 용어는 명확한 의미를 갖는 이름으로 추천
✍️ 핵심 요약 정리
| 항목 |
설명 |
| terminal |
실제 코드에 출력되는 기호 (예: int, =, ;) |
| nonterminal |
구문 구조를 설명하기 위한 심벌 (예: DeclList, IdList) |
| identifier |
변수명 등 구체적인 이름, 보통 terminal로 간주함 |
| 문법 설계 팁 |
nonterminal은 해당 구조의 의미를 설명하는 이름으로 설정 |
✅ 복습 퀴즈
- 다음 C 코드
int a, b, c;를 형식 문법으로 표현해보자.
Decl → int IdList ; IdList → a , b , c- 다음 Pascal 코드
CONST X = 10; Y = 20;은 어떤 구조로 해석할 수 있을까?
✅ 이번에 학습해야 할 내용
📌 학습 목표
- 주어진 문법이 특정 언어 L을 완전히 표현하고 있는지 증명하는 방법을 이해한다.
- 균형 잡힌 괄호 언어(
L = { w ∈ ( )* | w is balanced })를 생성하는 문맥 자유 문법(CFG)의 구성과 작동 방식을 이해한다.
- 귀납적 증명법(induction)을 통해 문법의 생성 능력(포함과 포함 역)을 확인할 수 있다.
▶ 문법 정의 (교과서 예제 2.16)
문법 G = ( {S}, {(, )}, {S → (S)S | ε}, S )
- 생성 규칙:
- S → (S)S : 괄호 열기와 닫기 + 재귀
- S → ε : 빈 문자열도 포함
- 생성 언어: 모든 균형 잡힌 괄호 문자열
✍️ 중점적으로 공부해야 할 내용
1. 문법이 언어를 생성하는 두 조건 증명
"G가 언어 L을 생성한다"는 것을 보이려면 아래 두 가지를 모두 증명해야 한다:
(⇒) 방향
모든 G로부터 유도 가능한 문자열은 균형 잡혀 있다.
(⇐) 방향
모든 균형 잡힌 문자열은 G에서 유도 가능하다.
🌳 (⇒) 방향: G로부터 유도된 문자열은 모두 균형 잡혀 있다
귀납법의 대상: 유도 단계 수
i) 기초 단계 (n = 1)
- S ⇒ ε
- ε는 균형 잡힌 괄호 문자열 (기본 성립)
ii) 귀납 가정
- n보다 작은 모든 유도 단계에서 생성된 문자열은 균형 잡혀 있다고 가정
iii) 귀납 단계
- n단계 유도에서
S ⇒ (S)S ⇒* (x)S =* (x)y (여기서 x, y는 S에서 유도된 부분 문자열)
- 귀납 가정에 따라 x, y는 모두 균형 잡혀 있음
- ⇒ (x)y도 균형 잡혀 있음 (괄호가 올바르게 열리고 닫힘)
✅ 따라서, G로부터 유도되는 모든 문자열은 균형 잡힌 괄호 문자열이다.
🌳 (⇐) 방향: 균형 잡힌 문자열은 G로부터 유도할 수 있다
귀납법의 대상: 문자열의 길이
i) 기초 단계 (|ω| = 0)
ii) 귀납 가정
- 길이 < 2n 인 균형 잡힌 문자열은 S에서 유도 가능하다고 가정
iii) 귀납 단계
- ω의 길이가 2n인 균형 잡힌 문자열
- 균형 잡힌 문자열은 반드시
( x ) y의 구조를 가짐
- ω = (x)y, 여기서 x, y도 균형 잡힌 문자열
- 귀납 가정에 의해 x, y는 S로부터 유도 가능
→ S ⇒ (S)S ⇒ (x)y = ω
✅ 따라서 균형 잡힌 모든 문자열은 G로부터 유도 가능
📘 정리: 어떤 걸 학습해야 하나?
| 항목 |
설명 |
| 문법 G의 구성 |
S → (S)S |
| 균형 문자열 조건 |
괄호가 짝을 이루며 닫히는 구조 |
| 귀납법 사용법 |
유도 단계 or 문자열 길이에 대해 귀납 진행 |
| 포함 방향 증명 |
(⇒): 생성된 문자열 ⊆ L, (⇐): L의 문자열 ⊆ 생성 집합 |
| 일반화 능력 |
CFG가 어떤 구조까지 표현 가능한지 감 잡기 |
✅ 이번 슬라이드에서 학습해야 할 핵심
📌 학습 목표
- 촘스키 위계(Chomsky Hierarchy)의 4가지 문법 유형(Type 0~3)을 구분할 수 있다.
- 각 문법이 생성하는 언어의 범위와 대응되는 인식기를 이해한다.
- 실제 예제 언어들이 어떤 클래스에 속하는지 분류할 수 있다.
- 정규 언어(RL), 문맥 자유 언어(CFL), 문맥 민감 언어(CSL), 계산 가능 언어(REL)의 관계를 시각적, 구조적으로 파악할 수 있다.
📘 1. Chomsky Hierarchy 요약 정리
| Type |
이름 |
생성 규칙 형태 |
생성 언어 |
인식기 |
| Type 0 |
unrestricted grammar |
아무 형태 가능 (α → β) |
REL (재귀적으로 열거 가능한 언어) |
튜링 기계 |
| Type 1 |
context-sensitive grammar |
α → β, 단 |
α |
≤ |
| Type 2 |
context-free grammar (CFG) |
A → α (A: nonterminal, α ∈ V*) |
CFL (문맥 자유 언어) |
PDA (스택 오토마타) |
| Type 3 |
regular grammar (RG) |
A → aB, A → a, A → Ba 등 |
RL (정규 언어) |
FA (유한 오토마타) |
📘 2. Chomsky 위계의 포함 관계
REL (가장 넓음)
└── CSL
└── CFL
└── RL
- 정규 언어(RL)는 문맥 자유 언어(CFL)의 부분집합
- CFL은 CSL의 부분집합
- CSL은 REL의 부분집합
→ 계층 구조를 이해하면 표현 가능성과 계산 능력의 경계를 구분할 수 있어.
📘 3. 예제 언어 분류
| 언어 |
정의 |
언어 클래스 |
| `Lₘ = { aⁿbⁿ |
n ≥ 0 }` |
개수 일치하는 a와 b |
| `L𝑑ₘ = { aⁿbⁿcⁿ |
n ≥ 1 }` |
a, b, c 개수 모두 동일 |
| `Lₘᵢ = { ωωᴿ |
ω ∈ Vᵀ* }` |
미러 문자열 (뒤집은 형태) |
| `Lᵣ = { ω |
ω = ωᴿ }` |
팰린드롬 (대칭) |
| `Lₚ = { ω |
ω는 balanced parenthesis }` |
균형 잡힌 괄호 |
📘 4. Recognizer 대응 관계
| Grammar Type |
Recognizer |
역할 (컴파일러 관점) |
| Type 0 |
Turing Machine |
일반 계산기 (언어 이론의 최상위 계산 모델) |
| Type 1 |
LBA |
제한된 메모리로 처리 가능한 복잡한 구조 |
| Type 2 |
PDA (Pushdown Automata) |
파서(Parser) 역할 수행 |
| Type 3 |
FA (Finite Automata) |
스캐너(Scanner, lexical analyzer) 역할 수행 |
✍️ 학습자가 중점적으로 공부해야 할 포인트
| 중점 항목 |
설명 |
| 문법 규칙의 형식 |
각 Type의 생산 규칙 패턴을 명확히 구분해야 함 |
| 포함 관계 |
RL ⊂ CFL ⊂ CSL ⊂ REL 관계는 암기 말고 구조적으로 이해해야 함 |
| 언어 예제 분류 |
문자열 패턴이 어느 클래스에 속하는지 식별할 수 있어야 함 |
| 오토마타 대응 |
정규 → FA, 문맥 자유 → PDA 등 인식기 대응 관계 숙지 필요 |
| 컴파일러 연결 |
Type 2 = Parser, Type 3 = Scanner로 이어짐. 실제 적용처 연결하면 더 쉬움 |
📌 학습용 연습 문제 제안
- 다음 언어는 어떤 클래스에 속하는가?
- (a)
L = { aⁿbᵐcⁿ | n, m ≥ 0 }
- (b)
L = { w ∈ {a,b}* | w는 팰린드롬 }
- (c)
L = { aⁿbⁿcⁿ | n ≥ 0 }
- (d)
L = { aᵢbʲ | i ≠ j }
- 다음 언어가 CFL인지 아닌지 증명하라 (또는 추론 근거를 설명하라)
- 각 문법 유형(Type 0~3)에 해당하는 문법을 1개씩 구성해보라
| 언어 클래스 |
표현 가능 구조 |
예시 언어 |
설명 |
| 정규 언어 (RL) |
단순 반복, 접두사/접미사, 특정 패턴 나열 |
{ a*b }, { (ab)* }, { 0(0+1)*1 } |
반복은 되지만, 상호 의존된 수는 못 셈 |
| 문맥 자유 언어 (CFL) |
중첩 구조, 좌우 대응, 균형 괄호 |
{ aⁿbⁿ }, { (ⁿ)ⁿ }, { w ∈ {a,b}\* | w = wᴿ } |
|
| 문맥 민감 언어 (CSL) |
다중 수의 동시 일치, 길이 비교 |
{ aⁿbⁿcⁿ }, { aᵐbⁿcᵐdⁿ }, { w | #a(w) = #b(w) = #c(w) } |
|
| 계산 가능 언어 (REL) |
임의의 조건, 수학적 성질, Turing-complete 언어 |
{ aⁿ | n은 소수 }, { M ⊢ w } |
|