코딩을 몰라도 이해할 수 있는 오토마타 이론 맛보기.

(출처 : https://en.wikipedia.org/wiki/Automata_theory)

(automata는 automaton의 복수형이다.)

오토마타는 특정 state에서 시작하여, string을 받으면 그 string의 첫 symbol과 처음 state에 따라 다음 state로 넘어가고, 다음의 state에서 처음 string의 다음 symbol을 받아서 또 그 다음 state로 넘어가는 과정을, string의 symbol이 모두 소진될 때까지 진행하는 알고리즘인 듯하다.

여기서 소개할 것은 오토마타 중 가장 간단한 형태의 오토마타이다.

-Deterministic Finite state automata (결정적 유한 상태 오토마타)

결정적 유한 오토마톤(Deterministic finite state automaton)은 (Q, B, f, q_0, F)의 5-순서쌍인데, 이때,

Q는 유한 집합이고, Q의 원소를 state라고 한다.

B는 유한 집합이고, B의 원소들을 symbol이라고 한다.

f는 f : A×B->A 이고, transition function이라고 한다.

q_0는 Q의 원소로, start state라고 한다.

F는 Q의 부분집합이고, accept state라고 한다.

-Input word(입력 단어)

string은 symbol들의 유한-순서쌍이다. 즉, {a | a는 B에 대한 string} B*=U(B^n) (n은 0 이상의 정수), (B^0은 원소의 개수가 1개인 집합으로, 그 원소를 empty string이라고 한다.)

(참고로, *를 Kleene star라는 이름의 1항 연상으로 봐서, 임의의 집합 A에 대해, A*를 A의 원소들로 이루어진 모든 순서쌍들의 집합으로 종종 본다고 한다.)

-Run(동작, 실행)

n을 자연수(0 포함), w=(a_1,a_2,....,a_n)∈B*, s=(q_0, q_1, ... , q_n)∈Q^n라고 하자. (q_0는 start state)

그러면, q_i=f(q_i, a_i)를 모든 n 이하의 양의 정수 i에 대해 만족할 때, s를 입력 w에 대한 automaton의 실행(run of the automaton on an input word w)이라고 한다. 그리고 q_n을 s의 종결 상태(the final state)라고 한다.

(lemma : 임의의 w∈B*에 대해, run of (Q, B, f, q_0, D) on w는 유일하게 존재한다.)

-Accepting word

w∈B*, s를 run of (Q, B, f, q_0, D) on w라고 하자.

q_n을 s의 the final state라고 하자.

그러면, q_n∈F 일 때, w는 accepted by the automaton (Q, B, f, q_0, D)이라고 한다.

-Recognized language (인식되는 언어)

L⊂B*라고 하자. 그러면, L={ w | w is accepted by the automaton (Q, B, f, q_0, D)}을 the language recognized by an automaton (Q, B, f, q_0, D) 이라고 한다.

-Recognizable languages(인식 가능한 언어)

L을 어떤 automaton에 의해 recognized language라고 하자.

그러면, K⊂L일 때, K를 the recognizable language 라고 한다.

그리고 L이 위의 automaton (Q, B, f, q_0, D)에 의해 인식되는 언어라면, K를 regular language 라고 한다.

(automaton의 정의가 달라지면 Recognizable language도 다르다. 공집합도 regular language이다.)