4. Finite Automata

< 나오는 용어 >

 

• Finite Automata
• Accept, Reject, Target , Start state
• Regular Expression ( RE )
• Transition Function
• DFA, NFA , Minimal DFA
• Sombrero Construction

 

 

---

• Finite Automata
• DFA ( Deterministic finite automata )
• NFA ( Non Deterministic finite automata )
• Draw DFA, NFA ( NFA -> DFA -> Minimal DFA )
• Regular expression to NFA ( RE -> NFA )
• Question

 

---

Finite Automata ( 유한 오토마타 )

 

촘스키 위계

 

• Finite automata

- 간선이 alphabet sigma 로 부터 선택된 기호 문자인, 유한 전이 그래프 ( finite transition graph )

- 어떤 string or word 가 정규 언어 ( Regular L ) 인지 string 을 token 화 해서 판단하는 machine

- Determinstic / Non Determinstic Finite Automata 로 나뉜다.

 

※ 상태 다이어그램 ( state diagram )

기호의 흐름(stream) 또는 문장에 응답하는 동안 기계가 취할 수 있는 모든 가능한 상태와 전환을 나타낸 상태 다이어그램

 

 

---

DFA ( Deterministic Finite Automata )

 

• DFA 

- 결정적 유한 오토마타 

- 5-tuple 로 정의된다.

 

 

• Q : 유한한 상태 집합
• Σ : 알파벳 집합
• δ : 전이 함수  , δ : Q X Σ-> Q
• q0 : 시작 상태 
• F : 최종 상태집합

- 상태집합 Q 중 하나인 Q 와 알파벳 집합 중 하나인 Σ 가 pair 가 되어 다른 상태인 Q' 라고 전이

- 시작 상태는 하나지만, 최종 상태는 여러개 ( 집합 ) 가 될 수 있다.

- Cartesian product ( X ) : 두 집합 A,B의 원소들로 만들어지는 모든 순서쌍 (a,b)들의 집합

- 전이 함수에 의해 pair ( Q, a ) 가 특정한 ( 단 하나의, unique ) 다른 상태 Q' 로 전이된다.

 

 

예시 )

 

 

예시 (3) 의 경우 1이 연속되지 않는 문자열이다. 이것에 대해 다음과 같이 착각할 수 있다.

 

Q. 처음에 ( 0 + 10 ) * 에서 0을 선택하고, ( e + 1 ) 에서 1을 선택한 다음에 ( 0 + 10 ) 에서 다시 10을 선택하고 

( e + 1 ) 에서 1을 선택하면 01101 로 가능한것 아닌가?

 

=> 처음에 ( 0 + 10 ) * 에서 0을 선택하고, ( e + 1 ) 에서 1을 선택 / 한 순간 문자열이 끝나는 것이다.

계속 반복된다고 착각하지 말자. ( 0 + 10 ) * 이므로 0과 10, 그리고 입실론은 무한히 반복될 수 있고 , 그 뒤에 

입실론 또는 1이 옴으로써 문자열이 끝나는 것이다.

 

 

• Definition of δ * 

δ *  = Q X Σ* 

전이 함수를 여러번 한다는 뜻이다.

 

• L ( D ) 

- Language L 은 D 에 accept 되는 언어라는 뜻이다.

 

• 연습해보기

 

10011 은 다음과 같은 순서로 Accepting state 에 도달할 수 있다. 따라서 Language L에 속한다.

 

1100000 은 다음 그림처럼 q1 에서 종료되고 q1 은 Accepting state 가 아니므로 Language L 에 속하지 않는다.

 

 

---

NFA ( Non-Deterministic finite automata )

 

 

• NFA 

- NFA 도 5-tuple 로 정의된다. 

 

DFA 와 차이점은 전이 함수에 있다. 전이 함수의 식에서 보면 알 수 있듯이 DFA 랑 다르게 입실론과도 카테시안 곱이 가능하며, 특정한 Q' 로 전이되는 것이 아니라 최대 2^Q 의 상태로 전이된다. 2^Q는 Q의 power set , 모든 부분집합을 의미한다. 단, 그 집합자체는 unique 하다, 여러개의 집합으로 전이되지는 않는다.

ex. q0 -> { q0,q1,q2 } 로 전이된다면, q0 -> { q3,q4 .. } 의 set 은 존재할 수 없다.

 

NFA 예시

집합으로 전이하기 때문에 다음과 같은 트리구조를 가진다.

 

그렇다면 tree computation 에서  F ( final state ) 가 accepting 되는지 어떻게 알 수 있을까?

도달하는 단 하나의 leaf node ( = final state ) 가 accepting state 라면 그 string or word 는 Language 에 속한다고 할 수 있다.

이를 수식으로 표현해 정의하면 다음과 같다.

여기서 F 는 accpeting state 집합이고, 최종적으로 도달한 곳과 accepting state 의 교집합이 단 한개도 없다면 reject 그렇지 않다면 accept 이다.

 

• ε - closure 

정의는 굉장히 복잡한 말로 쓰여져 있는데, ε 으로 갈 수 있는 모든 state set 으로 이해하면 된다.

 

• Definition of δ* 

DFA 랑 다르게 p 가 아닌 Us 인 것은, NFA 의 경우에는 Q 에서 δ 에 의해 다른 상태로 바뀔 때 특정 상태 Q' 라고 바뀌는 것이 아니라 특정 집합 Q set 으로 전이되기 때문이다.

 

 

 

---

Draw DFA, NFA ( Regular expression ) 

 

어떤 Regular expression 이 주어지면 먼저 이것을 NFA 로 그린 후 , DFA 로 바꾼다. 그리고 DFA를 minimal 하게 줄인다.

 

• NFA to DFA

- 시작 상태 s 에 대해서 ε 으로 상태전이가 되는 모든 상태 집합을 A 라고 한다.

- 이후 [ 상태집합 ] 의 집합 D 에 A를 넣는다.

- D에서 A를 꺼내고, 특정 alphabet 과 전이 함수를 이용해 다음으로 갈 수 있는 집합 B를 만든다.

- 집합 B에 대해 ε 으로 상태전이가 되는 모든 상태들의 모음으로 B를 재정의하고, D에 B를 넣는다.

- A 의 원소들과 pair 를 이루는 전이함수가 있는 모든 alphabet 에 대해 수행한다. 

- 위 과정을 하면 D = { B,C,....} 의 상태집합들이 모인다.

- D 에서 가장 먼저 넣은 상태집합을 꺼내면서 위 과정을 반복한다.

- D 가 빌 때까지 반복하고, D가 비면 종료.

 

 

※ 과정

 

 

• DFA to Minimal DFA ( 간소화 )

 

1. Reachability (도달가능성) 확인하기 

- start state q0 에서 시작해서 도달할 수 없는 state 들과 그 transition function은 전부 제거한다.

위 diagram 에서 시작 state 0 에서 2,3,4,는 도달할 수 없다. 따라서 전부 지워준다.

제거된 모습

 

2. State Equivalence ( 동일 상태 )

- 동일 상태를 찾는다.

- 찾았으면 둘을 합쳐준다.

 

※ 동일 상태 찾기

• non accept state 를 class1 , accept state 를 class2로 둔다.
• 클래스 1에 있는 state 들이 transition function = { a,b,c....} 에 의해 도달하는 class 를 표로 정리한다.
• 특정 state들이 transition function 에 의해서 다른 class 의 state 로 간다고 하자
• 그렇다면 특정 state 들을 class2 로 두고, accept state 를 class3로 둔다.
• 위 과정을 반복한다.
• 반복하면서, 더 이상 특정 state 들이 추가로 나오지 않았다고 하자
• 이 때 임의의 state M,N 이 서로 같은 transition function 에 의해 같은 state 또는 class 로 이동하는 경우가 있다면 둘은 동일 state 이다.

Find Equivalance state

 

---

Regular expression to NFA

 

 

먼저 우리가 배운 Regular expression 의 표현에 대해 살펴보자.

우리는 어떤 Regular L 에 속하는 R이 있다고하자. 그렇다면 우리는 다음과 같은 연산을 진행했다.

 

1. R + R'           2.   RR'       3. R*

 

즉, 이 3개의 표현만 NFA 로 나타낼 수 있다면, 우리는 Regular expression 을 NFA 로 표현할 수 있다.

 

• Regular expression to NFA by Sombrero Construction

- 먼저 start state 와 target(accept) state 를 그리고 둘을 ε 으로 연결해준다.

 

1. R + R'

- 새로운 state s1과 t1을 만든후 s1 -> t1 으로 trainsition funcion R에 의해 이동한다. 라고 기록한다.

- 똑같이 R' 에 대해서 수행한다.

- start 에서 s1과 s2로 각각 ε 으로 연결해준다.

- t1,t2 에서 각각 ε 으로 target state 로 연결해준다.

 

2. RR'

- 새로운 state s1과 t1을 만든후 s1 -> t1 으로 trainsition funcion R에 의해 이동한다. 라고 기록한다.

- 똑같이 R' 에 대해서 수행한다. 여기서 만든 state 를 s2 , t2 라고 하자

- t1 과 s2를 ε 으로 연결해준다. 그럼 전체적인 모양은  s1---R--->t1----ε---->s2----R'--->t2 가 된다.

- 이제 start state 와 s1을, t2와 target 을 각각  ε 으로 연결해준다.

 

3. R*  ( 그림 참조 )

 

위 1~3을 글로 읽으면 무슨 말인지 이해하기 어렵다. 그래도 조금이라도 이해에 도움이 되기 위해 적어놓았다.

그림을 보고 글을 읽어도 좋고, 글을 읽어보고 그림을 봐도 좋다. 아래 그림을 봄으로써, 대략적인 틀이 이해가 갈 것이다.

 

R+R'&nbsp; , RR'

a*

 

※ RE -> NFA 예시

 

 

---

Question. 

 

배우면서 생겼던 의문

 

• Q. Regular Language 가 counting 될 수 없는 것의 증명

 

• Q. Automata , Grammar 와 Language 간의 관계

A1.  어떤 Language 를 규정하는 rule = grammar 

A2.  어떤 string 또는 word 가 Langauge L 에 속하는지 판단하는 machine = Automata

 

• Q. DFA 의 transition function 에는 ε 이 없는가? NFA 만 존재하는가?

A. 그렇다. 이유는 앞에 글을 읽어보면 알 수 있다. 혹시 설명이 부족하거나 없다면 구글링....

 

• Q. 어떤 regular expression 은 모두 DFA, NFA 로 그릴수 있는지, 그 이외의 언어 ( Context -free ) 는 불가능한가?

A. 모든 RE는 DFA, NFA 로 표현할 수 있다. 또한 그 외의 언어는 불가능하다. 교수님께서 그 이유까지는 설명해주시지 않았다. 심화 내용도 있고, 컴파일러 중후반부에 따로 배운다고 하셨다. 더 알아보고 싶다면 관련 서적을 구매해서 보라고 하셨다.

 

• Q. DFA 로 그릴 수 있는 모든 상태 diagram 은 NFA 로 그릴수 있고 반대도 성립하는가? 

A. 그렇다. 단, RE 에서만 가능하다.

 

• Finite Automata 는 NFA나 DFA나 똑같이 인식하는가?

A. 그렇다.  RE 내에서는, NFA나 DFA나 똑같은 상태에 대해 다른 표현한 것일 뿐이다.

인간의 입장에서는 NFA 는 코딩하기 어렵다. 어떤 상태에서 똑같은 transition function 을 받아 또 다른 상태 '집합' 으로 이동한다. 이걸 코딩하려면 if else 문을 수십개에서 수백개를 써야한다. 

예를 들어 transition function 을 a, a, a 로 받는건 가능하고, a,a,b 는 불가능하다고 하면  < 다음 문자가 a일 떄 다음 문자가 a이고 다음문자가 b이면 거절 a이면 수락...> 이런식으로 if else 문을 8개도 넘게 만들어야 한다.

하지만 DFA의 경우 transition function 대해  다른 특정한 '상태' 로 이동하므로, if / else 단 2개만으로 구별할 수 있다. 즉 이진트리 모양으로 만들어 낼 수 있다.

 

요약 : NFA --> 자식이 여러개인 트리  , DFA --> 이진 트리