Non-Deterministic PushDown Automata (NFA)

강의/Theory of Computation

Non-Deterministic PushDown Automata (NFA)

studylida 2025. 2. 5. 05:28

요약 및 정리: 비결정적 유한 자동자(NFA, Non-deterministic Finite Automaton)

1. NFA의 개념

NFA(비결정적 유한 자동자)는 DFA(결정적 유한 자동자)와 유사하지만 각 입력 기호에 대해 여러 개의 가능한 상태 전이가 존재할 수 있음.
특정 입력에서 0개 이상의 상태로 전이할 수 있음. (즉, 특정 입력에 대해 전이가 없을 수도 있고, 하나 이상의 상태로 이동할 수도 있음)

2. NFA의 정의

NFA는 5개의 요소(Q, Σ, δ, q₀, F) 로 정의됨:
- Q (상태 집합): 자동자가 가질 수 있는 모든 상태.
- Σ (입력 알파벳): 허용되는 입력 기호 집합.
- δ (전이 함수): 현재 상태와 입력 기호에 따라 다음 상태를 결정 (0개 이상의 상태로 전이 가능).
- q₀ (초기 상태): 시작 상태.
- F (수락 상태): 입력을 수락하는 상태 집합.

3. DFA와 NFA의 차이점

구분	DFA (결정적 유한 자동자)	NFA (비결정적 유한 자동자)
전이 함수	하나의 입력에서 정확히 하나의 상태로 전이	하나의 입력에서 여러 개의 상태로 전이 가능
전이 개수	모든 상태에서 모든 입력에 대해 전이가 반드시 존재해야 함	특정 상태에서 입력에 대한 전이가 존재하지 않을 수도 있음
수락 조건	문자열을 입력했을 때 유일한 경로가 있어야 함	여러 경로 중 하나라도 수락 상태에 도달하면 됨
구현 방식	상태마다 유일한 경로를 따라가야 함	여러 경로를 동시에 따라갈 수 있음
변환 가능 여부	NFA로 변환 가능	DFA로 변환 가능 (Subset Construction Algorithm 사용)

4. NFA의 동작 방식

특정 입력을 주었을 때, 현재 상태에서 여러 개의 상태로 동시에 이동 가능.
여러 경로 중 하나라도 수락 상태에 도달하면 해당 문자열을 수락.
반대로, 모든 가능한 경로가 비수락 상태에서 끝나면 거부.

5. NFA 예제

예제 1: 입력이 `0` 또는 `1`일 때, 특정 상태로 이동하는 NFA

상태 집합: Q = {q₀, q₁, q₂}
입력 알파벳: Σ = {0, 1}
초기 상태: q₀
수락 상태: F = {q₂}
전이 함수:
- δ(q₀, 0) → {q₁, q₂} (0을 입력하면 q₁ 또는 q₂로 갈 수 있음)
- δ(q₀, 1) → {q₀} (1을 입력하면 다시 q₀으로 돌아감)
- δ(q₁, 0) → {q₂} (q₁에서 0을 입력하면 q₂로 이동)
- δ(q₁, 1) → {q₁} (q₁에서 1을 입력하면 q₁에 머무름)
- δ(q₂, 0) → {q₂} (q₂에서 0을 입력하면 q₂에 머무름)
- δ(q₂, 1) → {q₂} (q₂에서 1을 입력하면 q₂에 머무름)

예제 2: "01"을 포함하는 문자열을 인식하는 NFA

상태 집합: Q = {q₀, q₁, q₂}
입력 알파벳: Σ = {0, 1}
초기 상태: q₀
수락 상태: F = {q₂}
전이 함수:
- δ(q₀, 0) → {q₀, q₁} (q₀에서 0을 입력하면 q₀ 또는 q₁로 이동 가능)
- δ(q₁, 1) → {q₂} (q₁에서 1을 입력하면 q₂로 이동)
- δ(q₂, 0) → {q₂} (q₂에서 0을 입력하면 q₂에 머무름)
- δ(q₂, 1) → {q₂} (q₂에서 1을 입력하면 q₂에 머무름)

6. NFA의 수락 조건

주어진 입력 문자열에 대해 모든 가능한 경로를 탐색.
최소 하나의 경로라도 수락 상태에 도달하면 해당 문자열을 수락.
모든 가능한 경로가 비수락 상태에서 끝나면 거부.

7. NFA의 특징

표현력: DFA와 동일한 표현력을 가짐 (모든 NFA는 DFA로 변환 가능).
단순한 설계: DFA보다 상태 개수를 줄일 수 있어 설계가 간단함.
비효율적인 실행: 입력을 처리할 때 여러 경로를 동시에 탐색해야 하므로 DFA보다 느릴 수 있음.

8. NFA를 DFA로 변환 (Subset Construction Algorithm)

NFA를 DFA로 변환할 때 상태의 집합을 사용하여 새로운 DFA의 상태를 구성함.
예를 들어, NFA의 여러 상태를 하나의 DFA 상태로 묶는 방식으로 변환.

9. DFA와 NFA의 계산 능력 비교

DFA는 모든 입력에 대해 유일한 경로를 따라가므로 계산이 직관적이고 빠름.
NFA는 비결정성을 활용하여 여러 경로를 동시에 탐색하므로 표현력은 같지만 구현이 다소 복잡함.
DFA와 NFA는 동일한 언어를 인식할 수 있음, 즉, 모든 NFA는 DFA로 변환 가능.

10. NFA의 활용 사례

정규 표현식 해석기 (Regex Engines)
검색 알고리즘 (검색어 자동 완성)
자연어 처리 (NLP)에서 패턴 매칭
네트워크 프로토콜 분석
보안 시스템에서 침입 탐지 (Intrusion Detection Systems)

비결정적 유한 자동자(NFA)의 언어(Language of NFA) 요약 및 정리

1. NFA의 언어란?

NFA의 언어(Language of NFA)는 NFA가 수락하는 모든 단어들의 집합이다.
입력 문자열을 처리한 후 최소한 하나의 경로가 수락 상태(Final State)에 도달하면 해당 문자열을 수락한다.
즉, 모든 가능한 실행 경로 중 하나라도 수락 상태에 도달하면 해당 문자열은 NFA의 언어에 포함된다.
NFA에서 모든 수락 상태를 모아 언어를 형성하며, 이를 "NFA의 언어"라고 한다.

2. NFA의 언어 개념

DFA와 마찬가지로, NFA도 특정 언어를 정의할 수 있음.
NFA의 언어는 NFA가 모든 가능한 실행 경로를 따라가면서 수락할 수 있는 단어들의 집합으로 구성된다.
주어진 NFA에 대해 가능한 모든 입력 문자열을 고려하고, 최종적으로 수락 상태에 도달하는 모든 문자열을 수집하면 그 집합이 바로 NFA의 언어이다.
예제:
- 만약 NFA가 "01" 또는 "10"을 수락하도록 구성되어 있다면, 해당 NFA의 언어는 L = {01, 10}이다.
- 즉, NFA는 "01"이나 "10"을 입력받았을 때, 최소한 하나의 경로가 수락 상태에 도달하면 해당 문자열을 언어에 포함한다.

3. NFA의 언어와 DFA의 언어

NFA와 DFA는 동일한 언어를 표현할 수 있다.
같은 언어에 대해 여러 개의 NFA를 만들 수 있음 → 즉, 하나의 언어를 표현하는 NFA는 유일하지 않다.
반면, DFA는 최소화 과정(minimization)을 거치면 유일한 DFA로 수렴한다.
즉, 같은 언어를 표현하는 DFA는 유일하지만, NFA는 여러 개 존재할 수 있다.
NFA를 DFA로 변환할 경우, 항상 하나의 최소 DFA가 존재한다.

중요한 점:

같은 언어를 수락하는 NFA는 구조적으로 다르게 구현될 수 있음.

그러나 같은 언어를 표현하는 DFA는 최소화 과정 후 유일한 DFA로 수렴.

4. NFA의 특징

NFA는 유효한 입력(Valid Input)만 고려하고, 무효한 입력(Invalid Input)은 고려하지 않음.
모든 실행 경로 중 하나라도 수락 상태에 도달하면 문자열을 수락한다.
어떤 입력에 대해서도 전이가 없거나, 수락 상태에 도달하지 못하면 거부(Reject)된다.
따라서, NFA에는 "Dead State(죽음 상태)"가 필수적이지 않음.
(DFA에서는 특정 상태에서 더 이상 진행할 수 없는 상태를 명확하게 정의해야 하지만, NFA에서는 그럴 필요가 없음.)

5. NFA의 수락 및 거부 과정

(1) 수락(Acceptance) 과정

주어진 입력 문자열이 최소한 하나의 실행 경로를 통해 수락 상태에 도달하면, 해당 문자열은 수락(Accepted) 된다.
예제:
- NFA에서 "010"을 입력했을 때, 여러 개의 실행 경로 중 하나라도 수락 상태에 도달하면, "010"은 수락된다.

(2) 거부(Reject) 과정

입력 문자열을 처리한 후 모든 실행 경로가 비수락 상태에서 끝나면 해당 문자열은 거부(Rejected) 된다.
예제:
- NFA에서 "1101"을 입력했을 때, 모든 실행 경로가 비수락 상태에서 종료되면, "1101"은 거부된다.

6. NFA의 실행 및 결정 과정

입력 문자열을 처리하면서 가능한 모든 상태 전이를 탐색.
하나라도 수락 상태에 도달하면, 문자열은 수락됨.
모든 가능한 경로가 비수락 상태에서 종료되면, 문자열은 거부됨.
NFA는 "Dead State(죽음 상태)"를 필수적으로 가질 필요가 없음.
비결정성(Nondeterminism) 때문에, 같은 언어를 표현하는 NFA는 여러 개 존재할 수 있음.

NFA(비결정적 유한 자동자) 구성 및 상태 전이 다이어그램: 허용된 문자열 {ε, "10", "01"}

1. 목표

주어진 언어: NFA는 다음 세 개의 문자열만 수락해야 함.
1. 빈 문자열(ε)
2. "10"
3. "01"
이 언어에 포함되지 않은 문자열은 수락하지 않도록 NFA를 설계.

2. NFA의 상태 구성

q₀ (초기 상태, 빈 문자열 수락 상태): 빈 문자열(ε)은 자동으로 수락해야 하므로 q₀을 수락 상태로 설정.
q₁, q₂, q₃, q₄: "10"과 "01"을 수락하기 위해 필요한 상태.

3. 상태 전이 함수

현재 상태	입력	다음 상태
q₀	ε	q₀ (빈 문자열 수락)
q₀	1	q₁
q₁	0	q₂ (수락 상태)
q₀	0	q₃
q₃	1	q₄ (수락 상태)

4. NFA 상태 전이 다이어그램

(q₀) --ε--> (q₀)  (빈 문자열 수락)

(q₀) --1--> (q₁) --0--> (q₂)  (수락 상태)

(q₀) --0--> (q₃) --1--> (q₄)  (수락 상태)

5. NFA의 동작 방식

q₀에서 빈 문자열(ε)을 수락 → 따라서, q₀은 수락 상태.
"10"을 수락하는 과정:
- q₀에서 1을 입력하면 q₁로 이동.
- q₁에서 0을 입력하면 q₂로 이동 → 수락 상태.
"01"을 수락하는 과정:
- q₀에서 0을 입력하면 q₃으로 이동.
- q₃에서 1을 입력하면 q₄로 이동 → 수락 상태.

6. NFA의 특징

유효한 문자열만 고려하며, 불필요한 상태나 전이를 추가할 필요 없음.
각각의 수락 상태(q₀, q₂, q₄)는 해당 문자열을 완성한 지점.
DFA와 달리, NFA에서는 같은 언어를 표현하는 여러 개의 상태 구성이 가능함.
한 개의 입력에 대해 여러 개의 상태로 전이할 수 있으며, 반드시 모든 입력에 대한 전이를 정의할 필요는 없음.

NFA(비결정적 유한 자동자) 구성 및 상태 전이 다이어그램: 언어 L = { 0ⁿ 1 0ᵐ | m, n ≥ 1 }

1. 목표

주어진 언어는 다음과 같은 규칙을 가진다:
- 처음에는 하나 이상의 0(n ≥ 1)이 있어야 함.
- 중간에는 반드시 하나의 1이 포함되어야 함.
- 마지막에는 하나 이상의 0(m ≥ 1)이 있어야 함.
따라서, 언어 L은 L = { 0ⁿ 1 0ᵐ | m, n ≥ 1 } 형태를 갖는다.

2. NFA의 상태 구성

q₀ (초기 상태): 최소한 하나의 0을 입력받아야 하므로 q₀에서 0을 입력받아 q₁로 이동.
q₁: 여러 개의 0을 입력받을 수 있으며, 최소한 하나의 0이 포함된 상태.
q₂: 1을 입력받아 중간 부분을 처리하는 상태.
q₃: 1 이후에 0을 입력받아 최소한 하나의 0을 포함하는 상태.
q₄ (수락 상태): q₃에서 추가적인 0을 입력받아 도달하는 최종 상태.

3. 상태 전이 함수

현재 상태	입력	다음 상태
q₀	0	q₁
q₁	0	q₁
q₁	1	q₂
q₂	0	q₃
q₃	0	q₃
q₃	ε	q₄ (수락 상태)

4. NFA 상태 전이 다이어그램

(q₀) --0--> (q₁) --0--> (q₁) --1--> (q₂) --0--> (q₃) --0--> (q₃) --ε--> (q₄)
  |                                                                |
  |----------------------------------------------------------------|
                              (수락 상태)

5. NFA의 동작 방식

q₀ → q₁ (최소 1개의 0 필요)
- q₀에서 0을 입력해야만 q₁으로 이동 가능.
- 추가적인 0을 입력하면 여전히 q₁에 머무름.
q₁ → q₂ (1 입력, 중간 부분)
- 최소한 하나의 0을 입력한 후 1을 입력하면 q₂로 이동.
q₂ → q₃ (최소 1개의 0 필요)
- 1 입력 이후 최소한 하나의 0이 필요하므로 0을 입력하면 q₃로 이동.
q₃ → q₄ (추가적인 0 가능, 최종 수락 상태)
- q₃에서 0을 계속 입력하면 q₃에 머무름.
- q₃에서 ε-전이를 통해 q₄로 이동 → q₄가 최종 수락 상태.

6. NFA의 특징

언어 L = { 0ⁿ 1 0ᵐ | m, n ≥ 1 }에 맞게 설계됨.
NFA는 ε-전이를 사용할 수 있으므로, 특정 상태에서 자동으로 수락 상태로 이동 가능.
- ε-전이(Epsilon Transition)는 입력 심볼 없이 상태를 자동으로 전이할 수 있는 기능을 의미한다. 즉, 어떠한 입력도 소비하지 않고 다른 상태로 이동할 수 있는 전이이다.
각각의 수락 상태(q₄)는 해당 문자열을 완성한 지점.
DFA와 달리, 상태 수를 줄일 수 있고 여러 개의 경로를 가질 수 있음.

7. ε-전이를 사용하지 않도록 수정된 NFA

1. 수정된 NFA의 상태 전이

현재 상태	입력	다음 상태
q₀	0	q₁
q₁	0	q₁
q₁	1	q₂
q₂	0	q₃ (수락 상태)
q₃	0	q₃

2. 수정된 NFA의 상태 전이 다이어그램

(q₀) --0--> (q₁) --0--> (q₁) --1--> (q₂) --0--> (q₃)
                                         |
                                         v
                                       (q₃) (수락 상태, 0 입력 시 q₃ 유지)

3. 수정된 NFA의 동작 방식

q₀ → q₁ (최소 1개의 0 필요)
- q₀에서 0을 입력해야만 q₁으로 이동 가능.
- 추가적인 0을 입력하면 여전히 q₁에 머무름.
q₁ → q₂ (1 입력, 중간 부분)
- 최소한 하나의 0을 입력한 후 1을 입력하면 q₂로 이동.
q₂ → q₃ (최소 1개의 0 필요, 수락 상태)
- 1 입력 이후 최소한 하나의 0이 필요하므로 0을 입력하면 q₃로 이동.
q₃에서 추가적인 0 입력 시 계속 q₃ 유지
- 즉, q₃가 최종 수락 상태이며, 0을 추가로 입력해도 q₃에 머무름.

4. ε-전이 없이 구성할 경우의 장점

구현이 단순해짐
- ε-전이가 필요 없으므로 상태가 명확해짐.
DFA 변환이 용이
- ε-전이가 있으면 DFA 변환 과정에서 ε-클로저를 고려해야 하지만, ε-전이가 없으면 상태 변환이 더 직관적임.
여분의 상태(q₄)가 필요 없음
- q₃를 수락 상태로 설정함으로써 q₄를 추가하지 않아도 됨.

NFA(비결정적 유한 자동자) 구성 및 상태 전이 다이어그램: 언어 L = { 0²ⁿ 1ᵐ | m, n ≥ 1 }

1. 목표

주어진 언어는 다음과 같은 규칙을 가진다:
- 0이 짝수 개(2n개, n ≥ 1)여야 한다.
- 1이 최소 한 개 이상(m ≥ 1) 포함되어야 한다.
즉, 언어 L은 L = { 0²ⁿ 1ᵐ | m, n ≥ 1 } 형태를 갖는다.

2. NFA의 상태 구성

q₀ (초기 상태): 최소 두 개의 0을 입력받아야 하므로 q₀에서 0을 입력받아 q₁으로 이동.
q₁: 첫 번째 0을 입력한 상태.
q₂: 두 번째 0을 입력하여 최소 조건을 충족한 상태.
q₃(수락 상태): 1을 입력하여 조건을 만족하는 상태.

3. 상태 전이 함수

현재 상태	입력	다음 상태
q₀	0	q₁
q₁	0	q₂
q₂	0	q₁ (짝수 개를 유지)
q₂	1	q₃(수락상태)
q₃	1	q₃

4. NFA 상태 전이 다이어그램

(q₀) --0--> (q₁) --0--> (q₂) --1--> (q₃) --1--> (q₃)
                         |
                         0
                         v
                        (q₁)

5. NFA의 동작 방식

q₀ → q₁ → q₂ (최소 2개의 0 입력)
- q₀에서 0을 입력해야만 q₁으로 이동 가능.
- q₁에서 0을 입력하면 q₂로 이동.
- 이후 q₂에서 다시 0을 입력하면 다시 q₁으로 돌아감 → 항상 짝수 개의 0을 유지.
q₂ → q₃ (1 입력, 수락 상태)
- 최소한 2개의 0을 입력한 후 1을 입력하면 q₃로 이동.
q₃ → q₃ (1 추가 입력 가능)
- 1을 입력하면 q₃에 머무름
- q₃에서는 추가적인 1을 계속 입력할 수 있음.

6. NFA의 특징

언어 L = { 0²ⁿ 1ᵐ | m, n ≥ 1 }에 맞게 설계됨.
NFA는 특정 상태에서 다시 돌아가는 전이(Loop-back Transition)를 활용하여 짝수 개의 0을 유지.
각각의 수락 상태(q₄)는 해당 문자열을 완성한 지점.
DFA와 달리, 상태 수를 줄일 수 있고 여러 개의 경로를 가질 수 있음.

NFA(비결정적 유한 자동자) 구성 및 상태 전이 다이어그램: 언어 L = { 0²ᵐ 1³ⁿ | m, n ≥ 1 }

1. 목표

주어진 언어는 다음과 같은 규칙을 따른다:
- 0이 반드시 짝수 개(2m개, m ≥ 1) 포함되어야 함.
- 1이 반드시 3의 배수(3n개, n ≥ 1) 포함되어야 함.
즉, 언어 L은 L = { 0²ᵐ 1³ⁿ | m, n ≥ 1 } 형태를 갖는다.

2. NFA의 상태 구성

q₀ (초기 상태): 최소 두 개의 0을 입력받아야 하므로 q₀에서 0을 입력받아 q₁으로 이동.
q₁: 첫 번째 0을 입력한 상태.
q₂: 두 번째 0을 입력하여 최소 조건을 충족한 상태.
q₃: 1을 입력하여 최소 조건을 만족하는 상태.
q₄: 두 번째 1을 입력한 상태.
q₅ (수락 상태): 세 번째 1을 입력하여 도달하는 상태.

3. 상태 전이 함수

현재 상태	입력	다음 상태
q₀	0	q₁
q₁	0	q₂
q₂	0	q₁ (짝수 개 유지)
q₂	1	q₃
q₃	1	q₄
q₄	1	q₅ (수락 상태)
q₅	1	q₃ (3의 배수 유지)

4. NFA 상태 전이 다이어그램

(q₀) --0--> (q₁) --0--> (q₂) --0--> (q₁)
                       |
                       v
                      (q₂) --1--> (q₃) --1--> (q₄) --1--> (q₅)
                                                            |
                                                            v
                                        (q₃) <--- (q₅) (3의 배수 유지)

5. NFA의 동작 방식

q₀ → q₁ → q₂ (최소 2개의 0 입력)
- q₀에서 0을 입력해야만 q₁으로 이동 가능.
- q₁에서 0을 입력하면 q₂로 이동.
- 이후 q₂에서 다시 0을 입력하면 다시 q₁으로 돌아감 → 항상 짝수 개의 0을 유지.
q₂ → q₃ → q₄ → q₅ (최소 3개의 1 입력)
- 최소한 2개의 0을 입력한 후 1을 입력하면 q₃로 이동.
- 이후 1을 입력하면 q₄, 다시 1을 입력하면 q₅로 이동 → 수락 상태.
- 이후 q₅에서 다시 1을 입력하면 q₃로 돌아가서 3의 배수 유지.

6. NFA의 특징

언어 L = { 0²ᵐ 1³ⁿ | m, n ≥ 1 }에 맞게 설계됨.
짝수 개의 0을 유지하기 위해 q₀ → q₁ → q₂ → q₁ 사이의 루프를 활용.
3의 배수 개의 1을 유지하기 위해 q₃ → q₄ → q₅ → q₃의 루프를 활용.
각각의 수락 상태(q₅)는 해당 문자열을 완성한 지점.
DFA와 달리, 상태 수를 줄일 수 있고 여러 개의 경로를 가질 수 있음.

NFA(비결정적 유한 자동자) 구성 및 상태 전이 다이어그램: 언어 L = { (01)²ⁿ | n ≥ 0 }

1. 목표

주어진 언어는 다음과 같은 규칙을 따른다:
- (01) 패턴이 짝수 번(2n번, n ≥ 0) 등장해야 함.
- 즉, 허용되는 문자열은 ε(빈 문자열), "0101", "01010101" 등과 같이 (01) 패턴이 2의 배수로 반복됨.
즉, 언어 L은 L = { (01)²ⁿ | n ≥ 0 } 형태를 갖는다.

2. NFA의 상태 구성

q₀ (초기 상태, 수락 상태): ε(빈 문자열)도 언어에 포함되므로 초기 상태에서 즉시 수락할 수 있어야 함.
q₁: 0을 입력하면 q₁으로 이동.
q₂: 1을 입력하면 q₂로 이동하여 (01) 패턴을 완성.
q₃: 추가적인 0을 입력하여 (01)을 다시 시작.
q₀ (루프): q₃에서 1을 입력하면 다시 q₀로 돌아가면서 (01) 패턴이 짝수 번 반복될 수 있도록 구성.

3. 상태 전이 함수

현재 상태	입력	다음 상태
q₀	ε	q₀ (빈 문자열 수락)
q₀	0	q₁
q₁	1	q₂
q₂	0	q₃
q₃	1	q₀ (짝수 번 반복 유지)

4. NFA 상태 전이 다이어그램

(q₀) --0--> (q₁) --1--> (q₂) --0--> (q₃) --1--> (q₀)
  |                                          |
  |------------------------------------------|
  (빈 문자열 수락)

5. NFA의 동작 방식

q₀ → q₁ → q₂ → q₃ → q₀ (짝수 번의 (01) 패턴 유지)
- q₀에서 0을 입력하면 q₁으로 이동.
- q₁에서 1을 입력하면 q₂로 이동.
- q₂에서 0을 입력하면 q₃로 이동.
- q₃에서 1을 입력하면 q₀으로 돌아가면서 짝수 번의 (01) 패턴을 반복할 수 있음.
빈 문자열(ε)도 허용됨 → 따라서 q₀이 초기 상태이면서 수락 상태.
(01)의 짝수 개 반복만 허용됨 → 만약 (01)이 홀수 번 등장하면 수락 상태에 도달하지 못하고 거부됨.

6. NFA의 특징

언어 L = { (01)²ⁿ | n ≥ 0 }에 맞게 설계됨.
NFA는 특정 상태에서 다시 돌아가는 전이(Loop-back Transition)를 활용하여 짝수 개의 (01) 패턴을 유지.
초기 상태(q₀)가 수락 상태이므로 빈 문자열(ε)도 포함됨.
각각의 수락 상태(q₀)는 해당 문자열을 완성한 지점.
DFA와 달리, 상태 수를 줄일 수 있고 여러 개의 경로를 가질 수 있음.

NFA(비결정적 유한 자동자) 구성 및 상태 전이 다이어그램: 언어 L = { 시작이 "100"인 모든 문자열 }

1. 목표

주어진 언어는 다음과 같은 규칙을 따른다:
- 문자열이 반드시 "100"으로 시작해야 함.
- "100" 이후에는 어떤 문자열이 와도 됨 (0과 1의 조합 가능).
즉, 언어 L은 L = { w | w의 접두사가 "100"인 모든 이진 문자열 } 형태를 갖는다.

2. NFA의 상태 구성

q₀ (초기 상태): 입력이 1로 시작해야 하므로 q₀에서 1을 입력받아 q₁으로 이동.
q₁: 0을 입력받아 q₂로 이동.
q₂: 또다시 0을 입력받아 q₃로 이동.
q₃ (수락 상태): "100"을 완성한 상태이며, 이후 어떤 입력(0 또는 1)이 와도 됨.

3. 상태 전이 함수

현재 상태	입력	다음 상태
q₀	1	q₁
q₁	0	q₂
q₂	0	q₃ (수락 상태)
q₃	0,1	q₃ (임의의 입력 허용)

4. NFA 상태 전이 다이어그램

(q₀) --1--> (q₁) --0--> (q₂) --0--> (q₃) --0,1--> (q₃)
                                    (수락 상태)

5. NFA의 동작 방식

q₀ → q₁ → q₂ → q₃ ("100" 패턴이 처음에 등장)
- q₀에서 1을 입력해야만 q₁으로 이동 가능.
- q₁에서 0을 입력하면 q₂로 이동.
- q₂에서 다시 0을 입력하면 q₃로 이동하여 "100"을 완성.
q₃에서 어떤 입력이 와도 계속 수락 상태 유지
- q₃에 도달하면 이후 모든 입력(0 또는 1)에 대해 q₃에서 머무를 수 있음.
- 즉, "100"을 접두사로 가지는 모든 문자열을 수락.

6. NFA의 특징

언어 L = { 시작이 "100"인 모든 문자열 }에 맞게 설계됨.
NFA는 특정 상태에서 다시 돌아가는 전이(Loop-back Transition)를 활용하여 "100" 이후의 어떤 문자열도 허용.
초기 상태(q₀)에서 "100" 패턴을 완성하기 전까지는 다른 입력을 허용하지 않음.
각각의 수락 상태(q₃)는 해당 문자열을 완성한 지점.
DFA와 달리, 상태 수를 줄일 수 있고 여러 개의 경로를 가질 수 있음.

NFA(비결정적 유한 자동자) 구성 및 상태 전이 다이어그램: 언어 L = { "000"으로 끝나는 모든 문자열 }

1. 목표

주어진 언어는 다음과 같은 규칙을 따른다:
- 문자열이 반드시 "000"으로 끝나야 함.
- "000" 앞에는 어떤 문자열이 와도 됨 (0과 1의 조합 가능).
- "000" 이후에는 추가적인 입력이 들어오면 자동으로 거부됨.

2. NFA의 상태 구성

q₀ (초기 상태): "000"을 감지하기 전의 상태로, 어떤 입력(0 또는 1)도 허용됨.
q₁: "000"의 첫 번째 0을 감지한 상태.
q₂: "000"의 두 번째 0을 감지한 상태.
q₃ (수락 상태): 세 번째 0을 입력받아 "000" 패턴을 완성한 상태.
- 여기서 추가적인 입력이 들어오면 자동으로 거부됨.

3. 상태 전이 함수

현재 상태	입력	다음 상태
q₀	0	q₀ (비결정적) 또는 q₁
q₀	1	q₀
q₁	0	q₂
q₁	1	q₀
q₂	0	q₃ (수락 상태)
q₂	1	q₀
q₃	(추가 입력 없음)	(자동 거부)

4. NFA 상태 전이 다이어그램

(q₀) --0--> (q₁) --0--> (q₂) --0--> (q₃) 
  |                                  |
 0,1                                0,1
  |                                  |
  v                                  v
(q₀)                                (q₃) (수락 상태, 이후 입력 허용)

q₀에서 1을 입력받으면 q₀에서 머무름 ("000"이 시작되지 않음).
q₀에서 0을 입력받으면 "000"이 시작될 가능성이 있으므로 q₁으로 이동하거나 q₀에 머물 수 있음 (비결정성).
이후 q₁에서 0을 입력하면 q₂, 다시 0을 입력하면 q₃로 이동하여 "000"을 완성.
q₃에서는 추가 입력이 불가능하며, 입력이 들어오면 자동으로 거부됨.
어디서든 1이 입력되면 다시 q₀으로 돌아가야 함 → 이는 "000"을 새로 감지해야 하기 때문.

5. NFA의 동작 방식

q₀ → q₁ → q₂ → q₃ ("000" 패턴이 감지되면 수락 상태 도달)
- q₀에서 0을 받으면 "000"을 찾기 위해 q₁으로 이동하거나 기존 상태를 유지 가능.
- q₁에서 0을 받으면 q₂, 다시 0을 받으면 q₃로 이동하여 "000"을 완성.
- "000" 이후 추가적인 입력이 들어오면 자동으로 거부됨.
q₀에서 1이 입력되면 "000"을 다시 찾아야 하므로 초기 상태로 리셋됨.

6. 비결정성(Nondeterminism)의 역할

q₀에서 0을 받을 때 두 가지 가능성이 존재:
- q₀에서 머물기: 중간에 있는 0을 무시하고 마지막 "000"만 감지하도록 함.
- q₁으로 이동: "000"이 시작될 가능성을 추적.
이러한 비결정성 덕분에 문자열 어디에서든 "000"이 마지막 세 개의 문자로 존재하는지를 감지 가능.

7. NFA의 특징

언어 L = { "000"으로 끝나는 모든 문자열 }에 맞게 설계됨.
비결정성을 이용하여 문자열의 마지막 세 개의 문자가 정확히 "000"인지 확인.
초기 상태(q₀)에서 "000" 패턴을 완성하기 전까지는 어떤 입력도 허용.
각각의 수락 상태(q₃)는 해당 문자열을 완성한 지점이며, 이후 입력이 들어오면 거부됨.
DFA와 달리, 상태 수를 줄일 수 있고 여러 개의 경로를 가질 수 있음.

✅ q₀에서 0을 받을 때 두 가지 전이가 존재하는 이유

1️⃣ q₀ → q₀ (0을 입력받았을 때 q₀로 돌아감)

이 경우는 "000"을 찾기 전까지 무작위로 입력을 받을 수 있도록 하기 위함이야.
즉, 문자열의 중간이나 앞부분에 있는 0은 무시하고, 마지막 세 개의 0만 감지해야 하므로 0을 받더라도 q₀에 머물 수 있는 선택지를 유지하는 것이야.

2️⃣ q₀ → q₁ (0을 입력받았을 때 q₁으로 이동)

이 경우는 "000" 패턴이 시작될 가능성을 감지하기 위한 전이야.
즉, 이전까지 입력된 문자열은 무시하고, 새로운 "000"을 찾기 시작하는 것이지.

➡️ 두 전이는 어떻게 구분되는가?

NFA의 핵심 특성 중 하나는 "비결정성"이야.
즉, 같은 입력(0)을 받았을 때 q₀에서 머물 수도 있고, q₁으로 이동할 수도 있음.
그러면 NFA는 모든 가능성을 동시에 계산하며 진행하는 방식으로 동작해.
따라서, 어떤 입력이 들어왔을 때 각 가능한 상태를 유지하면서 모든 경로를 시뮬레이션하게 돼.
- 한 경로에서는 q₀에 머물러서 "000"이 나타날 기회를 계속 찾고,
- 또 다른 경로에서는 q₁으로 이동해서 실제로 "000"을 만들기 시작하는 거야.

✅ 비결정성이 "000"을 찾는 데 어떻게 작용하는가?

이제 NFA가 어떻게 동작하는지 좀 더 직관적으로 설명해 볼게.

예제 1: 입력 문자열이 "100000"인 경우

q₀에서 1을 받으면, q₀에 그대로 머뭄 (q₀ → q₀).
q₀에서 0을 받으면, q₀에 남을 수도 있고, q₁으로 이동할 수도 있음.
q₁에서 0을 받으면 q₂로 이동.
q₂에서 0을 받으면 q₃로 이동 → "000"을 완성하여 수락 상태에 도달.
이후 추가적인 입력이 들어오면 자동 거부됨.

예제 2: 입력 문자열이 "1100010"인 경우

q₀에서 1을 받으면, q₀에 그대로 머뭄.
q₀에서 또 1을 받으면, 여전히 q₀.
q₀에서 0을 받으면 q₀에 남을 수도 있고, q₁으로 이동할 수도 있음.
q₁에서 0을 받으면 q₂로 이동.
q₂에서 0을 받으면 q₃로 이동 → "000"을 완성하여 수락 상태에 도달.
마지막 1이 추가 입력으로 들어오므로, 거부됨.

✅ 최종 요약

q₀에서 0을 받을 때 두 가지 선택(q₀ 또는 q₁으로 이동)이 존재하는 이유는 비결정성(Nondeterminism) 때문이야.
NFA는 모든 가능성을 동시에 계산하며 동작하기 때문에 "000"이 마지막에 등장하는 모든 경우를 추적할 수 있음.
q₀ → q₀ (0 입력 시 계속 머물기)
- 문자열의 초반이나 중간에 등장하는 0을 무시할 수 있도록 함.
q₀ → q₁ (0 입력 시 "000" 감지 시작)
- 새로운 "000" 패턴을 찾기 시작하는 역할.

NFA for Language L = { 문자열 안에 "101"이 포함되는 모든 문자열 }

1. 목표

주어진 언어는 다음과 같은 규칙을 따른다:
- 문자열 안에 반드시 "101"이라는 부분 문자열(substring)이 포함되어야 함.
- "101" 앞에는 어떤 문자열이 와도 됨 (0과 1의 조합 가능).
- "101" 뒤에도 어떤 문자열이 와도 됨 (0과 1의 조합 가능).

2. 상태 전이 테이블

현재 상태	입력	다음 상태
q₀	0,1	q₀
q₀	1	q₁
q₁	0	q₂
q₂	1	q₃ (수락 상태)
q₃	0,1	q₃ (임의의 입력 허용)

3. 상태 설명

q₀ (초기 상태): "101"을 찾기 전의 상태.
- 입력이 "1"이면 "101"이 시작될 가능성이 있으므로 q₁으로 이동.
- 입력이 "0"이면 여전히 "101"이 나타날 가능성이 없으므로 q₀에 남음.
q₁: "101"의 첫 번째 1을 감지한 상태.
- 입력이 "0"이면 "101"의 중간 단계로 q₂로 이동.
- 입력이 "1"이면 "101"이 시작되지 않았다고 간주하고 다시 q₀로 이동.
q₂: "101"의 두 번째 0을 감지한 상태.
- 입력이 "1"이면 "101"을 완성하여 q₃로 이동 → 수락 상태.
- 입력이 "0"이면 "101"이 시작되지 않았다고 간주하고 다시 q₀로 이동.
q₃ (수락 상태): "101"을 감지한 상태.
- "101"을 포함한 문자열은 이후 어떤 입력이 들어와도 수락됨.
- 따라서 이후 입력(0 또는 1)에 대해 항상 q₃ 상태를 유지.

4. NFA 상태 전이 다이어그램

(q₀) --1--> (q₁) --0--> (q₂) --1--> (q₃)
  |                                  |
 0,1                                0,1
  |                                  |
  v                                  v
(q₀)                                (q₃) (수락 상태, 이후 입력 허용)

q₀에서 0 또는 1을 입력받아도 여전히 q₀에 머물거나, 1을 입력받으면 q₁으로 전이할 수 있음.
"101"을 찾으면 q₃로 이동하며, 이후 입력은 어떤 값이든 q₃에 계속 머물러야 함.

5. NFA의 동작 방식

q₀ → q₁ → q₂ → q₃ ("101" 패턴이 감지되면 수락 상태 도달)
- q₀에서 1이 입력되면 "101"이 시작될 가능성이 있으므로 q₁으로 이동.
- q₁에서 0이 입력되면 q₂로 이동.
- q₂에서 1이 입력되면 "101"을 완성하여 q₃로 이동 → 수락 상태.
q₃에서는 추가 입력이 들어와도 계속 유지됨
- 즉, "101"을 포함한 문자열은 이후 어떤 입력을 받아도 수락됨.

6. NFA의 특징

비결정성을 활용하여 문자열 안에서 "101"이 포함되었는지를 감지.
"101"이 완성된 이후(q₃)에는 어떤 입력이 들어와도 자동으로 수락됨.
q₀에서 "101" 패턴을 완성하기 전까지는 어떤 입력도 허용.
각각의 수락 상태(q₃)는 해당 문자열을 완성한 지점.
DFA와 달리, 상태 수를 줄일 수 있고 여러 개의 경로를 가질 수 있음.

NFA for Language L = { 마지막 두 비트가 같은 모든 문자열 }

1. 목표

주어진 언어는 다음과 같은 규칙을 따른다:
- 마지막 두 비트가 동일해야 함.
- "00" 또는 "11"로 끝나는 문자열만 포함됨.
- 그 외의 비트는 어떠한 조합이든 가능.

2. 상태 전이 테이블

현재 상태	입력	다음 상태
q₀	0,1	q₀
q₀	0	q₁
q₀	1	q₃
q₁	0	q₂ (수락 상태)
q₃	1	q₂ (수락 상태)

3. 상태 설명

q₀ (초기 상태): 아직 "00" 또는 "11" 패턴이 감지되지 않은 상태.
- 입력값이 0이면 "00" 패턴을 감지할 가능성이 있으므로 q₁으로 이동.
- 입력값이 1이면 "11" 패턴을 감지할 가능성이 있으므로 q₃으로 이동.
- 그 외에는 계속 q₀에 머물면서 입력을 기다림.
q₁: "00"의 첫 번째 0을 감지한 상태.
- 입력값이 0이면 "00" 패턴이 완성되어 q₂(수락 상태)로 이동.
q₃: "11"의 첫 번째 1을 감지한 상태.
- 입력값이 1이면 "11" 패턴이 완성되어 q₂(수락 상태)로 이동.
q₂ (수락 상태): "00" 또는 "11"을 감지한 상태.
- 이후에는 어떤 입력이 와도 수락됨.

4. NFA 상태 전이 다이어그램

   ----1--> (q₃) --1-----
  |                      |
  |                      v
(q₀) --0--> (q₁) --0--> (q₂) (수락 상태)
  |                                  
 0,1                                
  |                                  
  v                                  
(q₀)

q₀에서 0이 입력되면 q₁으로 이동 (마지막이 "00"이 될 가능성 존재).
q₀에서 1이 입력되면 q₃으로 이동 (마지막이 "11"이 될 가능성 존재).
q₁에서 다시 0이 입력되면 q₂(수락 상태)로 이동.
q₃에서 다시 1이 입력되면 q₂(수락 상태)로 이동.
q₂에서는 이후 어떤 입력이 들어와도 계속 유지되며 문자열을 수락함.

5. NFA의 동작 방식

q₀ → q₁ → q₂ ("00" 패턴이 감지되면 수락 상태 도달)
q₀ → q₃ → q₂ ("11" 패턴이 감지되면 수락 상태 도달)
q₂에서는 추가 입력이 들어와도 계속 유지됨
- 즉, "00" 또는 "11"을 포함한 문자열은 이후 어떤 입력을 받아도 수락됨.

6. 비결정성(Nondeterminism)의 역할

q₀에서 0을 받을 때 q₀에 남을 수도 있고, q₁으로 이동할 수도 있음:
- "00"이 나오기 전까지 무작위로 입력을 받을 수 있도록 하기 위해.
q₀에서 1을 받을 때 q₀에 남을 수도 있고, q₃으로 이동할 수도 있음:
- "11"이 나오기 전까지 무작위로 입력을 받을 수 있도록 하기 위해.

NFA for Language L = { 네 번째 비트가 1인 모든 문자열 }

1. 목표

주어진 언어는 다음과 같은 규칙을 따른다:
- 문자열의 네 번째 비트가 반드시 '1'이어야 함.
- 앞의 세 비트(1~3번째 비트)는 0 또는 1이 올 수 있음.
- 네 번째 비트 이후에는 어떤 비트(0 또는 1)라도 올 수 있음.

2. 상태 전이 테이블

현재 상태	입력	다음 상태
q₀	0,1	q₁
q₁	0,1	q₂
q₂	0,1	q₃
q₃	1	q₄ (수락 상태)
q₄	0,1	q₄ (임의의 입력 허용)

3. 상태 설명

q₀ (초기 상태): 아직 네 번째 비트에 도달하지 않은 상태.
- 첫 번째 비트는 0 또는 1이 올 수 있으므로 q₁으로 이동.
q₁: 두 번째 비트를 읽은 상태.
- 입력값이 0 또는 1일 수 있으므로 q₂로 이동.
q₂: 세 번째 비트를 읽은 상태.
- 입력값이 0 또는 1일 수 있으므로 q₃로 이동.
q₃: 네 번째 비트가 입력될 차례.
- 반드시 1이 와야 하므로 q₄(수락 상태)로 이동.
q₄ (수락 상태): 네 번째 비트가 1이라는 조건을 만족한 상태.
- 이후에는 어떤 입력이든 허용하며 계속 q₄에 머무름.

4. NFA 상태 전이 다이어그램

(q₀) --0,1--> (q₁) --0,1--> (q₂) --0,1--> (q₃) --1--> (q₄) --0,1--> (q₄) (임의의 입력 허용)
  |                                  
 0,1                                
  |                                  
  v                                  
(q₀)

q₀에서 처음 세 개의 비트(0 또는 1)를 읽을 수 있도록 상태를 유지.
q₃에서 반드시 1이 입력되어야 q₄(수락 상태)로 이동 가능.
q₄에서는 추가 입력이 들어와도 계속 유지되며 문자열을 수락함.

5. NFA의 동작 방식

q₀ → q₁ → q₂ → q₃ → q₄ ("네 번째 비트가 1이면 수락 상태 도달")
- 처음 세 개의 비트(0 또는 1)는 자유롭게 입력 가능.
- 네 번째 비트에서 반드시 1이 입력되어야 q₄(수락 상태)로 이동.
q₄에서는 추가 입력이 들어와도 계속 유지됨
- 즉, 네 번째 비트가 1인 문자열은 이후 어떤 입력을 받아도 수락됨.

6. NFA의 특징

비결정성을 활용하여 문자열 안에서 네 번째 비트가 1인지 감지.
네 번째 비트가 1인지 확인한 후(q₄)에는 어떤 입력이 들어와도 자동으로 수락됨.
q₀에서 네 번째 비트가 올 때까지는 어떤 입력도 허용.
q₄에서 이후 입력을 받아도 여전히 수락 상태 유지.

NFA for Language L = { 우측에서 다섯 번째 비트가 1인 모든 문자열 }

1. 목표

주어진 언어는 다음과 같은 규칙을 따른다:
- 우측에서 5번째 비트가 반드시 '1'이어야 함.
- 그 이전(더 높은 자리)의 비트는 어떤 값(0 또는 1)이라도 가능.
- 우측의 네 개의 비트(1~4번째 비트)도 어떤 값(0 또는 1)이라도 가능.

2. 상태 전이 테이블

현재 상태	입력	다음 상태
q₀	0,1	q₀
q₀	1	q₁
q₁	0,1	q₂
q₂	0,1	q₃
q₃	0,1	q₄
q₄	0,1	q₅ (수락 상태)

3. 상태 설명

q₀ (초기 상태): 아직 우측에서 5번째 비트에 도달하지 않은 상태.
- 입력이 0 또는 1일 경우, q₀에 머물거나 1이 입력되면 q₁으로 이동.
q₁: 우측에서 5번째 비트를 기록하는 중.
- 입력값이 0 또는 1일 수 있으므로 q₂로 이동.
q₂: 우측에서 4번째 비트를 기록하는 중.
- 입력값이 0 또는 1일 수 있으므로 q₃로 이동.
q₃: 우측에서 3번째 비트를 기록하는 중.
- 입력값이 0 또는 1일 수 있으므로 q₄로 이동.
q₄: 우측에서 2번째 비트를 기록하는 중.
- 입력값이 0 또는 1일 수 있으므로 q₅(수락 상태)로 이동.
q₅ (수락 상태): 우측에서 5번째 비트가 1이라는 조건을 만족한 상태.

4. NFA 상태 전이 다이어그램

(q₀) --1--> (q₁) --0,1--> (q₂) --0,1--> (q₃) --0,1--> (q₄) --0,1--> (q₅)
  |                                  
 0,1                                
  |                                  
  v                                  
(q₀)(임의의 입력 허용)

q₀에서 처음 1이 입력될 때 q₁으로 이동하며, 이는 우측에서 5번째 비트가 1이 되는 역할.
이후의 네 개의 비트(0 또는 1)는 자유롭게 입력 가능하며 q₅(수락 상태)에 도달하게 됨.

5. NFA의 동작 방식

q₀ → q₁ → q₂ → q₃ → q₄ → q₅ ("우측에서 다섯 번째 비트가 1이면 수락 상태 도달")
- 처음 네 개의 비트(0 또는 1)는 자유롭게 입력 가능.
- 네 번째 비트에서 반드시 1이 입력되어야 q₁로 이동.

6. NFA의 특징

비결정성을 활용하여 문자열 안에서 우측에서 다섯 번째 비트가 1인지 감지.
q₀에서 다섯 번째 비트가 올 때까지는 어떤 입력도 허용.

NFA for Language L = { 시작과 끝이 같은 문자로 이루어진 문자열 }

1. 목표

주어진 언어는 다음과 같은 규칙을 따른다:
- 문자열의 첫 번째 문자와 마지막 문자가 같아야 한다.
- 중간의 문자들은 어떤 값(0 또는 1)이라도 가능하다.

2. 상태 전이 테이블

현재 상태	입력	다음 상태
q₀	0	q₁
q₀	0,1	q₂ (수락 상태)
q₀	1	q₃
q₁	0,1	q₁
q₁	0	q₂ (수락 상태)
q₃	0,1	q₃
q₃	1	q₂ (수락 상태)

3. 상태 설명

q₀ (초기 상태): 아직 문자열을 시작하지 않은 상태.
- 입력이 0이면 q₁으로 이동 (첫 번째 문자가 0).
- 입력이 1이면 q₃으로 이동 (첫 번째 문자가 1).
- 입력이 0 또는 1인 경우 바로 q₂(수락 상태)로 이동할 수도 있음 (한 글자짜리 문자열 처리).
q₁: 첫 번째 문자가 0인 경우의 상태.
- 중간에 어떤 문자(0 또는 1)라도 허용됨.
- 마지막 입력이 0이면 q₂(수락 상태)로 이동.
q₃: 첫 번째 문자가 1인 경우의 상태.
- 중간에 어떤 문자(0 또는 1)라도 허용됨.
- 마지막 입력이 1이면 q₂(수락 상태)로 이동.
q₂ (수락 상태): 첫 번째 문자와 마지막 문자가 같은 경우 도달하는 상태.

4. NFA 상태 전이 다이어그램

(q₀) --0--> (q₁) --(0,1)--> (q₁) --0--> (q₂) (수락 상태)
  |                                    
  |                                    
  |--1--> (q₃) --(0,1)--> (q₃) --1--> (q₂) (수락 상태)
  |
  |--(0,1)--> (q₂) (한 글자짜리 문자열 즉시 수락)

q₀에서 0으로 시작하면 q₁, 1으로 시작하면 q₃로 이동.
q₁과 q₃에서는 중간 입력이 자유롭지만, 마지막 입력이 첫 입력과 같아야 q₂(수락 상태)로 이동.
한 글자짜리 문자열 0 또는 1도 즉시 q₂(수락 상태)로 이동하여 수락됨.

5. NFA의 동작 방식

q₀ → q₁ → (중간 값) → q₂ ("0"으로 시작하고 "0"으로 끝나면 수락 상태 도달)
q₀ → q₃ → (중간 값) → q₂ ("1"으로 시작하고 "1"으로 끝나면 수락 상태 도달)
- 첫 문자와 마지막 문자가 같으면 수락 상태로 이동.
- 중간 문자들은 어떤 값이든 허용.

6. NFA의 특징

비결정성을 활용하여 첫 번째 문자와 마지막 문자가 같은지 확인.
q₀에서 처음 문자가 0인지 1인지에 따라 다른 경로로 진행.
q₁과 q₃에서는 중간 입력이 자유롭지만, 마지막 입력이 첫 입력과 같아야 수락됨.

NFA for Language L = { 시작과 끝이 다른 문자로 이루어진 문자열 }

1. 목표

주어진 언어는 다음과 같은 규칙을 따른다:
- 문자열의 첫 번째 문자와 마지막 문자가 달라야 한다.
- 중간의 문자들은 어떤 값(0 또는 1)이라도 가능하다.

2. 상태 전이 테이블

현재 상태	입력	다음 상태
q₀	0	q₁
q₀	1	q₃
q₁	0,1	q₁
q₁	1	q₂ (수락 상태)
q₃	0,1	q₃
q₃	0	q₂ (수락 상태)

3. 상태 설명

q₀ (초기 상태): 문자열을 시작하기 전의 상태.
- 입력이 0이면 q₁으로 이동 (첫 번째 문자가 0).
- 입력이 1이면 q₃으로 이동 (첫 번째 문자가 1).
q₁: 첫 번째 문자가 0인 경우의 상태.
- 중간에 어떤 문자(0 또는 1)라도 허용됨.
- 마지막 입력이 1이면 q₂(수락 상태)로 이동.
q₃: 첫 번째 문자가 1인 경우의 상태.
- 중간에 어떤 문자(0 또는 1)라도 허용됨.
- 마지막 입력이 0이면 q₂(수락 상태)로 이동.
q₂ (수락 상태): 첫 번째 문자와 마지막 문자가 다른 경우 도달하는 상태.

4. NFA 상태 전이 다이어그램

(q₀) --0--> (q₁) --(0,1)--> (q₁) --1--> (q₂) (수락 상태)
  |                                    
  |                                    
  |--1--> (q₃) --(0,1)--> (q₃) --0--> (q₂) (수락 상태)

q₀에서 0으로 시작하면 q₁, 1으로 시작하면 q₃로 이동.
q₁과 q₃에서는 중간 입력(0 또는 1)이 자유롭지만, 마지막 입력이 처음과 달라야 q₂(수락 상태)로 이동.

5. NFA의 동작 방식

q₀ → q₁ → (중간 값) → q₂ ("0"으로 시작하고 "1"으로 끝나면 수락 상태 도달)
q₀ → q₃ → (중간 값) → q₂ ("1"으로 시작하고 "0"으로 끝나면 수락 상태 도달)
- 첫 문자와 마지막 문자가 다르면 수락 상태로 이동.
- 중간 문자들은 어떤 값이든 허용.

6. NFA의 특징

비결정성을 활용하여 첫 번째 문자와 마지막 문자가 다른지 확인.
q₀에서 처음 문자가 0인지 1인지에 따라 다른 경로로 진행.
q₁과 q₃에서는 중간 입력이 자유롭지만, 마지막 입력이 첫 입력과 달라야 수락됨.

'강의 > Theory of Computation' 카테고리의 다른 글

Construction of Minimal DFA Examples (0)	2025.02.02
Construct Minimal DFA (0)	2025.02.01
TOC Fundamentals, Regular Languages (0)	2025.01.28
Introduction (0)	2025.01.26

현재글Non-Deterministic PushDown Automata (NFA)

studylida

네트워크, OSI 참조 모델, cpp, 어드레싱, 마이크로서비스, INDA, 주식, 프로그래밍, 작성 규칙, 리얼티인컴, 로드 밸런서, 연결, SPTL, 게시글 작성 규칙, fill_n, 인터페이스, API 게이트웨이, MAC 주소 필터링, IEMG, 모놀리,

Today :
Yesterday :

일	월	화	수	목	금	토
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28

Non-Deterministic PushDown Automata (NFA)

요약 및 정리: 비결정적 유한 자동자(NFA, Non-deterministic Finite Automaton)

1. NFA의 개념

2. NFA의 정의

3. DFA와 NFA의 차이점

4. NFA의 동작 방식

5. NFA 예제

예제 1: 입력이 0 또는 1일 때, 특정 상태로 이동하는 NFA

예제 2: "01"을 포함하는 문자열을 인식하는 NFA

6. NFA의 수락 조건

7. NFA의 특징

8. NFA를 DFA로 변환 (Subset Construction Algorithm)

9. DFA와 NFA의 계산 능력 비교

10. NFA의 활용 사례

비결정적 유한 자동자(NFA)의 언어(Language of NFA) 요약 및 정리

1. NFA의 언어란?

2. NFA의 언어 개념

3. NFA의 언어와 DFA의 언어

4. NFA의 특징

5. NFA의 수락 및 거부 과정

(1) 수락(Acceptance) 과정

(2) 거부(Reject) 과정

6. NFA의 실행 및 결정 과정

NFA(비결정적 유한 자동자) 구성 및 상태 전이 다이어그램: 허용된 문자열 {ε, "10", "01"}

1. 목표

2. NFA의 상태 구성

3. 상태 전이 함수

4. NFA 상태 전이 다이어그램

5. NFA의 동작 방식

6. NFA의 특징

NFA(비결정적 유한 자동자) 구성 및 상태 전이 다이어그램: 언어 L = { 0ⁿ 1 0ᵐ | m, n ≥ 1 }

1. 목표

2. NFA의 상태 구성

3. 상태 전이 함수

4. NFA 상태 전이 다이어그램

5. NFA의 동작 방식

6. NFA의 특징

7. ε-전이를 사용하지 않도록 수정된 NFA

1. 수정된 NFA의 상태 전이

2. 수정된 NFA의 상태 전이 다이어그램

3. 수정된 NFA의 동작 방식

4. ε-전이 없이 구성할 경우의 장점

NFA(비결정적 유한 자동자) 구성 및 상태 전이 다이어그램: 언어 L = { 0²ⁿ 1ᵐ | m, n ≥ 1 }

1. 목표

2. NFA의 상태 구성

3. 상태 전이 함수

4. NFA 상태 전이 다이어그램

5. NFA의 동작 방식

6. NFA의 특징

NFA(비결정적 유한 자동자) 구성 및 상태 전이 다이어그램: 언어 L = { 0²ᵐ 1³ⁿ | m, n ≥ 1 }

1. 목표

2. NFA의 상태 구성

3. 상태 전이 함수

4. NFA 상태 전이 다이어그램

5. NFA의 동작 방식

6. NFA의 특징

NFA(비결정적 유한 자동자) 구성 및 상태 전이 다이어그램: 언어 L = { (01)²ⁿ | n ≥ 0 }

1. 목표

2. NFA의 상태 구성

3. 상태 전이 함수

4. NFA 상태 전이 다이어그램

5. NFA의 동작 방식

6. NFA의 특징

NFA(비결정적 유한 자동자) 구성 및 상태 전이 다이어그램: 언어 L = { 시작이 "100"인 모든 문자열 }

1. 목표

2. NFA의 상태 구성

3. 상태 전이 함수

4. NFA 상태 전이 다이어그램

5. NFA의 동작 방식

6. NFA의 특징

NFA(비결정적 유한 자동자) 구성 및 상태 전이 다이어그램: 언어 L = { "000"으로 끝나는 모든 문자열 }

1. 목표

2. NFA의 상태 구성

3. 상태 전이 함수

4. NFA 상태 전이 다이어그램

5. NFA의 동작 방식

6. 비결정성(Nondeterminism)의 역할

7. NFA의 특징

✅ q₀에서 0을 받을 때 두 가지 전이가 존재하는 이유

1️⃣ q₀ → q₀ (0을 입력받았을 때 q₀로 돌아감)

예제 1: 입력이 `0` 또는 `1`일 때, 특정 상태로 이동하는 NFA