[계산이론] Finite Automata - 4

Equivalence of NFAs and DFAs

Every NFA has an equivalent DFA??

• Equivalence
  • 두 finite automata M1과 M2가 동등하다(equivalent)고 말할 때, 그것은 𝐿(𝑀1) = 𝐿(𝑀2)
  • 즉, 두 자동기가 동일한 언어를 수용한다는 것을 의미합니다.

NFA (𝑁 = (𝑄, Σ, 𝛿, 𝑞0, 𝐹)) => DFA (𝑀 = (𝑄′, 𝛴, 𝛿′, 𝑞0′, 𝐹′))   NFA를 DFA로 변환하는 과정

 

1. 𝑁 에 대한 전이 테이블 생성 ( Create a transition table for 𝑁)

 

우선 N을 사용해 NFA에 대한 Transition Table을 만든다.

예시 NFA에 대한 Transition Table은 다음과 같다.

2. DFA의 시작 상태 생성 ( Create the DFA’s start state )

• NFA의 가능한 모든 시작 상태의 집합(set of all possible starting states)을 사용하여 DFA의 시작 상태를 생성한다.
• NFA의 시작 상태 𝑞0에서 𝜆-전이 (엡실론 전이)를 따라 도달할 수 있는 모든 상태의 경우
  • 이 경우, 시작 상태는 {𝑞0}가 됩니다.

3. DFA의 전이 테이블 생성 ( Create the DFA’s transition table)

• 새로운 상태가 생성되지 않을 때까지 계속합니다.

4. DFA의 최종 상태 결정 ( Determining the final state of the DFA)

• NFA의 최종 상태 중 적어도 하나를 포함하는 상태의 집합을 찾습니다.
• 이러한 집합들은 DFA의 최종 상태가 됩니다.

이렇게 M 전이 테이블이 완성되면 Transition graph를 그릴 수 있다.

실습 문제

• Converting NFA to DFA (𝛴 = {𝑎, 𝑏})