오토마타
what?
계산 능력이 있는 추상 기계와 그 기계를 이용해서 풀 수 있는 문제들에 대해 학문적으로 접근한 컴퓨터 과학 분야
종류
유한 상태 기계 (Finite State Machine, FSM)
컴퓨터 프로그램을 설계할 때 쓰이는 모델이다. 컴퓨터 내에 유한한 상태를 가지는 기계가 있다고 가정하고, 컴퓨터는 오로지 하나의 상태만 갖고 있을 수 있으며 각 상태별 동작과 상태끼리의 전이에 대한 내용을 설계하게 된다.
내부상태 이외의 저장 공간을 갖지 않는 오토마타이다. 입력 문자열이 주어지면 이것을 하나씩 읽으면서 내부상태를 바꿔나간다. 저장공간이 없기에 아주 간단한 특성을 가진다.
푸시다운 오토마타(Push-Down Automata, PDA)
내부상태 이외에 스택으로 된 저장 공간을 갖는 오토마타이다. 입력 문자열이 주어지면 이것을 하나씩 읽으면서 내부상태를 바꿔나간다. 동시에 스택 맨 위의 적힌 내용(Top)을 읽고 바꾸거나 지우거나 새로 쓸 수 있다.
튜링 머신
무한 1차원 테이프를 저장 공간으로 갖는다. 스택 오토마타가 스택 맨 위의 원소만 활용할 수 있던 것과 달리 무한 테이프 위를 왔다갔다 하면서 테이프의 모든 내용을 항상 활용할 수 있다. 입력도 테이프에 적혀있는 채로 주어진다. 테이프를 좌우로 왔다갔다 하면서 동작하기에 입력을 순서대로 읽는 것이 아니며 동작이 끝나지 않게 될 수도 있다.
why?
추후 전공수업 이수 후에 자세히 다룰 수 있을 것 같다. 이해가 안돼요..