항목
-
-
유한 오토머턴 FA, finite automaton오토머턴의 일종으로 가장 단순하고 기본적인 계산 기계 모델. 그림 1과 같이 입력 테이프와 그 위의 판독 전용 헤드와 유한 상태 제어부로 이루어져 있는데, 테이프를 작업용으로 사용할 수 없다는 점이 다른 오토머턴과 크게 다른 점이다. 유한 오토머턴은 입력 테이프 위를 헤드가 왼쪽에서 오른쪽으로 순차적으로...
- 분야 :
- 소프트웨어 기초, 프로그램 언어, 패턴 정보처리
-
선형 유계 오토머턴 LBA, linear bounded automaton기계의 테이프를 입력어가 놓여 있는 부분에만 한정하고 그 양끝에 경계 기호를 붙여, 헤드가 이 두 경계 기호의 밖으로 나가지 않도록 한 것. 선형 구속 오토머턴이라고도 한다. 비결정성의 LBA는 6항조 M=(Q, Σ, Г, δ, q0, F)로 주어진다. 여기서 Q는 상태가 공백이 아닌 유한 집합, Σ는 입력 알파벳, Г는 테이프...
- 분야 :
- 소프트웨어 기초
-
오토머턴 automaton컴퓨터를 비롯한 여러 가지 계산기구의 수학적인 모델의 총칭. 1차원의 기호열(계열)을 계산의 대상으로 하는 1차원 테이프 오토머턴을 가리키는 일이 많은데, 2차원 이상의 테이프를 가지는 오토머턴과 그래프오토머턴(그래프 문법 참고), 트리오토머턴, 셀오토머턴 등 많은 종류가 고안되어 있다. 형식언어의 문법이...
- 분야 :
- 소프트웨어 기초
-
푸시다운 오토머턴 PDA, pushdown automaton오토머턴의 일종. 한쪽 끝(이하 왼쪽끝이라고 한다)에서만 읽고 쓸 수 있고, 후입선출(LIFO)방식인 편면 반무한의 기억기구를 푸시다운 스택(pushdown stack)이라 하고, 거기에 기억시키는 기호를 스택 기호(stack symbol)라고 한다. 푸시다운 오토머턴은 유한 오토머턴에 다시 푸시다운 스택이 붙은 형식의 오토머턴...
- 분야 :
- 소프트웨어 기초, 프로그램 언어
-
셀룰러 오토머턴 셀 구조 오토머턴, cellular automaton셀 구조 오토머턴이라고도 한다. 오토머턴의 일종이며, 동일한 기능을 가지는 유한 오토머턴을 규칙적으로 배치하여 상호 접속한 계. 병렬 컴퓨터, 역학계, 생물계의 수학적인 모델로서 널리 연구되어 있다. 셀 공간(cell space)이라고 불리는 d차원 무한격자를 생각하여, 그 격자점에 동일한 유한 오토머턴을 배치한다...
- 분야 :
- 소프트웨어 기초
-
트리 오토머턴 tree automaton입력으로서 1차원의 기호열을 다루는 테이프 오토머턴(오토머턴 참고)을, 라벨화된 트리를 다루듯이 확장한 오토머턴. ∑를 알파벳으로 할 때, 트리 오토머턴의 입력이 되는 ∑트리(∑-tree)란, 그 노드에 그의 원소가 라벨화된 유향 트리(보통은 이분트리)이다. 유한 오토머턴에 대응하는 트리 오토머턴은 5항조(Q, ∑...
- 분야 :
- 소프트웨어 기초
-
확률 오토머턴 probabilistic automaton유한 오토머턴을 확장한 모델로, 상태전이가 확률적으로 주어지는 오토머턴. 형식적으로는 5항조 A=(Q, Σ, M, π, F)로 표시된다. Q는 상태의 유한집합, Σ는 입력기호의 유한집합, M은 마르코프 행렬(전이확률행렬)의 |Σ|개의 집합으로, i번째의 행렬의 (j, k)원소는 입력 xi가 들어갔을 때의 상태 qj에서 qk에의...
- 분야 :
- 소프트웨어 기초
