[과제물] 유한 오토마톤 (finite automaton)의 정의 및 공식 설명

목차

1. 유한 오토마톤(finite automaton : automaton은 automata의 단수형이다) 란?
2. 기본정의

본문내용

1. 유한 오토마톤(finite automaton : automaton은 automata의 단수형이다) 란?
이산적인 입력과 출력을 갖는 시스템의 수학적인 모형이다. 이 시스템은 유한한 개수의 내부의 형태(configuration)들, 혹은 “상태(state)"들 중의 하나에 있다. 시스템의 상태는 이 다음의 입력에 대한 시스템에 대한 시스템의 행동을 결정하는데 필요한 지금까지의 입력에 한 정보를 요약해서 나타내고 있다.

우리는 사람의 두뇌도 유한 상태 시스템으로 간주할 수 있다. 뇌세포 혹은 신경 단위 세포(neuron)는 아마 최대로 235개 이내이다. 비록 반론이 있을 수 있지만 각 신경 단위 세포의 상태는 적은 개수의 비트(bit)로서 나타낼 수 있다고 생각할 수 있다.

2. 기본정의
유한 오토마톤(finite automaton : FA)는 유한한 상태들의 집합과 변환(transition)들의 집합으로 구성된다. 여기서 변환이란, 알파베트 Ξ에서 취해진 입력 부호(input symbol)에서 생기는 상태에서 상태로의 변화이다. 각 입력 부호마다, 각 상태에서부터 꼭 하나의 변환이 있다. (원래의 상태로 다시 돌아가는 변환도 있을 수 있다). 보통 q0로 나타내는 한 상태를 최초 상태라고 한다. 이 최초 상태에서 그 오토마톤이 시작하게 된다. 또 어떤 상태들은 최종 상태 혹은 수락 상태(acceptin state)들로 지정된다.

<중 략>

(기초 단계) (연산자가 하나도 없는 경우) 정규 표현이 ?, 혹은 A이어야 한다. 단, a ∈ Σ이다.

(유도 단계) (하나 이상의 연산자가 있는 경우) 정리 2.3이 I보다 적은 개수의 연산자가 있는 정규 표현에 대해서 사실이라고 가정하자. 단, i≥1이다. r이 i개의 연산자를 갖고 있다고 가정한다. 그러면 r의 형태에 따라서 다음과 같은 세가지 경우가 있다.

[정리 2.4] 만약 L이 DFA에 의해 수락된다면, L은 어떤 정규 표현에 의해 표시된다.
(증명) L이 M=({q1, …, qn}, Σ, δ, q1, F)인 DFA에 의하여 수락되는 집합이라고 하자. Rkij를 다음과 같은 모든 스트링들 x의 집합이라고 하자. y가 스트링 x의 임의의 prefix라고 하자. 여기서 y는 x 혹은 ?이 아니다. δ(qi,x)= qj이며, 만약 δ(qi,x)= ql이면 l≤k이다. 즉 Rkij는 k보다 큰 숫자의 상태를 거치지 않고 상태 qi에서 qj로 가는 유한 오토마타를 택하는 모든 스트링들의 집합이다.

참고 자료

없음