유한 오토마타 - 상태전이도 & 형식적 표현

오토마타

- 디지털 컴퓨터의 추상적 모델

- 입력 자료를 읽는 기능, 출력 기능, 무한 개의 기억 소자(cell)로 이루어진 일시 기억 장치, 유한 개의 내부 상태 중 하나를 제어하는 제어 장치(control)로 구성

 

기능적인 측면에서 인식기(accepter)와 변환기(tranducer)로 구분

- 인식기의 경우 입력된 결과에 대해 오토마타는 인식/기각(accept/reject) 등을 표시하는 이진 기호를 출력

- 언어 변환기는 주어진 입력에 대응하는 새로운 문자열을 출력

- 변환기에는 상태에 따른 출력을 내는 Moore 기계와 전이에 따른 출력을 내는 Mealy 기계 등

 

결정적 오토마타(Determinisitic automata)와 비결정적 오토마타(non-deterministic automata)로 구분

- 결정적 오토마타는 한 상태에서 하나의 입력을 받았을 때 다음 상태가 유일

- 비결정적 오토마타는 한 상태에서 하나의 입력을 받았을 때 다음 상태가 두 개 이상

 

---

 

유한 오토마타

어떤 알파벳 Σ로부터 만들어지는 문자열의 특별한 것들을 받아들이는 시스템의 수학적 모델, 그 시스템에서 변화할 수 있는 상태가 유한 개인 것

- 컴퓨터의 여러 분야에서 널리 사용.. 플립 플롭, 형식 연어 연구, 컴파일러 등

- 컴파일러 중 어휘분석기 -> 유한 오토마타의 대표적인 것

 

표현 방법

- 상태 전이도(state-transition diagram)와 같이 비형식적으로 표현하는 방법

- 형식적으로 표현 : 5가지 구성 원소들로 표현

 

상태전이도

- 오토마타의 각 상태(state)를 노드(node)로 표현

- 이동함수 δ(q,a) = p에 대해서는 상태 q에서 p로 가는 라벨이 a인 간선으로 표기

- 최종 상태들은 이중원으로 나타내고, 시작 상태는 시작 간선으로 표시하는 유향 그래프

 

ex.

(a + b)*aab를 인식하는 유한 오토마타를 상태 전이도로 표현

예시.. aabb를 인식할 수 있는가?

시작 상태 q0에서 a 입력 받으면 q0 유지

다시 a받으면 q1 전이

b 받아서 q2, b받아서 q3로 전이

-> 주어진 유한 오토마타에 의해 인식됨

 

---

 

유한 오토마타의 형식적 정의

- 유한 오토마타를 형식적으로 표현하면 5 튜플로 구성

- 유한 오토마타를 M이라 하면

M =(Q, Σ, δ, q0, F)

- Q : 상태들의 유한 집합

- Σ : 입력 기호들의 유한 집합

- q0 : 시작 상태로, q0 ∈ Q

- F : 종결 상태들의 유한 집합, F ⊆ Q

- δ : 전이 함수(transition function)로, Q x Σ -> 2^Q (Q의 멱집합.. 유한 오토마타가 0, 1 기호 쓰니까 2의 Q제곱)

       * 즉 δ(q, a) = {P1, P2, ..., Pn}  단, {P1, P2, ···, Pn} ⊆ Q

 

 

(a + b)*aab를 인식하는 유한 오토마타를 형식적으로 표현

유한 오토마타를 M이라 하면

M =(Q, Σ, δ, q0, F)

단,

Q = {q0, q1, q2, q3}

Σ = {a, b}

δ:

δ(q0, a) = {q0, q1}

δ(q0, b) = {q0}

δ(q1, a) = {q2}

δ(q2, a) = {q3}

 

q0 = q0

 

F = {q3}

 

이 경우 간단히 표현 되지만,

전이 함수는 매우 길어질 수 있음-> 상태전이표(state transition table)- 유한 오토마타의 상태 전이를 행렬로 나타낸 것- 행: 상태 집합- 열: 입력 기호- 행과 열이 교차하는 위치에 다음 상태를 기록- 상태와 입력에 핻강하는 위치에 값이 없다면 그 위치에 ø을 넣음

 

첫번째 기호가 영문 소문자, 두번째 기호부터는 영문 소문자나 숫자이며 길이에 제한이 없는 유한 오토마타 상태전이표

δ	a	b	c...z	0	1	2...9
q0	q1	q1	q1...q1	ø	ø	ø... ø
q1	q1	q1	q1...q1	q1	q1	q1

 

상태 전이 함수의 형태에 따라 결정적 유한 오토마타(Deterministic Finite Automata, DFA)와

비결정적 유한 오토마타(Nondeterministic Finite Automata, NFA)로 구분