automata theory - 1. finite automata

1. Finite automata
Regular language을 정의하는 오토마타. Deterministic automata, non-deterministic automata는 서로 동일하다.
그 중 deterministic finite automata을 먼저 생각해본다.
 finite 한 state과 transition function, input symbols, start state, final state으로 이루어져 있다.
M = (Q, S, d, q0, F)

input string이 들어오면 transition function의 규칙에 따라 현재 state (첫번째 symbol을 읽을때는 start state에 있을 것이다.)에서 특정 symbol을 받았을 때 이동하는 state으로 이동한다.

예)
        |  0  |  1  |
---------------
->q0 | q2 | q0 |
*   q1| q1 | q1 |
   q2 | q2 | q1  |

->는 start state을 나타내고, *은 final state을 나타낸다.

i) input symbol : 011 일 때,
q0 state에서 (맨 앞 symbol) 0을 받는다. d(q0,0) = q2이므로 q2로 이동.
q2 state 에서 다음 symbol 1을 받는다. d(q2,1) = q1 이므로 q1으로 이동.
q1 state 에서 다음 symbol 1을 받는다. d(q1,1) = q1 이므로 q1으로 이동.
input symbol을 다 읽었을 때의 상태가 final state인 q1이다. 이러한 input string을 이 오토마타의 language라고 부른다.

ii) input symbol: 00
q0 state에서 (맨 앞 symbol) 0을 받는다. d(q0,0) = q2이므로 q2로 이동.
q2 state 에서 다음 symbol 0을 받는다. d(q2,0) = q2 이므로 q2으로 이동.
input symbol을 다 읽었을 때 상태가 final state이 아니다. 이러한 input string은 주어진 오토마타의 language가 아니다.

---------------------

두 오토마타가 같은 language을 표현한다면 두 오토마타를 같은 일을 하는 오토마타라고 부른다 (서로 동일하다).



위의 예시와 같이 특정 state에서 모든 가능한 input symbols에 대해서 하나씩의 transition state을 가지는 오토마타를 deterministic finite automata (DFA) 라고 한다.


finite automata 중에는 deterministic 하지 않은 것들도 있는데, nondeterministic finite automata(NFA) 라고 부른다. DFA와 비슷하지만 transition function의 함수값이 하나의 state이 아닌 state의 집합으로 나타내는 것이 다르다. (다시 말해, 어떤 state에서 symbol을 읽었을 때, 0개 이상의 state들로 동시에 이동이 가능하다).
epsilon-NFA는 받아들이는 symbol에 epsilon을 추가한 NFA이다. 즉 아무런 입력 없이도 한 state에서 다른 state으로 이동이 가능하다. (이러한 이동을 epsilon transition이라한다)



DFA와 epsilon-NFA는 서로 동일하다 (임의의 DFA을 동일한 일을 하는 epsilon-NFA로, 임의의 epsilon-NFA을 같은 일을 하는 DFA로 항상 바꿀 수 있다는 것을 의미한다).


---