Programming Language & Automata 2 - DFA & NFA

Automata는 컴퓨터를 기호화하여 나타낸 것으로 생각할 수 있다. 입력에 대한 연산을 매 step마다 실행하고, 이에 대한 결과를 내는 형식이다. 이는 메모리가 제거된 폰 노이만 구조로 생각할 수 있다.

 

1. DFA

Deterministic finite accepter : 하나의 결과만을 내는 오토마톤. 따라서 이를 이용하여 주어진 문장이 해당 문법에 맞는지 아닌지를 알 수 있다. 

Identifier(식별자) : 언더바나 문자로만 시작해야 한다. 이를 이용하여 그래프를 그리면 DFA로 주어진 어떤 단어가 변수명으로 올바른지 아닌지 알 수 있다. (3은 reject, 1, 2는 하나의 문자로 입력됨) 

DFA는 M=(Q, sigma, delta, q0, F) 로 나타낼 수 있다. 일반적으로 G=(V, T, S, p)이지만 여기서는 5개의 요소를 사용한다. Q는 finite set of internal state, sigma는 input alphabet finite set, delta는 total function(함수 도메인이 x의 집합 전체인 경우)인 transition function이다. Delta = Q * sigma -> Q 로 나타낼 수 있고, 이는 cartesian product이므로 Q의 상태가 다른 상태로 변하는 것을 나타낸다. (sigma의 크기와 internal state의 크기를 곱한 만큼의 transition이 존재한다!) Q0는 Q에 포함된 initial state이고, F는 Q에 포함된 final state의 set이다. 

Final state는 결국 DFA가 해당 문장을 검사하여 유효한지 아닌지를 나타내는 yes/no로 출력된다. 여러 개의 transition rule이 있으므로 현재 상태와 input symbol에 따라 결정된다.
 

DFA는 문자열의 가장 왼쪽 문자부터 순서대로 읽는다. 따라서 문자열을 다 읽었을 때 transition function에 의해 변환된 initial state가 final state set에 포함되지 않으면 reject 되게 된다. (DFA의 state가 transition function에 의해 변환되고, 원하는 state set에 포함되어야 해당 문장이 문법에 맞는 것!)

Delta(q0, a) = q1 : transition의 예시. DFA의 현재 상태가 q0이고, 현재 읽는 문자가 a이다. 이들을 transition function에 넣어서 얻은 결과는 DFA의 다음 state q1이 된다. 따라서 다음 문자를 읽을 때는 q1이 들어가게 된다.
Transition graph : finite automata를 시각적으로 나타내는 방법. Vertices = state ( initial state는 source node가 없는 화살표가 들어오는 곳, final state는 두 개의 동심원으로 표현) edge는 transition 이고 각 노드와 간선에 붙은 이름은 state의 이름과 현재 input symbol의 값이다. DFA M에 대한 transition graph는 Gm으로 나타낸다.
 

*를 붙이면 사이에 있는 반복되는 연산을 생략하는 효과이다. 따라서 delta* = Q * sigma* ->Q이다. 이 때 sigma*는 하나의 alphabet이 아니라 두 개 이상의 alphabet으로 이루어진 sentence일 수 있다. 따라서 이를 extended transition function이라 한다. 즉, 서로 다른 알파벳 a, b에 의한 transition이 있을 때, 이를 합쳐서 delta*(q0, ab) = q2로 나타낼 수 있다는 것이다. (a와 b를 차례대로 넣어서 q0 가  q2가 될 때 이 두 개의 연산을 합쳐서 하나로 표현)
앞서 lamda는 empty string이므로 delta*(q, lamda) = q ( 재귀)이다. 마찬가지로, extended의 정의를 재귀적으로 나타내면 delta*(q, wa) = delta(delta*(q, w), a) 로 나타낼 수 있다. (w는 또다른 한 개 이상의 알파벳이 합쳐진 string)

종합하여 나타내면, 어떤 grammar G와 sigma로 만들어 낼 수 있는 모든 가능한 문장 L(G)은 L(M) = {w < sigma* : delta*(q0,w)<f}로 나타낼 수 있다. 즉, sigma로 만들어 낼 수 있는 문장 조합 중, DFA의 transition이 final state 인 문장만 해당 grammar에 알맞다는 것이다. 이와 반대로, DFA의 final state에 있지 않다면 이는 해당 문법에 맞지 않는 문장이다.
간선에 알파벳이 쉼표로 이어진 것은 그냥 각각을 합쳐서 나타낸 것으로 각 알파벳의 transition이 각각 동일한 곳으로 이어진 것을 축약해서 나타낸 것이다. 따라서 서로 다른 두 개의 간선으로 나누어도 동일하다.
Final state가 아니지만 한 번 들어가면 나올 수 없는 간선들을 가지는 노드(잘못된 문법으로 작성된 문장들이 가는 곳)를 trap state라 한다.
 

DFA와 transition graph는 서로 변환 가능하다. (서로 다른 graph가 가능할 수도 있다. 물론 최적인 트리는 정해져 있지만 어떻게 표현하던지 상관없다) 해당 이론의 정확한 내용은 어떤 DFA의 transition function이 qi -> qj로의 이동을 나타낼 수 있으면 parse tree에도 노드 qi와 qj사이에 walk가 있어야 한다는 내용이다.
어떤 언어 L에 대해 DFA가 존재할 때(L=L(M)) L은 regular라고 한다. 따라서 정규언어 L이 있으면 DFA를 만들 수 있다. 또한 transition graph도 그릴 수 있다.

2. NFA

Nondeterministic Finite Accepter(NFA) : DFA와의 차이점은 움직임의 선택 방식이다. DFA에서는 모든 스텝에서 정해진 노드와 경로가 정해져 있다. 그러나 여기서는 몇 가지 가능한 사례들이 존재할 수 있다. 따라서 transition function delta가 DFA에서는 input 하나에 output 하나로 결정되지만, NFA에서는 어떤 input이 주어지면 가능한 집합을 반환하게 된다. 그래서 multiple internal state가 가능하다. 주어지는 결과는 Q의 power set이므로 공집합일 수도 있다. 따라서 transition의 반환값이 공집합이면 어떤 walk는 공집합으로 label 될 수도 있다. (Power set : empty set을 포함한 모든 부분집합)

NFA도 동일하게 주어진 string이 끝날 때 machine이 final state에 있을 때만 받아들이고 그렇지 않으면 거부한다. 동시에 final state로 possible sequence가 없으면 거부된다. 그러나 가능한 경로가 여러 개 있을 수 있으므로 이는 직관적인 방법으로 사료된다. (intuitive insight) 결국 하나의 입력에 서로 다른 state 출력이 가능하므로 여러 개의 final state가 결정될 수도 있다. 이러한 특성(or)을 사용할 수 있어서 nfa를 사용한다. 

NFA에서도 extended transition function delta*가 있다. 이는 DFA와 동일하게 적용된다. 마찬가지로 앞서 말한 것처럼 delta*(q0 , w)의 결과와(q0는 시작 state, w는 모든 가능한 string) final state F의 교집합이 공집합이 아니면(겹치는 부분이 있으면) 해당 string w는 문법에 맞는다(accepted).

실제 컴퓨터는 input에 의해 상태를 예측할 수 있으므로 DFA로 가정할 수 있다. 그러나 NFA의 개념을 배우는 이유는 search & backtracking (trail & error)를 할 수 있기 때문이다. 이를 이용하여 최적의 수를 찾을 수 있고, DFA는 NFA로 표현 가능하므로 최적의 DFA를 만들 수 있게 된다. 그리고 문제 해결 및 복잡한 언어 기술에 필요한 경우도 있다.

 

이 둘은 서로 다른 것이라고 생각할 수 있지만 실제로는 서로 상호 변환 가능하다.

Equivalence of DFA, NFA : 어떤 언어 L를 서로 다른 finite accepter가 받아들이면 두 accepter는 equivalent 하다고 할 수 있다. L(M1) = L(M2). 즉, 어떤 nfa든 동일한 dfa로 변환할 수 있다. 

NFA가 어떤 string w를 읽을 때 여러 가지 출력이 가능하므로 possible state의 set 중 하나의 상태에 있을 것이라는 것을 알 수 있다. 그러나 DFA는 반드시 어떤 상태에 있다는 것을 예측가능해야 한다. 따라서 이를 해결하기 위해 가능한 여러 state의 set을 ({q0, q1 … q}) single state라고 생각한다. 

즉, NFA에서 가능한 여러 state를 하나의 노드에 합쳐서 하나의 state로 고려하는 것이다. 만약 해당 state에 포함된 원소 중 하나가 NFA의 final state라면, 그 집합을 하나의 노드로 합친 DFA의 노드 역시도 final state가 된다. NFA의 final state가 여러 집합에 포함될 수 있으므로 DFA의 final state도 여러 개가 생성될 수 있다. 해당 노드가 단일이더라도(시작 노드 처럼) 하나의 state를 포함하는 집합으로 나타낸다. Q1 -> {q1}