Complementation of Regular Language 요약 및 정리
1. 개요
정규 언어(Regular Language)의 여집합(Complementation)은 주어진 정규 언어에서 해당 언어에 속하지 않는 모든 문자열을 포함하는 언어를 의미한다. 즉, 어떤 DFA(Deterministic Finite Automaton)가 특정 언어 L을 인식한다고 할 때, 해당 DFA의 수락 상태(Accepting States)와 비수락 상태(Non-Accepting States)를 뒤바꾸면 L^c (언어 L의 여집합)를 인식하는 DFA를 만들 수 있다.
2. 정규 언어의 여집합 특성
- 정규 언어는 여집합을 취해도 정규 언어이다.
즉, 만약 언어 L이 정규 언어라면, 그 여집합 L^c도 정규 언어이다. - DFA를 이용해 쉽게 구할 수 있음.
L을 인식하는 DFA를 구성한 후, 수락 상태와 비수락 상태를 바꾸는 것만으로 L^c를 인식하는 DFA를 얻을 수 있다.
3. DFA를 이용한 여집합 계산 방법
- L을 인식하는 결정적 유한 자동자(DFA)를 구성한다.
- DFA의 모든 수락 상태와 비수락 상태를 뒤바꾼다.
- 이렇게 변환된 DFA는 L^c를 인식하는 DFA가 된다.
예제 1: "1로 끝나는 문자열"의 여집합
주어진 DFA:
이진 문자열(0과 1) 중 1로 끝나는 문자열을 인식하는 DFA를 고려하자.
- 초기 상태에서 0을 입력하면 그대로 남아있음.
- 1을 입력하면 수락 상태로 이동.
- 수락 상태에서 다시 1을 입력하면 계속 유지됨.
- 0을 입력하면 다시 초기 상태로 돌아감.
DFA 변환:
- 여집합을 취하면, 이제 "1로 끝나지 않는 문자열"을 인식해야 함.
- 따라서 원래 DFA의 수락 상태와 비수락 상태를 뒤집는다.
- 결과적으로 1로 끝나는 경우가 아닌 문자열을 인식하는 DFA가 생성됨.
예제 2: "짝수 개의 0을 포함하는 문자열"의 여집합
주어진 DFA:
- 0이 짝수 개 등장하는 경우를 인식하는 DFA가 있다고 하자.
- 0을 한 개 입력하면 상태가 변경되고, 두 개 입력하면 원래 상태로 돌아감.
- 1을 입력하면 상태는 변하지 않음.
DFA 변환:
- 여집합을 취하면, "홀수 개의 0을 포함하는 문자열"을 인식해야 함.
- DFA의 수락 상태와 비수락 상태를 뒤집어 변환을 수행한다.
4. NFA 및 DFA 변환 시 고려 사항
- DFA에서는 간단히 수락 상태를 변경하면 여집합을 얻을 수 있음.
- NFA(비결정적 유한 자동자)에서는 직접 여집합을 구하기 어려움.
일반적으로 NFA를 DFA로 변환한 후 여집합을 취하는 방식이 사용됨.
DFA에서 여집합을 구하는 과정 요약
- 주어진 언어 L을 인식하는 DFA를 구성.
- DFA에서 모든 수락 상태와 비수락 상태를 반전.
- 변환된 DFA는 L^c를 인식.
NFA의 경우
- NFA를 DFA로 변환 (Subset Construction Algorithm 활용).
- 변환된 DFA의 수락 상태를 반전.
- L^c를 인식하는 DFA가 생성됨.
5. 응용 및 활용
- 언어 연산: 언어의 여집합을 구한 후, 교집합이나 합집합과 같은 연산을 수행하는 데 유용함.
- 형식 언어 이론 및 자동화 이론: 정규 표현식 및 유한 자동자의 개념을 확장하는 데 사용됨.
- 보안 및 인증 시스템: 특정 패턴을 허용하거나 차단하는 방식으로 활용 가능.
네가 원하는 대로 LaTeX 수식 표기에서 불필요한 슬래시와 괄호를 제거하고 깔끔하게 정리해 줄게.
1. 문제 정의
주어진 문제는 ‘10’로 끝나지 않는 모든 이진 문자열을 인식하는 DFA를 구성하는 것이다.
✅ 단계적 접근 방법:
- ‘10’로 끝나는 문자열을 인식하는 DFA를 먼저 구성한다.
- DFA의 수락 상태를 반전하여 여집합을 얻는다.
2. ‘10’로 끝나는 문자열을 인식하는 DFA 구성
우선, ‘10’로 끝나는 문자열을 인식하는 DFA를 만들자.
(1) 상태 정의
- q0 → 초기 상태 (아직 ‘10’ 패턴이 시작되지 않음)
- q1 → ‘1’을 입력받은 상태
- q2 → ‘10’이 완성된 상태 (최종 상태)
(2) 상태 전이 테이블 (Transition Table)
| 현재 상태 | 입력: 0 → 다음 상태 | 입력: 1 → 다음 상태 |
|---|---|---|
| q0 (초기 상태) | q0 (그대로 유지) | q1 (‘1’이 입력됨) |
| q1 | q2 (‘10’ 완성) | q1 (계속 ‘1’ 유지) |
| q2 (최종 상태) | q2 (계속 유지) | q1 (다시 시작) |
3. ‘10’로 끝나지 않는 문자열을 인식하는 DFA 구성 (여집합 취하기)
- DFA의 여집합을 만들려면 최종 상태(accepting state)와 비최종 상태(non-accepting state)를 반전하면 된다.
- 즉, q2 (기존 DFA의 최종 상태)를 비최종 상태로 변경하고, 기존 비최종 상태였던 q0과 q1을 최종 상태로 변경한다.
(1) 상태 전이 테이블 (Complemented DFA)
| 현재 상태 | 입력: 0 → 다음 상태 | 입력: 1 → 다음 상태 | 최종 상태 여부 |
|---|---|---|---|
| q0 (초기 상태) | q0 | q1 | ✅ (최종 상태) |
| q1 | q2 | q1 | ✅ (최종 상태) |
| q2 | q2 | q1 | ❌ (비최종 상태) |
💡 이제 새로운 DFA는 ‘10’로 끝나지 않는 문자열만 인식한다!
4. DFA 다이어그램
(1) 원래 DFA (’10’로 끝나는 문자열을 인식)
(q0) --1--> (q1) --0--> (q2) [Final]
| |
| +--1--> (q1)
|
+--0--> (q0)(2) 여집합 DFA (‘10’로 끝나지 않는 문자열을 인식)
(q0) --1--> (q1) --0--> (q2)
| |
| +--1--> (q1) [Final]
|
+--0--> (q0) [Final]✅ 이제 q0과 q1이 최종 상태이고, q2는 비최종 상태로 변경됨!
Complementation of Regular Language - 요약 및 정리 (DFA for strings not ending with '10' or '00')
이 문제에서는 ‘10’ 또는 ‘00’로 끝나지 않는 모든 이진 문자열을 인식하는 DFA를 구성해야 한다.
즉, DFA의 여집합을 취하는 과정에서 기존 DFA의 수락 상태와 비수락 상태를 반전하는 방법을 사용한다.
1. 문제 분석 및 접근 방법
주어진 문자열이 다음 두 패턴으로 끝나지 않도록 하는 DFA를 설계해야 한다.
✅ 허용되지 않는 패턴:
- 문자열이 ‘10’로 끝나는 경우
- 문자열이 ‘00’로 끝나는 경우
이 문제를 해결하기 위해 다음 단계를 수행한다.
- ‘10’ 또는 ‘00’로 끝나는 문자열을 인식하는 DFA를 먼저 구성한다.
- DFA의 수락 상태를 반전하여 여집합을 구한다.
2. ‘10’ 또는 ‘00’로 끝나는 문자열을 인식하는 DFA 구성
우선, ‘10’ 또는 ‘00’로 끝나는 문자열을 인식하는 DFA를 만든다.
(1) 상태 정의
- q0 → 초기 상태 (아직 ‘10’ 또는 ‘00’ 패턴이 시작되지 않음)
- q1 → ‘1’을 입력받은 상태
- q2 → ‘0’을 입력받은 상태
- q3 → ‘10’이 완성된 상태 (최종 상태)
- q4 → ‘00’이 완성된 상태 (최종 상태)
(2) 상태 전이 테이블
| 현재 상태 | 입력: 0 → 다음 상태 | 입력: 1 → 다음 상태 | 최종 상태 여부 |
|---|---|---|---|
| q0 (초기 상태) | q2 | q1 | ❌ (비최종 상태) |
| q1 | q3 | q1 | ❌ (비최종 상태) |
| q2 | q4 | q1 | ❌ (비최종 상태) |
| q3 | q4 | q1 | ✅ (‘10’로 끝나는 경우) |
| q4 | q4 | q1 | ✅ (‘00’로 끝나는 경우) |
✅ 이 DFA는 ‘10’ 또는 ‘00’로 끝나는 문자열을 인식한다.
✅ 최종 상태는 q3 (‘10’로 끝나는 경우)와 q4 (‘00’로 끝나는 경우)이다.
3. 여집합을 위한 DFA 변환 (수락 상태 반전)
- DFA의 여집합을 만들려면 최종 상태(accepting states)와 비최종 상태(non-accepting states)를 반전하면 된다.
- 즉, q3과 q4 (기존 DFA의 최종 상태)를 비최종 상태로 변경하고, 기존 비최종 상태였던 q0, q1, q2를 최종 상태로 변경한다.
(1) 변환된 DFA의 상태 전이 테이블
| 현재 상태 | 입력: 0 → 다음 상태 | 입력: 1 → 다음 상태 | 최종 상태 여부 |
|---|---|---|---|
| q0 (초기 상태) | q2 | q1 | ✅ (최종 상태) |
| q1 | q3 | q1 | ✅ (최종 상태) |
| q2 | q4 | q1 | ✅ (최종 상태) |
| q3 | q4 | q1 | ❌ (비최종 상태) |
| q4 | q4 | q1 | ❌ (비최종 상태) |
✅ 이제 새로운 DFA는 ‘10’ 또는 ‘00’로 끝나지 않는 문자열만 인식한다!
4. DFA 다이어그램
(1) 원래 DFA (’10’ 또는 ‘00’로 끝나는 문자열을 인식)
(q0) --1--> (q1) --0--> (q3) [Final]
| |
| +--1--> (q1)
|
+--0--> (q2) --0--> (q4) [Final]
|
+--1--> (q1)(2) 여집합 DFA (‘10’ 또는 ‘00’로 끝나지 않는 문자열을 인식)
(q0) --1--> (q1) --0--> (q3)
| |
| +--1--> (q1) [Final]
|
+--0--> (q2) --0--> (q4)
|
+--1--> (q1) [Final]✅ 이제 q0, q1, q2가 최종 상태이고, q3과 q4는 비최종 상태로 변경됨!
DFA for Strings Without Consecutive '00' or '11' - 요약 및 정리
이 문제에서는 연속된 ‘00’ 또는 ‘11’이 포함되지 않는 모든 이진 문자열을 인식하는 DFA를 구성해야 한다.
즉, DFA의 여집합을 취하는 과정에서 기존 DFA의 수락 상태와 비수락 상태를 반전하는 방법을 사용한다.
1. 문제 분석 및 접근 방법
주어진 문자열에서 연속된 '00' 또는 '11'이 포함되면 거부해야 한다.
✅ 허용되지 않는 패턴:
- 문자열이 ‘00’ (연속된 0) 포함
- 문자열이 ‘11’ (연속된 1) 포함
이 문제를 해결하기 위해 다음 단계를 수행한다.
- ‘00’ 또는 ‘11’이 포함된 문자열을 인식하는 DFA를 먼저 구성한다.
- DFA의 수락 상태를 반전하여 여집합을 구한다.
2. ‘00’ 또는 ‘11’이 포함된 문자열을 인식하는 DFA 구성
우선, 연속된 ‘00’ 또는 ‘11’이 포함된 문자열을 인식하는 DFA를 만든다.
(1) 상태 정의
- q0 → 초기 상태 (아직 ‘00’ 또는 ‘11’ 패턴이 시작되지 않음)
- q1 → ‘0’을 입력받은 상태
- q3 → ‘1’을 입력받은 상태
- q2 → ‘00’이 나타난 상태 (최종 상태, Dead State)
- q4 → ‘11’이 나타난 상태 (최종 상태, Dead State)
(2) 상태 전이 테이블
| 현재 상태 | 입력: 0 → 다음 상태 | 입력: 1 → 다음 상태 | 최종 상태 여부 |
|---|---|---|---|
| q0 (초기 상태) | q1 | q3 | ❌ (비최종) |
| q1 | q2 | q3 | ❌ (비최종) |
| q3 | q1 | q4 | ❌ (비최종) |
| q2 (Dead State) | q2 | q2 | ✅ (‘00’ 포함) |
| q4 (Dead State) | q4 | q4 | ✅ (‘11’ 포함) |
✅ 이 DFA는 연속된 ‘00’ 또는 ‘11’이 포함된 문자열을 인식한다.
✅ 최종 상태는 q2 (‘00’ 포함)와 q4 (‘11’ 포함)이다.
✅ q2와 q4는 한 번 도달하면 빠져나올 수 없는 Dead State이다.
3. 여집합을 위한 DFA 변환 (수락 상태 반전)
- DFA의 여집합을 만들려면 최종 상태와 비최종 상태를 반전하면 된다.
- 즉, q2와 q4 (기존 DFA의 최종 상태)를 비최종 상태로 변경하고, 기존 비최종 상태였던 q0, q1, q3을 최종 상태로 변경한다.
(1) 변환된 DFA의 상태 전이 테이블
| 현재 상태 | 입력: 0 → 다음 상태 | 입력: 1 → 다음 상태 | 최종 상태 여부 |
|---|---|---|---|
| q0 (초기 상태) | q1 | q3 | ✅ (최종 상태) |
| q1 | q2 | q3 | ✅ (최종 상태) |
| q3 | q1 | q4 | ✅ (최종 상태) |
| q2 (Dead State) | q2 | q2 | ❌ (비최종) |
| q4 (Dead State) | q4 | q4 | ❌ (비최종) |
✅ 이제 새로운 DFA는 연속된 ‘00’ 또는 ‘11’이 포함되지 않은 문자열만 인식한다!
4. DFA 다이어그램
(1) 원래 DFA (‘00’ 또는 ‘11’이 포함된 문자열을 인식)
(q0) --0--> (q1) --0--> (q2) [Final, Dead State]
| |
| +--1--> (q3)
|
+--1--> (q3) --1--> (q4) [Final, Dead State]
|
+--0--> (q1)(2) 여집합 DFA (‘00’ 또는 ‘11’이 포함되지 않은 문자열을 인식)
(q0) --0--> (q1) --0--> (q2)
| |
| +--1--> (q3) [Final]
|
+--1--> (q3) --1--> (q4)
|
+--0--> (q1) [Final]✅ 이제 q0, q1, q3이 최종 상태이고, q2, q4는 비최종 상태로 변경됨!
Complementation of Regular Languages - 요약 및 정리 (L과 L' 관계 정리)
이 내용에서는 정규 언어 L과 그 여집합 L'을 DFA로 표현할 때의 관계를 정리하고 있다.
즉, L을 인식하는 DFA M과 여집합 L'을 인식하는 DFA M'의 차이점을 논의한다.
1. 정규 언어의 여집합 (Complement of Regular Language)
- 주어진 DFA M이 언어 L을 인식한다고 하자.
- 여집합 언어 L'은 L' = Σ* - L 로 정의된다.
즉, 전체 가능한 문자열 집합(알파벳 Σ의 모든 조합)에서 L을 제외한 것이다. - L'을 인식하는 DFA를 M'이라고 하자.
✅ 핵심 개념:
- DFA의 상태 개수는 변하지 않는다.
- 최종 상태(accepting states)와 비최종 상태(non-accepting states)만 반전된다.
2. DFA M과 M'의 상태 개수 관계
- M과 M'은 동일한 수의 상태(states)를 가진다.
- 만약 M이 n개의 상태를 가진다면, M'도 n개의 상태를 가진다.
(즉, 상태 개수는 동일)
✅ 요약:
- DFA의 상태 개수는 변하지 않음.
- 즉, |Q_M| = |Q_M'| (M과 M'의 상태 개수 동일)
3. 최종 상태(accepting states)의 변화
- 만약 DFA M이 k개의 최종 상태(final states)를 가지고 있다면,
DFA M'의 최종 상태 개수는 n - k 개가 된다.
✅ 수식 표현:
- DFA M에서 최종 상태 개수가 k개라면,
- DFA M'에서 최종 상태 개수는 n - k 개가 된다.
📌 조건:
- k ≤ n (최종 상태 개수는 전체 상태 개수를 초과할 수 없음)
✅ 핵심 개념:
- 기존 DFA의 최종 상태 → 비최종 상태로 변경
- 기존 DFA의 비최종 상태 → 최종 상태로 변경
- 따라서 최종 상태 개수는 n - k 개가 된다.
4. 시각적 정리 (DFA 변환 과정)
(1) 원래 DFA M
M:
- 상태 개수: n
- 최종 상태 개수: k
- 비최종 상태 개수: n - k(2) 여집합 DFA M'
M':
- 상태 개수: n (그대로 유지)
- 최종 상태 개수: n - k (반전됨)
- 비최종 상태 개수: k (반전됨)✅ 핵심 요약:
- M과 M'의 상태 개수는 동일하다.
- 최종 상태 개수는 k → n - k로 반전된다.
'강의 > Theory of Computation' 카테고리의 다른 글
| NFA to DFA Conversion: Subset Construction (0) | 2025.02.12 |
|---|---|
| Non-Deterministic PushDown Automata (NFA) (0) | 2025.02.05 |
| Construction of Minimal DFA Examples (0) | 2025.02.02 |
| Construct Minimal DFA (0) | 2025.02.01 |
| TOC Fundamentals, Regular Languages (0) | 2025.01.28 |