NFA/DFA/RE Conversion

○DFA from NFA

 ▷Set of L(M_DFA) ⊆ Set of L(M_NFA)

  ▷DFA는 NFA의 일종이다.

 

 ▷어느 한 NFA가 있으면 L(M_DFA) = L(M_NFA)인 DFA가 존재한다.

 

 ▶DFA - derivation from NFA

  ▷DFA -> D = (Q_D, Σ, δ, S_0, F_D)

  ▷NFA -> N = (Q_N, Σ, Δ, q_0, F_N)

 

  ▷1. Start State에 대한 λ-Closure 구하기 -> S_0

  ▷2. S_0에 대한 Reachable State Set -> S_1, S_2, ... (Set이 다르면 State도 다르다.)

  ▷3. 이전 State에 대한 Reachable State. -> S_n ...

  ▷4. NFA의 Final State를 포함하는 Set을 의미하는 State -> DFA의 Final State

 

○NFA from Regular Expression

 ▷Regular Expression에 대해 이를 의미하는 NFA가 존재한다.

 

 ▶Tompson's Algorithm

  ▷다음 NFA의 Recursive Contruction을 이용해서 Regular Expression을 표현할 수 있다.

  ▷State가 많아지지만, 매우 쉽게 만들 수 있다.

  ▶속성

   ▷Number of states ≤ 2×number of steps

   ▷N은 단 하나의 Start State와 Final State를 가진다. (Final State 에서는 나가는 State가 없다.

   ▷하나의 Outgoing edge를 가지거나, 최대 2개의 Outgoing λ-edges르 가진다.

◎(0 + 11)*

 

○Regular Expression from DFA

 ▷Language of DFA를 의미하는 Regular Expression이 존재한다.

 

 ▶Algorithm

  ▷DFA M = ( {q_1, q_2, ... , q_n}, Σ, δ, q_1, F)

  ▷R_ij^k : k보다 높은 State를 거치지 않고 q_i에서 q_j로 가는 String (도착은 OK)

  ▷L(M) = ∪_q_final∈F R_1f^n