'수학/오토마타'에 해당되는 글 2건

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의 구성요소는 다음과 같이 정리 할 수 있다.

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다.

예제)

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

이 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 되는지 판단해라.

풀이

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는 다음과 같이 표현한다.

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

예시)

이 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,Σ,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들을 정의해라.

정답)

풀이)

을 살펴보자면, 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

강의자료

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

1.1 오토마타 관련 기본 수학

 - 집합이론

 - 트리와 그래프

 - 기본적인 증명법들(귀납법, 연역적 추론법, 반례)

1.2 Language, Grammar, Automata 개념

2. 집합(Set)

집합이란? 

- 서로다른 대상들이 모여 이루는 새로운 대상.(https://ko.wikipedia.org/wiki/%EC%A7%91%ED%95%A9)

집합 관련 기호

- 포함관계(Membership)

집합 표현 예제

집합의 Powerset

Powerset 2^S는 집합 S의 모든 subset의 집합이다.

집합 S = {a,b,c}에 대하여 집합 S의 Powerset 2^S = { {}(공집합), {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} }

드모르간의 법칙

Function

: 집합을 입력으로 받고 하나의 숫자를 출력으로 내는 함수.

Relation

: S X S의 임의의 서브클래스

3. 그래프

그래프는 2개의 유한 집합 Vertices, Edges로 구성됩니다.

4. 트리

트리는 그래프의 일종으로, Cycle이 없는 Directed Graph입니다.

5. 증명법

- 연역적 추론(모든 인간은 죽는다. 소크라테스는 인간이다. 따라서 소크라테스는 죽는다.)

- 귀납법(소크라테스는 아테네인이다. 소크라테스는 철학자이다. 그러므로 모든 아테네인들은 철학자다.)

- 반례제시(소크라테스는 죽지 않는다. 따라서 모든 인간이 죽는것은 아니다.)

6. Language

6.1 용어 정리

- Alphabet 

Symbol(a,b,c,...)들로 구성된 유한한, 비어있지 않은 집합 ∑

- String

유한한 갯수의 Symbol들이 연속으로 이어진 것

- Concatenation

두 개의 스트링을 잇는다.

- Reverse

뒤집기

- Length

스트링의 길이

- Empty String  λ

비어있는 문자열을 나타내는 람다문자

- Substring, Prefix & Suffix

- Repeats

반복

- Infinite Alphabets

ex1)

라고 하면

이다.

ex2) 

집합 

의 Language이고,

Finite Language이다.

ex3)

집합 은

의 Language이고,

Infinite Language다.

- Language의 일반적인 정의

Language L은 일반적으로  의 Subset으로 정의된다.

7. Grammars

7.1 Grammar란?

- Language를 표현하기 위한 메커니즘

Grammar G는 다음의 quadruple로 표현된다.

• G=(V,T,S,P).

• V : 변수, 유한한 객체의 집합.

• T : Terminal Symbol. 유한한 객체의 집합.

• S V: Start Variable. 특별한 Symbol

• P: Productions. 유한한 객체의 집합

• V와 T는 비어있지 않고, disjoint하다.

7.2 Production Rule 이란?

- Grammar가 String을 어떻게 변화시키는지를 나타내는 것.

- Grammar = Language + Production Rules

ex) Grammar G=({S}, {a,b}, S, P)이고, Production Rule P가

• S -> aSb

• S -> λ

라고 하면,

• S => aSb => aaSbb => aabb

7.3 Derivation

• x -> y

• w = uxv

• z = uyv

라고 하면

w => z 이다.(z is derived from w)

 : w1=>w2=>...=>wn (wn이 w1으로부터 derive 될 수 있다.)

7.4 Language

Grammar G=(V,T,S,P)에 의해 생성되는 Language는

이다.

ex) Grammar G=({S}, {a,b}, S, P)이고, Production Rule P가

• S -> aSb

• S -> λ

라고 하면,

G의 Language 는 다음과 같다.