비결정론적 유한 상태 기계

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. NFA의 동작 방식 (직관적 설명)
4. DFA와의 동등성
5. ε-이동을 갖는 NFA (NFA-ε)
- 5.1. ε-폐쇄 (ε-closure)
- 5.2. NFA-ε와 NFA의 동등성
6. 확장 NFA (GNFA)
7. 닫힘 성질 (Closure Properties)
8. 구현
9. 복잡도
10. 응용
참조

1. 개요

비결정적 유한 상태 기계(NFA)는 유한한 상태, 입력 문자, 전이 함수, 초기 상태, 수용 상태로 구성되며, 입력 문자열을 처리할 때 여러 상태로 동시에 전이할 수 있는 유한 상태 기계의 한 종류이다. NFA는 입력에 따라 비결정적으로 다음 상태를 선택하며, 최종 상태에 도달할 수 있는 경우 해당 문자열을 수용한다. NFA는 결정적 유한 상태 기계(DFA)와 동등하며, NFA-ε, 확장 NFA(GNFA) 등 다양한 형태로 확장될 수 있다. NFA가 인식하는 언어는 정규 언어에 해당하며, 합집합, 교집합, 연결, 부정, 클레이니 스타 연산에 대해 닫혀 있다. NFA는 DFA로 변환하거나, 상태 집합을 유지하는 등의 방법으로 구현할 수 있으며, 공집합 문제, 전체성, 포함 문제 등과 관련된 다양한 복잡도를 가진다. NFA는 DFA보다 구성이 용이하며, 정규 언어의 폐포 성질을 증명하는 데 유용하게 사용된다.

더 읽어볼만한 페이지

유한 상태 기계 - 정규 언어
정규 언어는 주어진 알파벳으로 구성된 문자열 집합으로, 클레이니 스타, 합집합, 문자열 연결 연산을 통해 확장되며, 정규 표현식, 유한 상태 기계 등으로 표현 가능하다.
유한 상태 기계 - Lex
Lex는 마이크 레스크와 에릭 슈미트가 개발한 어휘 분석기 생성기로, 정규 표현식을 기반으로 입력 텍스트를 분석하여 토큰을 식별하고 컴파일러 개발 등에 활용된다.
언어학에 관한 - 세례명
세례명은 기독교에서 세례를 받을 때 받는 새로운 이름으로, 예수 그리스도 안에서 새롭게 태어남을 의미하며, 성경 속 인물들의 이름 변화에서 유래하여 중세 이후 유럽에서 일반적인 이름 형태로 정착되었고, 수호성인의 이름에서 따와 이름 축일로 기념되기도 한다.
언어학에 관한 - 개명
개명은 개인이나 법인이 이름을 바꾸는 행위로, 결혼, 이혼, 이민, 종교 개종, 성 정체성 확인, 사회적 이미지 개선, 범죄 회피 등 여러 이유로 행해지며, 절차는 국가별로 다르지만 법적 제약과 고려 사항이 따른다.

비결정론적 유한 상태 기계

2. 정의

비결정적 유한 오토마톤(NFA)은 $(S, \Sigma, T, s_0, A)$ 의 5가지 요소로 구성되며, 각 요소는 다음과 같은 성질을 가진다.

상태의 유한 집합( $S$ )
입력 문자의 유한 집합( $\Sigma$ )
전이 함수( $T:S \times (\Sigma \cup {\varepsilon}) \rarr P(S)$ )
상태 $s_0$ 를 특히 "초기(또는 시작) 상태"로 구분( $s_0 \in S$ )
상태의 집합 $A$ 를 특히 "수용(또는 종료) 상태"로 구분( $A \subseteq S$ )

여기서

P(S)

는

S

의 멱집합이며,

\varepsilon

는 빈 문자열이며,

\Sigma

는 입력 문자군이다.

\mathbf{M}

이

\mathbf{M} = (S, \Sigma, T, s_0, A)

로 구성된 NFA이고,

X

가

\Sigma

에 포함된 문자로 구성된 문자열이라고 하자.

\mathbf{M}

이 문자열

X

를 수용하는 것은, 다음 조건이 성립하는 경우이다. 우선,

X

를

x_1, x_2 \cdots x_n, x_i \in (\Sigma \cup {\varepsilon})

로 나타낼 때, 이를 입력받은

\mathbf{M}

이 취하는 상태 전이가

r_0, r_1, \cdots, r_n, r_i \in S

와 같을 때, 다음 조건이 성립한다.

1.

r_0 = s_0

2.

r_i \in T(r_{i-1}, x_i) \text{ for } i = 1, \cdots, n

3.

r_n \in A

머신은 초기 상태

s_0

에서 시작하여 입력 문자열을 읽는다. 오토마톤은 전이 함수

T

에 현재 상태와 입력 문자(또는 빈 문자)를 주어 다음에 전이해야 할 상태를 얻는다. 그러나 NFA의 다음 상태는 현재 입력 이벤트만으로 결정되는 것이 아니라, 그 이후의 임의 개수의 입력 이벤트(문자열)에도 영향을 받으며, NFA가 영향을 받는 입력 이벤트가 계속되는 한, 다음 전이 대상을 결정할 수 없다. 오토마톤이 읽기를 종료했을 때 수용 상태에 있으면, NFA는 해당 입력 문자열을 수용했다고 말할 수 있다. 그렇지 않으면 해당 입력 문자열은 거부된 것으로 간주된다.

어떤 NFA가 수용하는 문자열 전체의 집합이 NFA가 수용하는 언어이다. 이 언어는 정규 언어의 범위와 일치한다.

2. 1. 구성 요소

비결정론적 유한 상태 기계(NFA)는 5-튜플

(Q, \Sigma, \Delta, q_0, F)

로 정의되며, 다음과 같은 구성 요소로 이루어진다.

Q: 가능한 모든 상태의 유한 집합
Σ: 입력 기호의 유한 집합
Δ: 전이 함수로, $Q\times\Sigma \rightarrow P(Q)$ 와 같이 정의된다. 여기서 $P(Q)$ 는 $Q$ 의 멱집합이다.
$q_0$ : 초기 상태로, $q_0 \in Q$ 를 만족한다.
F: 최종 상태 (또는 수용 상태)의 집합으로, $F \subseteq Q$ 를 만족한다.

2. 2. NFA가 인식하는 언어

NFA가 인지하는 언어는 해당 NFA가 수용하는 모든 문자열의 집합으로,

L(M)

으로 표기한다.^[16]^[3]

문자열

w = a_1 a_2 ... a_n

이 NFA

M = (Q, \Sigma, \Delta, q_0, F)

에 의해 수용된다는 것은, 초기 상태

q_0

에서 시작하여

w

의 각 기호를 따라 전이 함수

\Delta

에 의해 정의된 상태 변화를 거쳐 최종 상태(

F

) 중 하나에 도달할 수 있음을 의미한다.^[16]^[3]

이는 다음과 같이 형식적으로 정의할 수 있다.

$Q$ 에 속한 상태 $r_0, r_1, ..., r_n$ 이 존재하여 다음을 만족한다.
$r_0 = q_0$ (초기 상태에서 시작)
$r_{i+1} \in \Delta (r_i, a_{i+1})$ , ( $i = 0, \ldots, n-1$ ) (전이 함수에 따른 상태 변화)
$r_n \in F$ (최종 상태 중 하나에 도달)

M

이

w

를 수용하려면 가능한 모든 상태의 수열이 최종 상태로 끝날 필요는 없으며, 가능한 상태의 수열 중 하나라도 최종 상태로 끝나면 충분하다.^[16] 만약

q_0

에서 출발해서

w

를 따라

F

에 속한 상태로 갈 방법이 전혀 없다면 NFA는 해당 문자열을 수용하지 않는다.^[16]^[3]

다른 정의로는,

\Delta^*(q_0, w) \cap F \not = \emptyset

라는 조건으로 표현할 수 있다. 여기서

\Delta^*: Q \times \Sigma^* \rightarrow P(Q)

는 다음과 같이 재귀적으로 정의된다.^[15]^[18]

$\Delta^*(r, \epsilon) = \{r\}$ ( $\epsilon$ 은 빈 문자열)
모든 $x \in \Sigma^*, a \in \Sigma$ 에 대해 $\Delta^*(r, xa)= \bigcup_{r' \in \Delta^*(r, x)} \Delta(r', a)$ .

즉,

\Delta^*(r, x)

는 상태

r

에서 출발해서 문자열

x

를 읽고 도달할 수 있는 모든 상태의 집합이다.

q_0

에서 출발해서 문자열

w

를 따라

F

에 속한 상태 중 하나에 도달할 수 있다면, 문자열

w

를 수용한다.^[15]^[18]

NFA가 수용하는 문자열 전체의 집합이 NFA가 인식하는 언어이며, 이 언어는 정규 언어의 범위와 일치한다.

2. 3. 초기 상태에 대한 참고 사항

NFA는 단일 초기 상태를 가지는 것이 일반적이지만, 여러 개의 초기 상태를 가지도록 정의하는 경우도 있다. 이렇게 하면 표기가 편리해지는 경우가 있다. 여러 초기 상태를 가진 NFA는 단일 초기 상태를 가진 동등한 NFA로 쉽게 변환할 수 있다.

3. NFA의 동작 방식 (직관적 설명)

NFA는 입력 문자열을 처리할 때, 매 단계마다 가능한 다음 상태 중 하나를 "비결정적"으로 선택한다.^[3] 여러 개의 다음 상태가 가능한 경우, NFA는 스스로를 "복제"하여 각 복사본이 서로 다른 가능한 상태로 진입하는 방식으로 동작한다고 볼 수 있다.^[3] 만약 전이가 적용되지 않으면 현재 복사본은 막다른 골목에 있으며 "사멸"한다. 입력 문자열을 모두 처리한 후, 복사본 중 하나라도 최종 상태에 도달하면 해당 문자열을 수용한다.^[3] 반면, 모든 복사본이 최종 상태에 도달하지 못하면 해당 문자열은 거부된다.

''M''의 상태 도표. 상태 ''p''에서 입력 1을 받으면 ''p'' 또는 ''q''로 갈 수 있기 때문에 비결정론적이다.

입력 “1011”을 받았을 때 ''M''의 가능한 모든 작동.
호 첨자: 입력 기호, 노드 첨자: 상태, : 초기 상태, : 최종 상태.

예를 들어, 기계

M

은 {0, 1} 위의 입력을 받아들여 입력이 1로 끝나는지 판정한다.

M = (\{p, q\}, \{0, 1\}, \Delta, p, \{q\})

이고, 전이 함수

\Delta

는 상태 전이 표와 같이 정의된다.

	0	1
$p$	$\{p\}$	$\{p,q\}$
$q$	$\emptyset$	$\emptyset$

$\Delta(p,1)$ 은 하나보다 많은 상태를 포함하므로, $M$ 은 비결정론적이다. $M$ 의 언어는 정규 표현식 (0|1)*1에 대응하는 정규 언어이다.

입력 “1011”을 받았을 때, 상태의 수열 중 하나가 조건을 만족시키므로 $M$ 은 이 문자열을 수용한다. 다른 수열이 실패하는 것은 상관없다.

$M$ 은 “10”을 수용하지 않는데, 마지막 기호인 0을 읽고 유일한 최종 상태인 $q$ 에 도달하는 것은 불가능하기 때문이다. 첫 기호인 1을 읽으면 상태 $q$ 에 도달하게 되지만, 이는 “10”이 아니라 “1”이 수용된다는 의미이다.

4. DFA와의 동등성

NFA는 결정적 유한 상태 기계(DFA)의 특수한 경우로 볼 수 있으므로, DFA가 인식할 수 있는 모든 형식 언어는 NFA로도 인식 가능하다.^[10] 반대로, 임의의 NFA에 대해 동일한 언어를 수용하는 DFA가 존재한다.^[10] 이는 멱집합 구성(부분 집합 구성법)을 통해 DFA를 구성할 수 있기 때문이다.^[10]

이러한 동등성은 NFA가 DFA보다 더 강력한 기능을 가지지 않음을 보여준다. NFA는 구성이 더 쉬울 수 있지만, DFA로 변환하여 효율적으로 실행할 수 있다. 그러나 NFA의 상태 수가 ''n''개일 때, 변환된 DFA는 최대 2^''n''개의 상태를 가질 수 있어, 큰 NFA의 경우 변환이 비효율적일 수 있다.^[10] NFA를 DFA로 변환하는 방법에는 부분 집합 구성법이 사용되지만, 최악의 경우 상태 수가 지수 함수적으로 증가하는 문제가 발생할 수 있다.^[10]

5. ε-이동을 갖는 NFA (NFA-ε)

ε-이동을 갖는 비결정적 유한 오토마톤(NFA-ε)은 NFA를 더욱 일반화한 것이다. 이러한 종류의 오토마톤에서, 전이 함수는 또한 빈 문자열 ε에 대해서도 정의된다. 입력 기호를 소비하지 않는 전이를 ε-전이라고 하며, 상태 다이어그램에서 "ε"로 표시된 화살표로 표현한다. ε-전이는 현재 상태를 정확히 알 수 없는 시스템을 모델링하는 편리한 방법을 제공한다. 즉, 어떤 시스템을 모델링하고 있고 (일부 입력 문자열을 처리한 후) 현재 상태가 q 또는 q'인지 명확하지 않은 경우, 이 두 상태 사이에 ε-전이를 추가하여 오토마톤을 동시에 두 상태에 놓을 수 있다.

''NFA-ε''는 다음과 같은 5-튜플 $(Q, \Sigma, \delta, q_0, F)$ 로 공식적으로 표현된다.

유한한 집합의 상태 $Q$
입력 기호의 유한한 집합으로 알파벳 $\Sigma$ 라고 부른다.
전이 함수 $\delta : Q \times (\Sigma \cup \{\epsilon\}) \rightarrow \mathcal{P}(Q)$
''초기'' (또는 ''시작'' 상태) 상태 $q_0 \in Q$
''수락'' (또는 ''최종'') ''상태''로 구분되는 상태 집합 $F \subseteq Q$ .

여기서

\mathcal{P}(Q)

는

Q

의 멱집합을 나타내며,

\epsilon

는 빈 문자열을 나타낸다.

### ε-폐쇄 (ε-closure)

상태 q의 ε-폐쇄는 ε-이동만을 통해 q에서 도달 가능한 모든 상태의 집합을 의미한다. 상태 집합 P의 ε-폐쇄는 P의 각 상태에서 ε-이동만을 통해 도달 가능한 모든 상태의 집합이다.

상태 q ∈ Q 에 대해, E(q)는 전이 함수 δ에서 ε-전이를 따라 q로부터 도달 가능한 상태 집합을 나타낸다. 즉, p ∈ E(q)는 다음과 같은 상태 시퀀스 q₁, ..., q_k 가 존재할 경우 성립한다.

q₁ = q
각 1 ≤ i < k 에 대해 q_i+1 ∈ δ(q_i, ε)
q_k = p

E(q)는 q의 ε-폐쇄라고 알려져 있다.

NFA의 상태 집합 P의 ε-폐쇄는 ε-전이를 따라 P의 임의의 상태로부터 도달 가능한 상태 집합으로 정의된다. 공식적으로, P ⊆ Q 에 대해, E(P) = ∪_q∈P E(q)로 정의한다.

### NFA-ε와 NFA의 동등성

NFA-ε는 NFA와 동등하다. NFA는 NFA-ε의 특수한 경우이므로, 모든 NFA-ε에 대해 동등한 NFA가 존재함을 보이면 된다.

엡실론 이동(ε-이동)을 포함하는 NFA-ε `M = (Q, Σ, δ, q_0, F)`가 주어졌을 때, NFA `M' = (Q, Σ, δ', q_0, F')`를 다음과 같이 정의할 수 있다.

`F' = F ∪ { q_0 }` (만약 `E(q_0) ∩ F ≠ {}` 인 경우) 또는 `F'` = F (그렇지 않은 경우)
`δ'(q, a) = δ*(q, a)` (각 상태 `q ∈ Q` 와 각 기호 `a ∈ Σ`에 대해 확장된 전이 함수 `δ*`를 사용)

여기서 `M`의 전이 함수 `δ`와 `M'`의 전이 함수 `δ'`, 그리고 문자열로 확장된 `δ*`와 `δ'*`를 구별해야 한다. `M'`은 ε-전이를 포함하지 않는다.

귀납법을 사용하여 각 문자열 `w ≠ ε`에 대해 `δ'*(q_0, w) = δ*(q_0, w)`임을 증명할 수 있다.

이를 기반으로, 각 문자열 `w ∈ Σ*`에 대해 `δ'*(q_0, w) ∩ F' ≠ {}`이면, 그리고 그 경우에만 `δ*(q_0, w) ∩ F ≠ {}`임을 보일 수 있다.

`w = ε`인 경우, 이는 `F'`의 정의로부터 따른다.
`w = va`이고 `v ∈ Σ*`, `a ∈ Σ`라고 가정하면, `δ'*(q_0, w) = δ*(q_0, w)`와 `F ⊆ F'`로부터, `δ'*(q_0, w) ∩ F' ≠ {} δ*(q_0, w) ∩ F ≠ {}` 이고, "`⇒`" 방향을 보여야 한다.
`δ'*(q_0, w)`가 `F' { q_0 }`의 상태를 포함하는 경우, `δ*(q_0, w)`는 `F`에 속하는 동일한 상태를 포함한다.
`δ'*(q_0, w)`가 `q_0`를 포함하고 `q_0 ∈ F`이면, `δ*(q_0, w)` 또한 `F`에 있는 상태, 즉 `q_0`를 포함한다.
`δ'*(q_0, w)`가 `q_0`를 포함하고 `q_0 ∉ F`이지만, `q_0 ∈ F'`이면, `E(q_0) ∩ F`에 상태가 존재하고, 동일한 상태가 `δ*(q_0, w) = ⋃_{r ∈ δ*(q, v)} E(δ(r, a))`에 있어야 한다.

NFA는 DFA와 동등하므로, NFA-ε도 DFA와 동등하다.

5. 1. ε-폐쇄 (ε-closure)

상태 q의 ε-폐쇄는 ε-이동만을 통해 q에서 도달 가능한 모든 상태의 집합을 의미한다. 상태 집합 P의 ε-폐쇄는 P의 각 상태에서 ε-이동만을 통해 도달 가능한 모든 상태의 집합이다.

상태 q ∈ Q 에 대해, E(q)는 전이 함수 δ에서 ε-전이를 따라 q로부터 도달 가능한 상태 집합을 나타낸다. 즉, p ∈ E(q)는 다음과 같은 상태 시퀀스 q₁, ..., q_k 가 존재할 경우 성립한다.

q₁ = q
각 1 ≤ i < k 에 대해 q_i+1 ∈ δ(q_i, ε)
q_k = p

E(q)는 q의 ε-폐쇄라고 알려져 있다.

NFA(비결정론적 유한 상태 기계)의 상태 집합 P의 ε-폐쇄는 ε-전이를 따라 P의 임의의 상태로부터 도달 가능한 상태 집합으로 정의된다. 공식적으로, P ⊆ Q 에 대해, E(P) = ∪_q∈P E(q)로 정의한다.

5. 2. NFA-ε와 NFA의 동등성

NFA-ε는 NFA와 동등하다. NFA는 NFA-ε의 특수한 경우이므로, 모든 NFA-ε에 대해 동등한 NFA가 존재함을 보이면 된다.

엡실론 이동(ε-이동)을 포함하는 NFA-ε `M = (Q, Σ, δ, q_0, F)`가 주어졌을 때, NFA `M' = (Q, Σ, δ', q_0, F')`를 다음과 같이 정의할 수 있다.

`F' = F ∪ { q_0 }` (만약 `E(q_0) ∩ F ≠ {}` 인 경우) 또는 `F'` = F (그렇지 않은 경우)
`δ'(q, a) = δ*(q, a)` (각 상태 `q ∈ Q` 와 각 기호 `a ∈ Σ`에 대해 확장된 전이 함수 `δ*`를 사용)

여기서 `M`의 전이 함수 `δ`와 `M'`의 전이 함수 `δ'`, 그리고 문자열로 확장된 `δ*`와 `δ'*`를 구별해야 한다. `M'`은 ε-전이를 포함하지 않는다.

귀납법을 사용하여 각 문자열 `w ≠ ε`에 대해 `δ'*(q_0, w) = δ*(q_0, w)`임을 증명할 수 있다.

이를 기반으로, 각 문자열 `w ∈ Σ*`에 대해 `δ'*(q_0, w) ∩ F' ≠ {}`이면, 그리고 그 경우에만 `δ*(q_0, w) ∩ F ≠ {}`임을 보일 수 있다.

`w = ε`인 경우, 이는 `F'`의 정의로부터 따른다.
`w = va`이고 `v ∈ Σ*`, `a ∈ Σ`라고 가정하면, `δ'*(q_0, w) = δ*(q_0, w)`와 `F ⊆ F'`로부터, `δ'*(q_0, w) ∩ F' ≠ {} δ*(q_0, w) ∩ F ≠ {}` 이고, "`⇒`" 방향을 보여야 한다.
`δ'*(q_0, w)`가 `F' { q_0 }`의 상태를 포함하는 경우, `δ*(q_0, w)`는 `F`에 속하는 동일한 상태를 포함한다.
`δ'*(q_0, w)`가 `q_0`를 포함하고 `q_0 ∈ F`이면, `δ*(q_0, w)` 또한 `F`에 있는 상태, 즉 `q_0`를 포함한다.
`δ'*(q_0, w)`가 `q_0`를 포함하고 `q_0 ∉ F`이지만, `q_0 ∈ F'`이면, `E(q_0) ∩ F`에 상태가 존재하고, 동일한 상태가 `δ*(q_0, w) = ⋃_{r ∈ δ*(q, v)} E(δ(r, a))`에 있어야 한다.

NFA는 DFA와 동등하므로, NFA-ε도 DFA와 동등하다.

6. 확장 NFA (GNFA)

확장 비결정적 유한 오토마톤(GNFA^[11]) 또는 확장 비결정적 유한 상태 기계^[12]는 각 상태 전이가 임의의 정규 표현식에 대응하는 NFA이다. GNFA는 입력으로부터 한꺼번에 여러 문자를 읽어들이지만, 그 문자열은 전이(에지)에 표기된 정규 표현식에 대응하는 것이다.

GNFA는 (S, Σ, T, s, a)의 5개 요소로 구성되며, 각 요소는 다음과 같은 성질을 갖는다.

상태의 유한 집합(S)
입력 문자의 유한 집합(Σ)
전이 함수(T: (S - {a}) × (S - {s}) → R)
시작 상태(s ∈ S)
수용 상태(a ∈ S)

여기서 R은 문자 집합 Σ로 구성된 모든 정규 표현식의 집합이다.

DFA나 NFA는 쉽게 GNFA로 변환할 수 있으며, GNFA는 정규 표현식으로 쉽게 변환할 수 있다. 그 변환은 중간적인 전이를 정규 표현식으로 변환해 가면서, 최종적으로 S = {s, a}라는 하나의 전이(에지)가 되도록 하는 것이다. 마찬가지로 GNFA의 각 전이(에지)에 부기된 정규 표현식을 한 글자씩 분해할 때까지 중간 상태를 추가하면 NFA로 변환할 수 있다. 또한 NFA는 앞서 언급했듯이 DFA로 변환 가능하다. 따라서 GNFA는 DFA 및 NFA와 등가인 형식 언어를 이해한다.^[11]^[12]

7. 닫힘 성질 (Closure Properties)

NFA가 인식하는 언어 집합은 다음과 같은 연산에 대해 닫혀 있다. 이러한 닫힘 연산은 모든 정규 표현식에서 NFA를 구성하는 톰슨의 구성 알고리즘에서 사용된다. 또한 NFA가 정확히 정규 언어를 인식한다는 것을 증명하는 데 사용할 수 있다.

합집합: 언어 ''L''₁이 어떤 NFA ''A''₁에 의해 허용되고 ''L''₂가 어떤 ''A''₂에 의해 허용되는 경우, 언어 ''L''₁∪''L''₂를 허용하는 NFA ''A''_u를 구성할 수 있다.
주어진 NFA ''N''(''s'')와 ''N''(''t'')의 언어의 합집합을 허용하는 합성 NFA. 언어 합집합의 입력 문자열 ''w''에 대해 합성 오토마톤은 ''q''에서 적절한 하위 오토마톤의 시작 상태로 ε-전이를 따른다. 여기서 ''w''를 따라 허용 상태에 도달할 수 있다. 거기에서 다른 ε-전이를 통해 상태 ''f''에 도달할 수 있다.
교차: ''A''₁과 ''A''₂에서 ''L''₁∩''L''₂를 허용하는 NFA ''A''_i를 구성할 수 있다.
연결
부정: ''A''₁에서 Σ^*\''L''₁을 허용하는 NFA ''A''_n을 구성할 수 있다.
클레이니 스타

NFA는 ε-이동이 있는 비결정적 유한 오토마톤(NFA-ε)과 동일하므로 위 닫힘은 NFA-ε의 닫힘 속성을 사용하여 증명된다.

8. 구현

NFA를 구현하는 방법에는 여러 가지가 있다.^[5]

등가 DFA로 변환한다. 경우에 따라 상태 수가 기하급수적으로 증가할 수 있다.^[5] 모든 NFA는 DFA로 변환 가능하다.
NFA가 현재 있을 수 있는 모든 상태의 집합 자료 구조를 유지한다. 입력 기호를 소모할 때, 모든 현재 상태에 적용된 전이 함수의 결과를 합집합하여 다음 상태 집합을 얻는다. ε-이동이 허용되는 경우, 이러한 이동으로 도달할 수 있는 모든 상태(ε-폐쇄)를 포함한다. 각 단계는 최대 ''s''²개의 계산을 필요로 하며, 여기서 ''s''는 NFA의 상태 수이다. 마지막 입력 기호를 소모할 때, 현재 상태 중 하나가 최종 상태이면 기계는 해당 문자열을 수락한다. 길이가 ''n''인 문자열은 ''O''(''ns''²) 시간 및 ''O''(''s'') 공간으로 처리할 수 있다.^[5]
여러 상태로의 전이에 대해, 배열과 같은 자료 구조를 사용하여, 전이 가능한 상태에 표시한다(상태 번호를 인덱스로 하는 배열). 표시된 여러 상태가 가질 수 있는 상태로 간주되며, 입력에 따라 가질 수 있는 모든 상태에 대해 전이 대상을 판단한다(어떤 상태는 입력 문자를 허용하지 않는 경우도 있으며, 그 경우 해당 상태는 버려진다). 이렇게 하여 최종적으로 수용 상태에 표시가 되어 있다면, 해당 입력 문자열이 수용된 것으로 판단할 수 있다.
여러 복사본을 만든다. 각 ''n'' 방향 결정에 대해 NFA는 최대 ''n''−1개의 기계 복사본을 생성한다. 각 복사본은 별도의 상태로 들어간다. 마지막 입력 기호를 소모한 후, NFA의 복사본 중 적어도 하나가 수락 상태에 있으면 NFA는 수락한다. (이 역시 NFA 상태 수에 비례하는 선형 스토리지를 필요로 한다. NFA 상태마다 하나의 기계가 있을 수 있기 때문입니다.)
객체 지향적인 구현 방법으로, NFA를 객체로 하여, 전이 대상이 여러 개 존재하는 경우 전이 대상의 개수만큼 객체의 복사본을 생성하여 각각에 동일한 입력 문자열(미입력분)을 부여하는 방법이 있다. 최종적으로 수용 상태가 된 NFA 객체가 존재한다면, 해당 문자열이 수용된 것으로 판단할 수 있다. 현재 상태와 미입력 입력 문자열을 인수로 하는 재귀 함수의 형태도 가능하다.
NFA의 전이 구조를 통해 토큰을 명시적으로 전파하고 토큰이 최종 상태에 도달할 때마다 일치시킨다. 이는 NFA가 전이를 유발한 이벤트에 대한 추가 컨텍스트를 인코딩해야 하는 경우에 유용하다.^[6]

9. 복잡도

NFA에 대한 공집합 문제는 선형 시간 안에 해결할 수 있다. 즉, 주어진 NFA의 언어가 공집합인지 확인할 수 있다. 이를 위해 초기 상태에서 깊이 우선 탐색을 수행하고 일부 최종 상태에 도달할 수 있는지 확인할 수 있다.^[7]

NFA가 주어졌을 때, 해당 NFA가 ''전체적''인지, 즉, 허용하지 않는 문자열이 있는지 테스트하는 것은 PSPACE-완전 문제이다. 결과적으로, 동일한 문제가 ''포함 문제''에도 적용된다. 즉, 두 개의 NFA가 주어졌을 때, 하나의 언어가 다른 언어의 부분 집합인지 묻는 것이다.^[7]

NFA ''A''와 정수 n이 입력으로 주어졌을 때, ''A''가 허용하는 길이 ''n''의 단어가 몇 개인지 결정하는 계산 문제는 풀기 어렵다. 이는 '''#P'''-hard 문제이다. 실제로 이 문제는 파시모니어스 환산에 따라 복잡도 클래스 SpanL에 대해 완전하다.^[8]

10. 응용

NFA는 주어진 언어를 인식하는 NFA를 구성하는 것이 해당 언어에 대한 DFA를 구성하는 것보다 더 쉬울 때가 있기 때문에 유용하다. 또한, NFA는 계산 이론에서 많은 중요한 속성을 확립하는 데 필요한 수학적 작업의 복잡성을 줄이는 데 사용될 수 있기 때문에 중요하다. 예를 들어, NFA를 사용하면 DFA보다 정규 언어의 폐포 성질을 증명하는 것이 훨씬 쉽다.

참조

_[1] 서적 Introduction to Languages and the Theory of Computation McGraw Hill
_[2] 문서
_[3] 서적 The Design and Analysis of Computer Algorithms https://archive.org/[...] Addison-Wesley
_[4] 웹사이트 Finite-State Machine http://foldoc.org/nf[...]
_[5] 웹사이트 NFA to DFA blowup https://cseweb.ucsd.[...] 2005-02-27
_[6] 간행물 Adding trace matching with free variables to AspectJ http://abc.comlab.ox[...]
_[7] 저널 The equivalence problem for regular expressions with squaring requires exponential space IEEE Computer Society 1972-10-25
_[8] 저널 A very hard log-space counting class https://dx.doi.org/1[...] 1993-01-04
_[9] 웹사이트 Finite State Machine http://foldoc.doc.ic[...] 2005-11-20
_[10] 서적 コンパイラI: 原理・技法・ツールサイエンス社
_[11] 문서
_[12] 문서
_[13] 서적 Introduction to Languages and the Theory of Computation McGraw Hill
_[14] 저널 Finite Automata and Their Decision Problems 1959-04
_[15] 서적 Introduction to Automata Theory, Languages, and Computation https://archive.org/[...] Addison-Wesley
_[16] 서적 The Design and Analysis of Computer Algorithms https://archive.org/[...] Addison-Wesley
_[17] 서적 Introduction to the Theory of Computation https://archive.org/[...] PWS Publishing Co.
_[18] 서적 Introduction to Automata Theory, Languages, and Computation http://148.216.38.24[...] Addison Wesley 2021-04-03

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com