• CHAPTER 2. Finite Automata
    • 2.1 DETERMINISTIC FINITE ACCEPTERS
    • 2.2 NONDETERMINISTIC FINITE ACCEPTERS
    • 2.3 EQUIVALENCE OF DETERMINISTIC AND NONDETERMINISTIC FINITE ACCEPTERS
  • 챕터 2. 유한 오토마타
    • 2.1 결정적 유한 인식기
    • 2.2 비결정적 유한 인식기
    • 2.3 결정적 유한 인식기와 비결정적 유한 인식기의 동치성

동치성(equivalence)

DEFINITION 2.7
Two finite accepters, \(M_1\) and \(M_2\), are said to be equivalent if
\(L(M_1) = L(M_2)\),
that is, if they both accept the same language.

  • \(L(M_1) = L(M_2)\) 이면, 동치.
    • 두 오토마타가 같은 언어를 인식한다면, 두 유한 인식기 \(M_1, M_2\)는 동치.

다음 nfa는(λ 전이가 있으므로 nfa) 언어 \(\{ (10)^n : n \ge 0 \}\)을 인식한다.

q₀ q₁ q₂ 1 0, 1 0 λ

그리고 다음 dfa 도 언어 \(\{ (10)^n : n \ge 0 \}\)을 인식한다.

q₀ q₁ q₂ 1 1 0 0 0, 1

따라서 위의 nfa와 dfa는 동치이다.

The classes of dfa’s and nfa’s are equally powerful: For every language accepted by some nfa there is a dfa that accepts the same language.

  • dfa와 nfa는 같은 능력을 갖고 있다.
    • nfa가 인식하는 모든 언어에 대해, 해당 언어를 인식하는 dfa가 적어도 하나 존재한다.
    • 즉 nfa 하나가 있으면, 동치인 dfa도 존재한다.

THEOREM 2.2
Let L be the language accepted by a nondeterministic finite accepter \(M_N = (Q_N, Σ, δ_N, q_0, F_N)\). Then there exists a deterministic finite accepter \(M_D = (Q_D, Σ, δ_D, \{q_0\}, F_D)\) such that
\(L = L (MD)\).

  • \(M_N = (Q_D, Σ, δ_N, q_0, F_N)\)라는 nfa 가 있다고 하자.
    • 이 nfa가 인식하는 언어를 L 이라 하자.
    • 이 때, \(L = L(M_D)\)를 만족하는 dfa \(M_D = ( Q_D, \Sigma, ldelta_D, \{ q_0 \}, F_D )\)가 존재한다.

결론 : nfa에 의해 인식되는 모든 언어는 정규 언어이다.

  • 정규 언어: \(L = L(M)\)을 만족하는 dfa가 있는 언어 L.