카테고리 없음

[계산이론] Finite Automata - 5

7_JUN_7 2023. 10. 18. 03:47

Reduction of the number of states

One language can be accepted by many DFAs

  • 하나의 DFA는 하나의 언어만 수용합니다 ( One DFA => One Language )
    • 결정적 유한 자동기 (DFA)는 명확하게 정의된 전이 함수를 가지고 있으므로 주어진 입력에 대해 항상 동일한 결과를 생성합니다. 따라서 각 DFA는 특정 언어를 수용하며, 그 언어는 DFA의 구조와 전이 함수에 의해 결정됩니다.
  •  하나의 언어는 여러 DFA에 의해 수용될 수 있습니다 ( One language => many DFAs )
    • 특정 언어를 수용하는 DFA를 여러 가지 방식으로 설계할 수 있습니다. 예를 들어, 불필요한 상태를 가진 DFA와 최소화된 DFA는 동일한 언어를 수용할 수 있습니다. 또한, 다양한 구조와 전이를 가진 여러 DFA가 동일한 언어를 수용할 수 있습니다.

구별 불가능한 상태 (Indistinguishable states)

  •  DFA의 두 상태 p와 q는 다음 조건이 충족될 때 '구별 불가능하다'고 부른다
    • 𝛿^∗ (𝑝, 𝑤) ∈ 𝐹 implies 𝛿^∗ (𝑞, 𝑤) ∈ 𝐹
    • and
    • 𝛿^∗ (𝑝, 𝑤) ∉ 𝐹 implies 𝛿∗ (𝑞, 𝑤) ∉ 𝐹
      • 즉, 상태 p에서 시작하여 문자열 w를 따라 전이하면 수락 상태에 도달한다면  𝛿^∗(𝑞, 𝑤)도 𝐹에 속해야 합니다.
      • 상태 p에서 시작하여 문자열 w를 따라 전이하면 수락 상태에 도달하지 않는다면 𝛿^∗(𝑞, 𝑤)도 𝐹에 속하지 않아야 합니다.
    •  두 상태가 구별 불가능하다는 것은 그 두 상태가 동일한 동작을 하며, 동일한 입력에 대해 동일한 결과를 생성한다는 것을 의미합니다. 즉, 두 상태는 DFA의 동작에 있어서 실질적으로 동일하다고 볼 수 있습니다.
    • DFA 상태의 수 축소 (Reducing the number of DFA states)
      • Reducing the number of DFA states = finding indistinguishable pairs and merging them
      • DFA의 상태 수를 줄이는 것은 구별 불가능한 상태 쌍(indistinguishable pairs)을 찾아서 그들을 합치는(merging) 것을 의미합니다.

Finding and merging indistinguishable pairs

1. 초기상태에서 도달할 수 없는(inaccessible) 모든 상태를 제거한다 ( Remove all inaccessible states, where no path exists from the initial state)

 

다음은 예시로 존재하는 DFA의 transition graph이다.

여기서 초기 상태에서 시작할 때 절대 도달할 수 없는 상태는 q5이다. q5에 도달할수 있는 어떠한 경로는 존재하지 않는다. 고로, q5의 상태를 삭제한다.

 

2. 상태 쌍 그리드 구성 (Construct a grid of pairs of states)

"상태 쌍 그리드"는 DFA의 상태 간의 관계를 시각적으로 표현하기 위한 도구이다. 이 그리드는 DFA의 모든 상태 쌍을 나타내며, 각 쌍이 구별 가능한지 또는 구별 불가능한지를 판단하는 데 사용됩니다.

  • 우선 그래프에서 구별가능한 상태를 판단해야한다.
  • For a pair (𝑝, 𝑞) , if 𝑝 ∈ 𝐹 and 𝑞 ∉ 𝐹 (or vice versa), (𝑝, 𝑞) is distinguishable
  • 쌍 (𝑝, 𝑞)에 대해, 𝑝가 수락 상태에 있고 𝑞가 수락 상태에 있지 않으면 (또는 그 반대의 경우) (𝑝, 𝑞)는 구별됩니다.
  • (q0,q3),(q0,q4),(q1,q3),(q1,q4),(q2,q3),(q2,q4)는 수락 상태의 여부가 명확하게 드러나있기 때문에 확실하게 구별할 수 있기 때문에 그리드 상에 표시가 가능하다.

  • For all pairs (𝑝, 𝑞) and all 𝑎 ∈ Σ, compute 𝛿 (𝑝, 𝑎) = 𝑝𝑎 and 𝛿 (𝑞, 𝑎) = 𝑞𝑎.
  • 쌍 (𝑝, 𝑞)와 𝑎를 포함하는 문자열 Σ에 대해, 𝛿 (𝑝, 𝑎) = 𝑝𝑎 와 𝛿 (𝑞, 𝑎) = 𝑞𝑎를 계산한다.
  • If the pair 𝑝𝑎, 𝑞𝑎 is distinguishable, then 𝑝, 𝑞 is distinguishable
  • 만약 𝑝𝑎, 𝑞𝑎 쌍이 구별되면, 𝑝와 𝑞도 구별됩니다.

{0, 1} given 0 => {1, 2}

{0, 1} given 1 => {2, 3}

{0, 2} given 0 => {1, 2}

{0, 2} given 1 => {2, 4}

{1, 2} given 0 => {2, 2}

{1, 2} given 1 => {3, 4}

{3, 4} given 0 => {3, 4}

{3, 4} given 1 => {3, 4}

 

{1,2} 와 {3,4} 상태 쌍은 pq, qa 계산을 해도 둘 다 같은 비수락 상태거나 수락 상태의 같은 결과를 나타내기 때문에 구별할 수 없다.

그러나

{0,1} 쌍의 경우는

입력 0을 받을 때는 아직 구별할 수 없지만

입력 1을 받아 계산할 때 0의 상태는 2로, 2의 상태는 종료상태인 3으로 전이되기 때문에 구별이 된다.

{0,2} 쌍의 경우에도

입력 1을 받을 때 계산 후에 상태는 구별이 가능해진다.

 

즉 {1,2} , {3,4}의 상태만이 구별할 수 없다.

3. 새로운 DFA 구성 ( Construct a new DFA)

  • 구별 불가능한 상태들을 하나의 상태로 합친다. ( Indistinguishable states => a single state)

우리는 방금의 과정들을 통해 두 가지 구별 불가능한 상태를 얻었다.구별 불가능한 상태를 하나의 집합으로 묶어서 총 우리는 3개의 state를 얻을 수 있다.

{𝑞0}, {𝑞1, 𝑞2}, {𝑞3, 𝑞4}

q0에 0을 입력하면 q1을 전이된다.

q0에 1을 입력하면 q2로 전이된다.

 

q1,q2은 구별 불가능한 상태이니 전이함수로 묶어서 표현해서

𝛿′ (𝑞0 , 0) = 𝛿′ (𝑞0 , 1) = {𝑞1, 𝑞2}

q1에 0을 입력하면 q2로 전이된다.

q2에 0을 입력하면 같은 q2로 전이된다.

 

{q1,q2}는 구별 불가능한 상태이니

이를 묶어서

𝛿′ ({𝑞1, 𝑞2} , 0) = {𝑞1, 𝑞2} 로 표현

q1에 1을 입력하면 q3로 전이된다.

q2에 1을 입력하면 q4로 전이된다.

 

{q1,q2}는 구별 불가능한 상태이니

이를 묶어서

𝛿′ ({𝑞1, 𝑞2} , 1) = {𝑞3, 𝑞4} 로 표현

q3 또는 4에 0을 입력하면 자기 자신으로 상태를 유지한다.

q3 또는 4에 1을 입력하면 자기 자신으로 상태를 유지한다.

 

{q3,q4}는 구별 불가능한 상태이니

이를 묶어서

𝛿′ ({𝑞3, 𝑞4} , 0) = 𝛿′ ({𝑞3, 𝑞4} , 1)  = {𝑞3, 𝑞4} 로 표현

 

만들어진 새로운 DFA는 다음과 같다.

 

실습문제

(𝜮 = {𝒂, 𝒃})