[Compiler] 4-1. Finite Automata

Finite automata (유한 오토마타)

유한 오토마타는 edges가 다음과 같은 유한 전이 그래프다.

• 비공식적 표현
• 입력 기호의 스트림 또는 sequence에 응답하는 동안, 기계가 취할 수 있는 모든 가능한 state 및 transitions(전환)을 캡처하는 상태 다이어그램 (상태 전의도)

• A state에서 a 마킹시 B state가 된다.
• A에서 a 입력시 B로 transition한다.
• 이러한 state들이 유한개 있다.

 

Recognizer for "Regular Languages"

• 정규 언어를 인식하는 수학적 모델
• 어휘 분석기
• 종류 2개
  • Deterministic finite automata
  • Non-Deterministic finite automata

 

Deterministic finite automata (DFA)

DFA는 5-tuple(quintuple)로 정의된다.

D = (Q, ∑, δ, q0, F)

• Q : state의 유한 집합
• ∑ : input symbols(alphabet)의 유한 집합
• δ : transition function
  
  • δ : Q × ∑ -> Q
• q0 : start state (initial state), q0 ∈ Q
• F : final state의 집합, F ⊆ Q
• state p∈Q, input a∈∑에 대해 state q=δ(p, a)는 확실하게 결정된다.
  여러 state 아닌 한 state로 확실하게 결정된다.
• state 중 하나가 uniquely determine 된 것

 

DFA for regular expression

ex1) Regular expression : ab

- state diagram

- DFA :  D = (Q, ∑, δ, q0, F)

• Q = {q0, q1, q2}
• ∑ : {a, b}
• q0 : start state
• F : {q2}
• δ : transition function, δ : Q × ∑ -> Q

δ	a	b
q0	{q1}	ø
q1	ø	{q2}
q2	ø	ø

 

ex2) Regular expression : ((0+1)(0+1))* = {00, 01, 10, 11}*

* 111이 경우 도착지가 Accepting state가 아니기 때문에 인식 불가능

- state diagram

- DFA :  D = (Q, ∑, δ, q0, F)

• Q = {q0, q1, q2, q3}
• ∑ : {0, 1}
• δ : transition function, δ : Q × ∑ -> Q
• q0 : start state
• F : {q0, q2}

δ	0	1
q0	{q3}	{q1}
q1	{q2}	{q0}
q2	{q1}	{q3}
q3	{q0}	{q2}

 

ex3) Regular expression : (0+10)*(ε+1) -> 1이 연속되지 않는 문자열

* 101101은 Accepting state가 아니기 때문에 인식 불가능

- state diagram

- DFA :  D = (Q, ∑, δ, q0, F)

• Q = {q0, q1, q2}
• ∑ : {0, 1}
• δ : transition function, δ : Q × ∑ -> Q
• q0 : start state
• F : {q0, q2}

δ	0	1
q0	{q0}	{q1}
q1	{q0}	{q2}
q2	{q2}	{q2}

 

Definition of the extended transition function δ*

DFA D = (Q, ∑, δ, q0, F)가 주어졌을 때, 확장 전이 함수는 δ* : Q × ∑* -> Q로 정의된다.

• p ∈ Q, u ∈ ∑*, a ∈ ∑
• Basic : δ*(p, ε) = p
• Induction : δ*(p, ua) = δ(δ*(p, u), a)
• δ*(p, w) = w로 지정된 p에서 경로를 따라 상태 p에서 도달한 상태입니다.

 

Language L(D) accepted by DFA D

DFA D = (Q, ∑, δ, q0, F)가 주어졌을 때, D가 수용한 언어 L(D)는 언어다.

L(D) = {w ∈ ∑* | δ*(q0, w) ∈ F}

문자열 w ∈ ∑*는 입력 q0에서 w를 따라가 Accepting state로 끝나는 경우 인식 가능하다.

-> 이러한 w를 모아둔 것이 L(D)

 

Membership (recognition) problem (Revisited)

정의 : ∑*에 포함된 w가 주어지고, L(Language)가 있을 때, w가 L에 속하는지 판단(결정)하고 싶다.

w ∈ ∑*가 주어졌을 때, w는 DFA에 acceptable 한가?

• q0로 부터 시작한다.
• 모든 symbol을 사용했을 때, 도달한 state가 accepting state(F)에
  있으면 accept한 것
  그렇지 않으면 reject 된다.

---

Non-Deterministic finite automata (NFA)

NFA는 5-tuple(quintuple)로 정의된다.

N = (Q, ∑, δ, q0, F)

• Q : state의 유한 집합
• ∑ : symbols(alphabet)의 유한 집합
• δ : transition function, δ: Q x (∑ ∪ {ε}) -> 2^Q
  • 2^Q : power set, 모든 부분집합을 포함하는 집합
• q0 : start state
• F : final state의 집합, F ⊆ Q

모든 state p ∈ Q 및 input a ∈ ∑ ∪ {ε}에 대해, state 집합 δ(p, a)의 부분집합은 고유하게 결정된다.

• 주어진 입력에 대해 주어진 상태에서 다중 전환을 허용한다.
  

  

  
  
• 입력 ε에 대한 transition 허용

 

NFA for strings ends with abb

ex1) Regular expression: (a+b)*abb

- state diagram

- NFA : N = (Q, ∑, δ, q0, F)

• Q = {q0, q1, q2, q3}
• ∑ : {a, b}
• q0 : start state
• F : {q3}
• δ : transition function, δ: Q x (∑ ∪ {ε}) -> 2^Q (모든 부분집합)
  ε이 포함되어있다. -> 아무 입력을 받지 않더라도 다른 상태로 이동할 수 있다.
  

δ	a	b
q0	{q0, q1}	{q0}
q1	ø	{q2}
q2	ø	{q3}
q3	ø	ø

• {q0, q1}
  • 2^Q의 부분집합 중 하나
  • 부분 집합 중 하나가 uniquely determine 된 것
• A tree of computation paths

* Accepting state에 하나라도 도착시 인식된다. 아니면 reject

이를 코딩한다 생각해보자. 언제 어느 방향으로 가는지 구분이 불가능하다.

이를 위해 NFA를 DFA로 변환할 것이다.

* NFA와 DFA가 인식하는 Language가 다를까?

• L(NFA) > L(DFA)? (X)
• 표현력 L(NFA) = L(DFA)? (O) : NFA 만든 후 DFA로 변환시
• NFA가 표현한 L은 반드시 대응하는 DFA가 존재한다.

 

NFA for strings ends with abb

- 세 종류의 computation paths가 있다.

1. reject state로 끝나는 input w의 path
2. w의 적절한 접두사에 있는 경로로 계산이 중단된다.
3. accepting state 상태로 끝나는 input w의 path

- NFA에 대한 허용 기준은 매우 관대하다.

• 문자열 w가 computation paths 트리가 accepting path를 포함한다면 accept된다.
• w가 모든 computation paths에서 실패한다면(accepting state에 도달하지 못 한다면) reject된다.

 

Language L(N) accepted by N

NFA N = (Q, ∑, δ, q0, F)이 주어졌을 때, extended transition functions은 δ*: Q x ∑* -> 2^Q 로 정의된다.

a ∈ ∑, u ∈ ∑*에서

NFA N = (Q, ∑, δ, q0, F)이 주어졌을 때, N으로부터 수용 또는 인식되는 language L(N)은 language다.

L(N) = {w ∈ ∑* | δ*(q0, w) ∩ F != ø}

---

ε-closure (ε-closure(S))

모든 p ∈ Q에 대하여 state NFA N = (Q, ∑, δ, q0, F)가 주어질 때,

ε-closure of p, ε-closure(p)는 state q로 구성되어 있는데, p로 부터 q로 가는 path가 있을 때, 어떤 ε-path에 의해 갈 수 있는 q들이다.

-> q : p 또는 p로부터 시작해 ε이 가진 모든 label

• ε-closure(p) = {p} ∪ {q ∈ Q | ∃s ∈ ε-closure(p), q ∈ δ(s, ε)}
• ε-closure(S) = U_(s ∈ S)ε-closure(s) -> 모든 subset을 Union 한 것

 

ε-closure example

• ε-closure(A) = {A, B, D}
• ε-closure({A, C}) = ε-closure(A) ∪ ε-closure(C) = {A, B, D} ∪ {C, D} = {A, B, C, D}
  
• 자기 자신과 ε으로 갈 수 있는 state

 

Definition of the extended transition function δ*

NFA N = (Q, ∑, δ, q0, F)가 주어졌을 때, extended transition function δ* : Q x ∑* -> 2^Q은 다음과 같이 정의된다.

• 모든 p ∈ Q, u ∈ ∑*, a ∈ ∑
• Basis : δ*(p, ε) = ε-closure({p})
• Induction : δ*(p, ua) = ε-closure(U_s∈δ*(p, u) δ(s, a))
  • p에서 u로가는 모든 집합에 속하는 s들 중, a로 갈 수 있는 모든 것들을 구해 ε-closure 하는 것
• δ*(p, w)는 p로부터 시작해 w를 인식했을 때 도달하는 모든 state의 집합이다.

 

Language L(N) accepted by NFA N

extended transition function δ* : Q x ∑* -> 2^Q을 정의한 이유는

NFA N = (Q, ∑, δ, q0, F)으로 인식되는 language를 정의하기 위해서이다.

L(N) = {w ∈ ∑* | δ*(q0, w) ∩ F != ø}

• ∑*에 속하는 모든 w가 있을 때, start symbol에 extended transition fuction을 적용해 모든 w를 소모해 얻어지는 모든 state를 가지고 와 Accepting state와 교집합을 했을 때 공집합이 아니면 인식한다.

문자열 w ∈ ∑*가 accept된다는 것은, δ*(q0, w)이 final state를 가지고 있어 인식된다는 것이다.

 

DFA and NFA

NFA와 DFA가 인식하는 language는 동일하다. L(D) = L(N)

NFA가 표현한 L은 반드시 대응하는 DFA가 존재한다.

-> NFA를 DFA로 변환할 수 있다.

NFA	DFA