공간 효율이 좋은 오토마타가 더 바람직하다

  • 한 dfa는 한 언어를 정의한다.
  • 그러나 한 언어를 정의하는 dfa는 여러 개 있을 수 있다.
  • 공간 효율을 위해 여러 dfa 중에서 상태가 적은 오토마타를 선택하는 것이 바람직하다.
    • 즉, 중복 상태를 최소화하여 간단하게 만들자.

DEFINITION 2.8
Two states p and q of a dfa are called indistinguishable if
\(δ^*(p, w) ∈ F\) implies \(δ^*(q, w) ∈ F\),
and
\(δ^*(p, w) ∉ F\) implies \(δ*^(q, w) ∉ F\),
for all \(w ∈ Σ^*\). If, on the other hand, there exists some string \(w ∈ Σ^*\) such that
\(δ^*(p, w) ∈ F\) and \(δ* (q, w) ∉ F\),
or vice versa, then the states p and q are said to be distinguishable by a string w.

구분불가능(indistinguishable)

어느 dfa에 p, q 라는 두 상태가 있다고 하자.

모든 문자열 \(w ∈ Σ^*\)에 대해 다음의 두 조건을 만족한다면 상태 p와 q는 구분불가능하다.

  • \(δ^*(p, w) ∈ F\) implies \(δ^*(q, w) ∈ F\).
    • 상태 p일 때 입력 w를 받으면 최종 상태 중 하나가 된다.
    • 상태 q일 때 입력 w를 받으면 최종 상태 중 하나가 된다.
  • \(δ^*(p, w) ∉ F\) implies \(δ*^(q, w) ∉ F\).
    • 상태 p일 때 입력 w를 받으면 최종 상태가 되지 못한다.
    • 상태 q일 때 입력 w를 받으면 최종 상태가 되지 못한다.

구분불가능은 동치 관계(equivalence relation).

구분가능(distinguishable)

어느 dfa에 p, q 라는 두 상태가 있다고 하자.

다음의 조건을 만족하는 문자열 \(w ∈ Σ^*\)가 존재한다면, 상태 p와 q는 구분가능하다.

  • \(δ^*(p, w) ∈ F\) and \(δ* (q, w) ∉ F\).
    • 상태 p일 때 입력 w를 받으면 최종 상태 중 하나가 된다.
    • 상태 q일 때 입력 w를 받으면 최종 상태가 되지 못한다.

구분불가능한 상태 찾아내기

구분불가능한(indistinguishable) 상태를 찾아내서 합치는 방법을 사용하면 효율적인 dfa를 만들 수 있다.

구분불가능한 상태를 모두 찾으려면 어떻게 해야 할까?

일단 구분가능한 상태의 쌍을 먼저 찾아 표시하는 방법이 있다.

다음의 "프로시저: mark"는 모든 구분가능한 쌍을 찾아 표시하는 방법이다.

procedure: mark

  1. Remove all inaccessible states. This can be done by enumerating all simple paths of the graph of the dfa starting at the initial state. Any state not part of some path is inaccessible.
  2. Consider all pairs of states \((p, q)\). If \(p ∈ F\) and \(q ∉ F\) or vice versa, mark the pair \((p, q)\) as distinguishable.
  3. Repeat the following step until no previously unmarked pairs are marked. For all pairs \((p, q)\) and all \(a ∈ Σ\), compute \(δ (p, a) = p_a\) and \(δ (q, a) = q_a\). If the pair \((p_a, q_a)\) is marked as distinguishable, mark \((p, q)\) as distinguishable.
    We claim that this procedure constitutes an algorithm for marking all distinguishable pairs.
  1. 도달할 수 없는 상태를 모두 찾아 삭제한다.
    • 모든 단순 경로를 나열해서(brute force), 없는 상태는 도달불가능이다.
  2. 두 상태 쌍 \((p, q)\)에 대해 "\(p ∈ F\) 이고, \(q ∉ F\)이다" 이거나 "\(p ∉ F\) 이고, \(q ∈ F\)이다" 이면, \((p, q)\)는 구분가능이라고 표시한다.
    • 얘네는 구분가능이므로 중복 상태가 아니다. 줄일 수 없다.
  3. 나머지 상태 쌍에 대해 계속 작업한다. 더 이상 표시할 수 없다면 멈춘다.
  4. 모든 \((p, q)\)와 모든 \(a ∈ Σ\)에 대하여, \(δ(p, a) = p_a\)와 \(δ(q, a) = q_a\)를 계산한다.
  5. 만약 \((p_a, q_a)\)가 구분가능으로 표시되어 있다면, \((p, q)\)를 구분가능으로 표시한다.

THEOREM 2.3
The procedure mark, applied to any dfa \(M = (Q, Σ, δ, q_0, F)\), terminates and determines all pairs of distinguishable states.

정리 2.3

  • 프로시저 mark는 어떤 dfa \(M = (Q, Σ, δ, q_0, F)\)에 적용하건 간에,
    • 언젠가는 종료된다. (무한루프하지 않는다.)
    • 모든 구분가능한 상태 쌍을 결정한다.

증명은 생략.

dfa 축소하기

procedure: reduce
Given a dfa \(M = (Q, Σ, δ, q_0, F)\), we construct a reduced dfa \(\widehat{M}=( \widehat{Q}, Σ, \widehat{δ}, \widehat{q_0}, \widehat{F})\)

  1. Use procedure mark to generate the equivalence classes, say {\(q_i, q_j, ..., q_k\)}, as described.
  2. For each set {\(q_i, q_j, ..., q_k\)} of such indistinguishable states, create a state labeled \(ij ... k\) for \(\widehat{M}\).
  3. For each transition rule of M of the form
    \(δ (q_r, a) = q_p\),
    find the sets to which \(q_r\) and \(q_p\) belong. If \(q_r ∈ \{q_i, q_j, ..., q_k \}\) and \(q_p ∈ \{ q_l, q_m, ..., q_n \}\), add to δˆ a rule
    \(\widehat{δ} (ij ... k, a) = lm ... n.\)
  4. The initial state \(\widehat{q_0}\) is that state of \(\widehat{M}\) whose label includes the 0.
  5. \(\widehat{F}\) is the set of all the states whose label contains i such that \(q_i ∈ F\).

주어진 dfa \(M = (Q, Σ, δ, q_0, F)\)로, 축소된 dfa \(\widehat{M}=( \widehat{Q}, Σ, \widehat{δ}, \widehat{q_0}, \widehat{F})\)를 만들자.

  1. 프로시저 mark를 써서 동치 부류(class)를 만든다.
    • 구분불가능한 상태들의 집합 {\(q_i, q_j, ..., q_k\)} 을 찾아낸다는 말.
  2. 구분불가능한 상태들의 집합 {\(q_i, q_j, ..., q_k\)} 에 대하여, 라벨이 \(ij ... k\)인 \(\widehat{M}\)의 상태를 생성한다.
  3. \(δ (q_r, a) = q_p\) 형태를 갖는 M의 각 전이 규칙에 대하여, \(q_r, q_p\)가 들어있는 집합을 찾는다.
    • 만약 \(q_r ∈ \{ q_i, q_j, ..., q_k \}\) 이고 \(q_p ∈ \{ q_l, q_m, ..., q_n \}\) 이면, \(\widehat{δ}\) 에 다음 규칙을 추가한다.
    • \(\widehat{δ} (ij ... k, a) = lm ... n\).
  4. 초기 상태 \(\widehat{q_0}\)은 \(\widehat{M}\) 상태들 중 라벨이 0을 포함하는 상태이다.
  5. \(\widehat{F}\) 는 라벨이 \(q_i ∈ F\)인 \(i\) 를 포함하는 모든 상태들의 집합이다.

THEOREM 2.4
Given any dfa M, application of the procedure reduce yields another dfa \(\widehat{M}\) such that
\(L (M) = L ( \widehat{M} )\).
Furthermore, \(\widehat{M}\) is minimal in the sense that there is no other dfa with a smaller number of states that also accepts \(L (M)\).

  • 어떤 dfa M 에 대해 프로시저 reduce를 사용하면 \(L(M) = L(\widehat{M})\)을 만족하는 dfa \(\widehat{M}\)을 얻을 수 있다.
  • \(\widehat{M}\) 은 언어 \(L(M)\)을 accept하는 dfa 중 상태의 수가 가장 적은 dfa 이다.

증명은 생략.