2장 Finite Automata

1. 이번 장에서 다루는 내용

- Deterministic Finite Accepter (DFA)

- Non-deterministic Finite Accepter (NFA)

- DFA와 NFA의 공통점

2. Deterministic Finite Accepter (DFA)

2.1 Deterministic Accepters and Transition Graphs

DFA란?

- 컴퓨터란 무엇인가에 대한 가장 간단한 모델

- 많은 장치들은 DFA로 프로그래밍 되었다.(ATM, 자판기, 엘리베이터, 컴파일러 등등...)

- 관측 가능한 세상은 모두 Finite하다.

 모든 오토마타와 마찬기지로, Deterministic Accepter는 내부 States, 한 State에서 다른 State로 전환하기 위한 규칙, 입력, 그리고 결정을 내릴 방법들을 가진다.

 DFA의 구성요소는 다음과 같이 정리 할 수 있다.

• Q는 내부 State들이다.

• Σ는 Input Alphabet으로, Symbol들의 유한한 집합이다.
  

• δ : Q x Σ -> Q 은 transition function으로, total function이다..

• 는 initial state다.

• 는 final state다.

DFA는 다음과 같은 순서로 작동한다.

1. 처음에는 오토마타를 initial state q0상태라고 하고, 입력 스트링의 가장 왼쪽 심볼부터 처리한다(입력 메커니즘을 가장 왼쪽 심볼에 둔다.).

2. 오토마톤(오토마타의 단수형)의 각 이동마다, 입력 메커니즘은 오른쪽으로 한 포지션씩 이동한다. 여기서 한 번의 이동에 하나의 입력 심볼을 소비한다.

3. 스트링의 끝에 도달했을 때 오토마톤이 Final State들 중 하나에 있다면 String은 Accept 된다.

4. 스트링의 끝에 도달했는 때 오토마톤이 Final State에 있지 않다면 String은 Reject 된다.

예를 들어,

이라고 할 때, DFA가 q0 상태이고 현재 입력 Symbol이 a이면 dfa는 q1 상태로 전환 될 것이다.

2.2 Transition Graph

 오토마타는 깔끔하고 직관적으로 보여주는 것이 중요하다. Finite Automata를 시각화 하기 위해서 Transition Graph라는 것을 사용 할 수 있다.

 DFA의 요소들은 Transition Graph에서 다음과 같이 표현된다.

• Vertex - DFA의 State를 나타냄.

• Edge - DFA의 Transition을 나타냄.

• 2중원 Vertex - DFA의 Final Stat을 나타냄.

• Initial State는 특정 Vertex에서 출발하지 않은, 이름이 붙여지지 않은 화살표가 가르키는 Vertex로 표현된다.

DFA 을 나타내는 그래프 은 정확하게 |Q|개의 Vertex를 가지며 각각의 Vertex는 라고 이름 붙인다. q0에 매칭되는 Vertex가 Initial Vertex이고, 인 qf들은 모두 Final Vertex다.

 

예제)

순서대로 (States, Input Alphabet, Transition Function, Initial State, Final States)

위의 DFA는 다음과 같이 표현 할 수 있다.

출처 Formal Languages and Automata - Peter Linz

이 DFA가 01이라는 String을 입력받으면 다음의 순서로 진행된다.

1. q0 State에서 시작

2. Symbol 0를 먼저 읽게되고, 오토마톤은 q0->q0으로 이동하게 됨.

3. Symbol 1을 읽으면 오토마톤은 q0->q1로 이동하게 됨.

q1은 Final State이므로 01 String은 accept 된다.

같은 방식으로 00이라는 String을 입력하면 Reject된다.

2.3 Extended Transition Function

 Extended Transition Function 라는 것이 있다.

 의 2번째 Argument는 하나의 Symbol이 아닌 String이고, 의 값은 이 String을 읽고 난 후의 Automaton의 State를 나타낸다.

예시)

이면

이다.

을 재귀적으로 정의하기

Extended Transition Function()은 다음과 같이 정의 할 수도 있다.

예제)

다음의 Transition Graph를 보고 String w=abba 에 대해 를 계산하고 String w가 accept 되는지 판단해라.

출처 - 강의자료

풀이

q2는 Final State이므로 abba는 Accept 된다.

2.4 Language와 DFA

2.4.1 Language란?

Language는 오토마톤에 의해 Accept되는 모든 String들의 집합이다.

DFA 

의 Language L은 Σ에 속하는 String들 중 M에 의해 Accept 될 수 있는 모든 String들의 집합이다.

L은 다음과 같이 표현한다.

DFA는 의모든 String을 처리 할 수 있고, 그 각각의 String들을 Accept하거나 하지 않을 수 있다.

여기서 Accept되지 않는다는 것은 DFA가 FInal State가 아닌 State에서 끝났다는 것을 의미한다.

Accept되지 않는 Language는 다음과 같이 표현한다.

Trap State

한번 들어가면 빠져 나올 수 없는 State를 Trap State라고 한다.

예시)

출처 Formal Languages and Automata - Peter Linz

이 Transition Graph에서 오토마톤이 q2 State로 들어가면 빠져 나올 수 없다. 여기선 q2가 Trap State다.(Non-final Trap State)

2.5 Regular Language

 모든 유한 오토마톤은 어떤 Language를 Accept한다.

 어떤 유한 오토마타와 관련된 Language들을 묶어서 Family로 만들 수 있다.

 DFA에 의해 Accept되는 Language들의 Fmaily는 굉장히 제한된다. DFA에 의해 Accept되는 Family의 구조와 특성에 대해서는 계속 공부해나가다 보면 알게 될 것이다.

2.5.1 Regular Language란?

어떤 Language L에 대하여 L=L(M)을 만족하는 DFA M이 존재한다면 L이 Regular하다고 한다.

그래서 Language L이 Regular 하다는 것을 증명하기 위해서는 L에 맞는 DFA를 찾아야한다.

3. Non-deterministic Finite Accepter(NFA)

 Non-determinism이란 것은 오토마톤의 이동에서 하나의 선택을 의미한다. Non-deterministic하면 각 상황에서 한가지 이동을 제공하지 않고, 가능한 이동 방법 여러개를 제공한다. 이는 Transition Function가 하나의 State를 값으로 가지는 것이 아닌, 가능한 State들의 범위를 가지는 것으로 구현해낸다.

3.1 Non-deterministic Finite Accepter(NFA)란

 Non-deterministic Finite Accepter(NFA)은 다음과 같이 Quintuple로 정의된다.

• Q는 내부 State들이다.

• Σ는 Input Alphabet으로, Symbol들의 유한한 집합이다.
  

• 은 transition function으로, total function이다.(* 2^Q는 Q의 Powerset.)

• 는 initial state다.

• 는 final state다.

Q,Σ,q0,F는 DFA와 동일하고, δ(transition function)은 다르다.

DFA와의 비교

 이 정의는 DFA와 주요한 3가지 차이점이 있다.

 첫째로, Non-deterministic Accepter에서, δ의 범위는 2^Q(Q의 Powerset)에 포함되기 떄문에 δ의 값은 Q의 하나의 요소가 아니라 Q의 Subset이다. 이 Subset은 Transition에 의해 만들 수 있는 모든 State들의 집합을 정의한다.

 예를 들어, 현재 State가 q1이고 Symbol a를 읽어 냈을 때, δ(q1,a) = {q0,q2}라고 정의하면 q0, q2 둘 다 NFA의 다음 State가 될 수 있다.

 둘째로, λ를 δ의 두번째 아규먼트로 쓸 수 있다.

 이 말은 NFA는 Input Symbol을 소모하지 않고도 Transition을 일으킬 수 있다는 뜻이다. 지금까지 입력 메커니즘이 오른쪽으로만 이동 할 수 있는 줄 알았지만, 오토마톤이 이동해도 입력메커니즘은 움직이지 않는 경우도 있다.

 마지막으로, NFA에서 δ(qi,a)의 집합이 비어있을 수도 있다. 그런 경우에는 Transition이 하나도 정의되지 않은 경우다.

 DFA와 마찬가지로, Non-deterministic Accepter는 Transition Graph로 표현 할 수 있다. Vertex들은 Q에 의해 결정되고, a라는 이름의 Edge(qi,qj)는 δ(qi,a)가 qj를 포함할 때 Edge로 그래프에 포함된다.

 그리고 a는 빈 스트링일 수도 있으니까 λ라는 이름의 Edge도 존재 할 수 있다.

NFA에서 스트링이 Accept되는 조건

 NFA에서 어떤 스트링을 따라 머신을 이동하는 여러 경우의 수들 중 스트링의 끝에 머신을 Final State에 가게 만드는 경우의 수가 있다면 그 스트링으 Accept되고, 그런 경우가 없다면 Reject된다.

Transition Function 확장

 NFA에서도 Transition Function은 확장 될 수 있다. 그래서 확장된 Transtion Function의 두번째 아규먼트는 String이다.

 확장된 Transition Function인 에 대하여 를 수행한 결과로 오토마톤이 될 수 있는 모든 State들의 집합을 Qj라고 하고, 가 qi부터 시작되고 w 스트링을 읽는다고 하면 다음과 같이 표현한다.

예제)

다음의 Transition Graph를 보고 NFA의 Transition Function들을 정의해라.

출처 Formal Languages and Automata - Peter Linz

정답)

풀이)

을 살펴보자면, q2->q0로의 λ 라는 이름의 Transition이 존재한다. 그러므로 는 q0를 포함한다.

그리고 어떤 State든지 자기자신에서 움직이지 않고 머무를 수 있는데, 그 때는 Input Symbol을 소모하지 않는다. 그러므로 는 q2도 포함한다고 할 수 있다.

따라서 

을 살펴보자면, 

λ-λ-a-λ-λ 순으로 q1->q2->q0->q1->q2->q0 로 갈 수 있으니 q0를 포함한다.

λ-λ-a 순으로 q1->q2->q0->q1 로 갈 수 있으므로 q1를 포함한다.

λ-λ-a -λ  순으로 q1->q2->q0->q1->q2 로 갈 수 있으니 q2를 포함한다.

따라서 

Languages Accepted By NFA

NFA 에 의해 Accept되는 Language L은 다음과 같이 정의 할 수 있다.

4. DFA와 NFA의 동일함(Equivalence of DFA and NFA)

 

 DFA와 NFA는 어떤 점에서 다른가?

 물론 둘은 정의에서 부터 차이가 있다. 하지만 그 사실이 그 둘의 근본적인 차이가 있다는 의미는 아니다. 이 질문에 답하기 위해 오토마타 사이의 Equivalence라는 컨셉을 소개한다.

 

 정의

 두 유한 Accepter M1과 M2가 둘 다 같은 Language를 Accept하면 Equivalent하다고 한다.

 즉, 다음을 만족하면 M1과 M2는 동일하다.

Powerful

어떤 종류의 오토마톤이 다른 어떤 오토마톤으로도 달성 할 수 없는 것을 할 수 있는 오토마톤을 Powerful하다고 한다.

 DFA와 NFA를 비교해보면, 둘은 동등하게 Powerful하다.

 DFA는 NFA에 규칙을 더한 것이 때문에, DFA에 의해 Accept되는 String을 Accept 하는 NFA가 반드시 존재한다. 그 반대로 NFA에 의해 Accept되는 String을 Accept하는 DFA도 반드시 존재한다.

 그러니 모든 DFA, NFA에 대해 DFA->NFA, NFA->DFA로의 변경이 가능하다.

 

NFA->DFA 전환

NFA를 DFA로 전환하려면 NFA의 Transition Graph로 다음의 과정을 따라가면 된다.

1. 심볼을 따라 그래프를 따라간다.

2. Non-deterministic Transition에 대한 새로운 State를 추가한다.

3. 부족한 Edge들을 추가한다.

4. Final State를 포함하는 State들은 Final State로 한다.

5. Finite Automata에서 State의 수 줄이기

State의 수를 줄이려면 다음의 과정을 따라가면 된다.

1. State를 Final State와 Non-final State로 나눈다.

2. Transition들을 계산하고 식별불가능한 State들은 나눈다.

3. 더이상 나눌 필요가 없어질때까지 2번 과정을 반복한다.

레퍼런스

Formal Languages and Automata - Peter Linz

강의자료