유한 오토마타 : 어떤 알파벳 T로부터 만들어지는 문자열의 특별한 것들을 받아들이는 시스템의 수학적 모델로서, 그 시스템이 변화할 수 있는 상태가 유한개인 것
비결정적 유한 오토마타 : 어떤 상태에서 주어진 하나의 입력기호를 보고, 갈 수 있는 다음 상태가 두개 이상 존재할 수 있는 유한 오토
마타
결정적 유한 오토마타 : 하나의 입력문자열에 대하여 오직 하나의 다음 상태가 결정되는 것
상태전이도 : transition diagram, 오토마타의 각 상태(state)를 노드(node)로 나타내며, 이동함수 δ(q,a) ＝p에 대해서는 태 q에서 p로 가는 레이블(label)이 a인 지시선(directed arc)으로 표기. 또한 종결상태들은 이중 원(double circle)으로 나타내고, 시작상태는 시작지시선으로 표시하는 유향 그래프(directed graph)
상태 : 오토마타에서 입력기호에 의하여 전이된 것을 의미하고, 상태전이도에서 원으로 표현
내용 정리
유한 오토마타는 입력으로 문자열을 받아서, 그 문자열이 그 언어의 문장이면 “yes"를 답하고 그렇지 않으면 “no"라고 답하는 프로그램으로 어휘분석기는 유한 오토마타의 대표적인 예이다.
유한 오토마타를 표현하는 방법에는 두 가지가 있는데, 먼저 정의에 따라서 5가지의 구성원소들을 형식(formal)에 맞게 정확히 표현하는 방법이 있다. 다음으로는 상태전이도(transition diagram)를 사용하여 비형식적(informal)으로 표현하는 방법이다. 일반적으로 유한 오토마타를 설명할 때 상태전이도를 많이 사용한다.
