[Compiler] 4-2. Finite Automata

Convert an ε-NFA to a DFA

Regular expression을 -> NFA automata로 만들고 -> DFA automata로 변환

ex)

- Regular expression : (a + b)*abb

- ε-NFA : 

 

1. start symbol의 ε-closure를 구해라

• ε-closure(0) = {0, 1, 2, 4, 7, 8} -> A라는 state라고 하겠다.
• Ds = {A} -> Ds라는 곳에다가(queue라고 생각) A를 추가
• 아래 처럼 그림 그리기

2. Ds에 있는 element를 pop 한다. -> A 나온다.

• A는 {0, 1, 2, 3, 7, 8}이라는 state다.
• {0, 1, 2, 3, 7, 8}에서 a로 갈 수 있는 state를 찾는다. : {0, 1, 2, 3, 7, 8} + a -> {3, 9}
• ε-closure({3, 9}) = {1, 2, 3, 4, 6, 7, 8, 9, 10} -> B
  
  • ε-closure(3) = {3, 6, 1, 2, 4, 7, 8}
  • ε-closure(9) = {9, 10}
• Ds = {B}
• 다음 아래 그림 그리기

• {0, 1, 2, 4, 7} + b -> {5}
• ε-closure({5}) = {1, 2, 4, 5, 6, 7, 8} -> C
  
  • C로 할당 -> 기존의 것과 겹치는 것이 없기 때문에 새로 할당하는 것이다.
• Ds = {B, C}

3. Ds에서 pop -> B나온다.

• {1, 2, 3, 4, 6, 7, 8, 9, 10} + a -> {3, 9}
• ε-closure({3, 9}) = {1, 2, 3, 4, 6, 7, 8, 9, 10} -> B
  
  
• {1, 2, 3, 4, 6, 7, 8, 9, 10} + b -> {5, 11}
• ε-closure({3, 9}) = {1, 2, 4, 5, 6, 7, 8, 11, 12} -> D
• Ds = {C, D}

4. Ds에서 pop -> C

• {1, 2, 4, 5, 6, 7, 8} + a -> {3, 9}
• ε-closure({3, 9}) = {1, 2, 3, 4, 6, 7, 8, 9, 10} -> B
  
• {1, 2, 4, 5, 6, 7, 8} + b -> {5}
• ε-closure({5}) = {1, 2, 4, 5, 6, 7, 8} -> C
• Ds = {D}

5. Ds에서 pop -> D

• {1, 2, 3, 4, 5, 6, 7, 11, 12} + a -> {3, 9}
• ε-closure({3, 9}) = {1, 2, 3, 4, 6, 7, 8, 9, 10} -> B
  
• {1, 2, 3, 4, 5, 6, 7, 11, 12} + b -> {5, 13}
• ε-closure({5, 13}) = {1, 2, 4, 5, 6, 7, 8, 13} -> E
• Ds = {E}

 

6. Ds에서 pop -> E

• {1, 2, 4, 5, 6, 7, 8, 13} + a -> {3, 9}
• ε-closure({3, 9}) = {1, 2, 3, 4, 6, 7, 8, 9, 10} -> B
  
• {1, 2, 4, 5, 6, 7, 8, 13} + b -> {5}
• ε-closure({5}) = {1, 2, 4, 5, 6, 7, 8} -> C

7. Ds = {}

• A : {0, 1, 2, 4, 5, 8}
• B : {1, 2, 3, 4, 6, 7, 8, 9, 10}
• C : {1, 2, 4, 5, 6, 7, 8}
• D : {1, 2, 4, 5, 6, 7, 8, 11, 12}
• E : {1, 2, 4, 5, 6, 7, 8, 13}

ε-NFA의 Accepting state는 13이다.

위에서 13을 포함한 state는 E밖에 없으므로 E가 Accepting state이다.

8. 최종

---

Regular Language and DFA

Language L은 일부 DFA에서 accept한다면, Regular Language 이다.

Regular Language는 다른 많은 DFA에 의해 accept 될 수 있다.

ex) 아래 두 그림은 다르지만, 똑같이 L(a*)이다.

 

Minimal DFA

L에 대한 minimal DFA는 L을 accept하는 모든 DFA 중 state 수가 가장 적은 DFA이다.

 ex)

 

Reachability

DFA에 start state q0에서 연결할 수 없는 상태가 있을 수 있다.

필요 없는 것은 지우면 된다.

ex)

아래 그림에서 표시된 부분은 start state에서 도달할 수 없는 부분이므로 지워야 한다.

 

 

Reachable states

DFA D = (Q, ∑, δ, q0, F)가 있을 때, Qr을 reachable states라고 한다.

Qr = {p ∈ Q | (∃u ∈ ∑*)(p=δ*(q0, u))}

• r, s가 정의되면,
  Q - Qr = 도달할 수 없는 state => 지우면 된다.

ex)

 

State Equivalence(일치, 동치)

DFA D = (Q, ∑, δ, q0, F)가 주어졌을 때, Q에 대해 relation ≡  하다고(같다고) 하면, state equivalence하다고 한다.

모든 p, q ∈ Q,

p ≡ q iff(if and only if, 필요충분) ∀w ∈ ∑* (δ*(p,w) ∈ F iff δ*(q,w) ∈ F)

• p, q가 w에 의해 accepting state에 도달할 경우 p와 q를 하나로 표현 가능하다.
• 이 '같다'를 어떻게 정의할지에 관한 내용이다.

 

Finding Minimal DFA

1. reachable states를 확인한다.

2. non-reachable states를 지운다.

3. equivalence states를 찾아서 하나로 합친다.

ex) Find the equivalence class 과정

1.

Input	Class 1				Class 2
	A	B	C	D	E
a	1	1	1	1	1
b	1	1	1	2	1

• Accepting state와 non Accepting state로 class 나누기
• A에 input으로 a를 받아 B로 가는 경우, B는 1class이므로 1표시
• D에서 b를 입력받아 2 class에 있는 state로 이동하므로 2라고 표시
  => 다른 class로 가기 때문에 독립적인 class로 나누어준다.

2.

Input	Class 1			Class 2	Class 3
	A	B	C	D	E
a	1	1	1	1	1
b	1	2	1	3	1

3.

Input	Class 1		Class 2	Class 3	Class 4
	A	C	B	D	E
a	2	2	2	2	2
b	1	1	3	4	1

• 더 이상 나눌 것이 없고, Class 1은 같은 곳으로 간다.
  => 하나의 state로 merge 가능하다.

4. 최종

 

regular expression : regular language를 기술할 수 있는 방법
automata : regular language에 속하는지 인식하는 것

Regular expressions and NFA

임의의 정규식 R ∈ R(∑)이 주어지면, L_R = L(N)을 accept하는 NFA N을 구성하는 알고리즘이 있다.

-> R이 어떻게 주어지든 이를 인식할 수 있는 NFA를 만들 수 있는 알고리즘이 있다는 것

알고리즘을 위한 가정

• 각 NFA는 start state와 구별되는(분리된) 하나의 final state를 갖는다.
• start state(s)로 incoming하고, final state로 부터 outgoing하는 transition이 없다.
• 모든 state는 최대 두 개 들어오는 transition과 나가는 transition이 있다.

 

Sombrero construction

위에서 언급한 알고리즘

base case에 대해 NFA 정의

1. R = a

2. R = ε

3. R = ø

4. (R1 + R2) like (a + b)

5. R1R2 like ab

6. R*