오토마타 이론

Automata theory
Combinational logicFinite-state machinePushdown automatonTuring machineAutomata theoryAutomata theory.svg
About this image
오토마타 클래스
(각 레이어를 클릭하면 해당 주제에 대한 기사가 표시됩니다.)
상태 다이어그램에서 설명하는 자동화는 상태1 S에서 시작하여 0 또는 1로 표시된 화살표에 따라 상태가 변경됩니다.이중 원은 S를 수용 상태로 표시합니다1.S에서1 자체로의 모든 경로에는 0으로 표시된 짝수 화살표가 포함되어 있으므로 이 자동에서는 짝수 0을 포함하는 문자열을 사용할 수 있습니다.

오토마타 이론은 추상적기계와 오토마타, 그리고 그것들을 사용하여 해결할 수 있는 계산상문제에 대한 연구이다.그것은 이론적인 컴퓨터 과학의 이론이다.오토마타라는 단어는 그리스어 ααμαγο에서 유래했는데, 이는 "스스로 행동하고, 의지가 있고, 스스로 움직인다"는 뜻이다.오토마톤(복수의 오토마타)은 소정의 조작 시퀀스를 자동적으로 추종하는 추상적인 자기추진 컴퓨팅 장치이다.유한한 수의 상태를 가지는 오토마톤을 유한 오토마톤(FA) 또는 유한 상태 머신(FSM)이라고 부릅니다.오른쪽 그림은 잘 알려진 자동화 유형인 유한 상태 기계를 나타냅니다.이 자동화는 상태(그림에 원으로 표시됨)와 전환(화살표로 표시됨)으로 구성됩니다.오토마톤은 입력의 심볼을 볼 때 이전 상태와 전류 입력 심볼을 인수로 하는 전이 함수에 따라 다른 상태로 전이(또는 점프)한다.

오토마타 이론은 형식 언어 이론과 밀접한 관련이 있다.이 맥락에서 오토마타는 무한할 수 있는 형식 언어의 유한한 표현으로 사용됩니다.오토마타는 종종 그들이 인식할 수 있는 공식 언어의 클래스에 따라 분류됩니다. 촘스키 계층은 오토마타의 주요 클래스 간의 중첩 관계를 기술합니다.오토마타는 계산, 컴파일러 구성, 인공지능, 해석형식 검증이론에서 중요한 역할을 합니다.

역사

추상 오토마타 이론은 유한 [1]오토마타와 관련하여 20세기 중반에 개발되었다.오토마타 이론은 처음에는 이산 매개 변수 시스템의 동작을 연구하는 수학적 시스템 이론의 한 분야로 간주되었다.오토마타 이론의 초기 연구는 재료 [2]시스템을 기술하기 위해 미분적분이 아닌 정보 시스템을 기술하기 위해 추상대수를 사용함으로써 시스템에 대한 이전의 연구와 달랐다.유한 상태 변환기의 이론은 다른 연구 [3]공동체에 의해 다른 이름으로 개발되었습니다.튜링 기계의 초기 개념 또한 푸시다운 오토마타와 같은 새로운 형태의 무한 상태 오토마타와 함께 그 분야에 포함되었다.

1956년 클로드 섀넌, W. 로스 애쉬비, 존 폰 노이만, 마빈 민스키, 에드워드 F.포함한 과학자들의 작품을 모은 오토마타 스터디의 출판을 보았다. 무어, 그리고 스티븐[4]클린.이 책의 출간과 함께, "자동차 이론은 비교적 자율적인 학문으로 부상했다."[5]이 책에는 규칙적인 사건, 즉 규칙적인 언어에 대한 클린의 설명과 [6]섀넌의 튜링 기계 프로그램의 비교적 안정적인 복잡성의 척도가 포함되어 있다.같은 해, 노암 촘스키는 오토마타와 정형 [7]문법의 대응인 촘스키 계층을 기술했고, 로스 애쉬비는 오토마타와 기본 집합론을 사용하여 정보를 설명하는 접근 가능한 교과서인 사이버네틱스 입문서를 출판했다.

선형 유계 오토마타의 연구마이힐-네로드 [8]정리로 이어졌다. 마이힐-네로드 정리는 공식 언어가 규칙적이기 위한 필수적이고 충분한 조건과 언어를 위한 최소 기계에서 상태 수의 정확한 카운트를 제공한다.규칙성 증명에서도 유용한 정규 언어에 대한 펌프 보조어는 결정론적 및 비결정론적 유한 오토마타의 [9]계산적 등가성과 함께 이 시기에 마이클 O. 라빈과 다나 스콧에 의해 증명되었다.

1960년대에, "구조 이론" 또는 "대수 분해 이론"으로 알려진 대수적 결과의 집합이 등장했는데, 이것은 상호 [10]연결을 통해 작은 기계로부터 순차적인 기계의 실현을 다루었다.유한 오토마톤은 범용 게이트 세트를 사용하여 시뮬레이션할 수 있지만, 시뮬레이션 회로에는 임의의 복잡성의 루프가 포함되어 있어야 합니다.구조 이론은 기계의 "[5]루프 없는" 실현 가능성을 다룬다.계산 복잡성의 이론도 1960년대에 [11][12]구체화 되었다.10년 말, 오토마타 이론은 "컴퓨터 과학의 순수 수학"[5]으로 인식되게 되었다.

오토마타

이어지는 것은 자동화에 대한 일반적인 정의입니다. 자동화는 시스템의 광범위한 정의를 이산적인 시간 단계에서 작동하는 것으로 간주하는 것으로 제한하며, 각 단계에서 상태 동작과 출력은 상태와 [5]입력의 변화하지 않는 함수에 의해 정의됩니다.

비공식적인 설명

자동화는 이산(개별) 시간 단계(또는 단순한 단계)에서 입력 시퀀스가 주어질 때 실행됩니다.자동화는 기호 또는 문자 집합에서 선택한 하나의 입력을 처리하는데, 이를 입력 알파벳이라고 합니다.오토마톤이 어떤 단계에서든 입력으로 받는 기호는 단어라고 불리는 일련의 기호입니다.오토마톤은 일련의 상태를 가지고 있다.오토마톤을 실행하는 동안 각 순간 오토마톤은 그 상태 중 하나에 있습니다.자동화는 새로운 입력을 수신하면 이전 상태 및 전류 입력 기호를 파라미터로 사용하는 전환 함수를 기반으로 다른 상태로 이동합니다.동시에 출력 함수라고 불리는 또 다른 함수는 출력 알파벳에서 이전 상태 및 전류 입력 심볼에 따라 심볼을 생성합니다.오토마톤은 입력 워드의 기호를 읽고, 길이가 유한한 경우, 오토마톤이 정지하는 시점에서 워드를 완전히 읽을 때까지 상태 간에 전환합니다.오토마톤이 정지하는 상태를 최종 상태라고 합니다.

형식 언어이론을 사용하여 오토마톤에서 가능한 상태/입출력 시퀀스를 조사하기 위해 기계에 시작 상태 및 수용 상태 세트를 할당할 수 있다.그 후, 개시 상태로부터 개시하는 실행이 허가 상태로 종료하는지에 따라, 오토마톤은 입력 시퀀스를 받아 들이거나 거부한다고 말할 수 있다.오토마톤이 받아들이는 모든 단어의 집합을 오토마톤이 인식하는 언어라고 합니다.언어를 인식하는 기계의 친숙한 예로는 올바른 코드를 입력하려는 시도를 받아들이거나 거부하는 전자 잠금 장치가 있습니다.

형식적 정의

오토마톤
오토마톤은 5 M 、 ⟨ 、 \ M = \ \, \ ,, \ , \ 로 정식으로 나타낼 수 있습니다.
  • \Sigma는 자동 입력 알파벳이라고 불리는 유한한 기호 집합입니다.
  • \Gamma)는 오토마톤의 출력 알파벳이라고 불리는 또 다른 유한한 기호 세트입니다.
  • Q 일련의 상태입니다.
  • { \transition function }는 다음 상태 함수 또는 : Q × \\ transition function : : Q 상태 입력 쌍을 후속 상태에 매핑합니다.
  • { \ displayda}는 다음 출력 :Q × { \displayda : \ 출력에 상태 입력 쌍을 매핑합니다.
Q 유한하다면 M M 유한 오토마톤입니다.[5]
입력어
오토마톤은 유한한 줄의 를 읽습니다 n 입력워드라고 불리는 i \ \ \ 입니다.모든 워드의 displaydisplay(\로 표시됩니다.
달려.
나라들이 순서 q 0, q1...,q n{\displaystyle q_{0},q_{1},...,q_{n}}, q나는 ∈ Q{\displaystyle q_{나는}\in Q}가 q나는 갈δ(나는 − q1, 나는){\displaystyle q_{나는}=\delta(q_{i-1},a_{나는})}에 0<나는 ≤ n{\displaystyle 0<,i\leq n},의 automaton에 대한 입력을 설정합니다. ^{*}: 0부터 시작합니다.즉, 처음에는 자동이 시작 0이고 1({1의 입력을 받습니다.입력 문자열에서 1 경우 자동이 다음 를 선택합니다. 함수 ( i -1 ,) { ( _ { i - , { } }} , 、 마지막 { a _ { n}이 판독될 때까지, 기계는 실행의 최종 상태에 . 마찬가지로 각 단계에서 n { } } 。 출력 (i - , a ){ displaystyle \ (_ { i - 1 , _ { } }) 。
함수 유도적으로: Q × Q \ {\로 확장됩니다. Q 입력 단어 전체를 입력했을 때의 기계 동작을 설명합니다. " "" q {\q) = 모든 상태 q {\wa 은 마지막 war가비어 (\ wλ{\lambda\displaystyle}도 비슷하게는 완전한 outpu을 준다λ¯(q, w){\displaystyle{\overline{\lambda}}(q,w)}에 연장할 수 있는 세인트의 문자열,δ ¯(q, w))δ(δ ¯(q, w), a){\displaystyle{\overline{\delta}}(q,wa)=\delta({\overline{\delta}}(q,w),a)}그 출력 기능 .[10].의 tw로 가동하는 경우 wr.q
수용자
형식 언어 이론으로 오토마톤을 연구하기 위해 출력 알파벳 및 {\(\{\(\ 다음과 같이 대체하여 오토마톤을 수용체로 간주할 수 있습니다.
  • 00}\ Q 지정 시작 상태 및
  • F는 Q Q즉, Q \ F \ )의 의 상태를 승인 상태라고 부릅니다.
이를 통해 다음을 정의할 수 있습니다.
수용어
w 2. n { w =) 。^{*}}: ( 0 , )fF { { F인 경우, 즉 를 소비한 후 기계가 허용 상태에 있는 경우 자동화에 대한 허용 단어입니다.
인식된 언어
자동화에 의해 인식되는 L \ \ { * } 언어 자동화에 의해 받아들여지는 모든 단어의 집합입니다. { 0 , { L \ { { \ { \ \ \ \ \ Sigma }
인식 가능한 언어
인식 가능한 언어는 일부 자동화에 의해 인식되는 일련의 언어입니다.유한 오토마타의 경우 인식 가능한 언어는 정규 언어입니다.오토마타의 종류에 따라 인식할 수 있는 언어가 다릅니다.

오토마타의 다양한 정의

오토마타는 수학적 형식주의 하에서 유용한 기계를 연구하기 위해 정의된다.따라서 오토마톤의 정의는 오토마톤을 사용하여 모델링하고자 하는 "실제 기계"에 따라 달라질 수 있습니다.사람들은 오토마타의 많은 변형을 연구해 왔다.다음은 오토마타의 다양한 컴포넌트의 정의에서 자주 사용되는 변형입니다.

입력
  • 유한 입력:기호의 유한한 시퀀스만을 받아들이는 오토마톤.위의 도입부 정의는 한정된 단어만을 포함합니다.
  • 무한 입력:무한한 단어(ω-words)를 사용할 수 있는 오토마톤.이런 오토마타를 -오토마타라고 합니다.
  • 트리 입력:입력은 일련의 기호가 아닌 기호의 트리일 수 있습니다.이 경우 각 기호를 읽은 후 자동은 입력 트리의 모든 후속 기호를 읽습니다.오토마톤은 각 후계자에 대해 자신의 복사본을 하나씩 만들고, 이러한 복사본은 오토마톤의 전이 관계에 따라 상태에서 후속 기호 중 하나에서 실행되기 시작한다고 한다.이러한 자동화를 나무 자동화라고 합니다.
  • 무한 트리 입력 : 위의 두 확장자를 조합할 수 있기 때문에 자동화는 (무한) 분기가 있는 트리 구조를 읽습니다.이러한 자동화를 무한 트리 자동화라고 합니다.
미국.
  • 단일 상태:조합회로라고도 불리는 하나의 상태를 가진 오토마톤은 조합로직[10]구현할 수 있는 변환을 수행합니다.
  • 유한 상태:한정된 수의 상태만 포함하는 자동 장치입니다.
  • 무한 상태:유한한 수의 상태 또는 수 있는 수의 상태를 가지지 않는 오토마톤.이러한 기계에 유한한 기술을 제공하기 위해 다른 종류의 추상 메모리가 사용될 수 있다.
  • 스택 메모리: 오토마톤에는 기호를 눌러서 터트릴 수 있는 스택 형태의 추가 메모리가 포함되어 있을 수도 있습니다.이런 종류의 자동화를 푸시다운 자동화라고 합니다.
  • 메모리: 자동화는 큐 형태로 메모리를 가질 수 있습니다.이러한 기계는 큐머신이라고 불리며 튜링 완전하다.
  • 테이프 메모리:오토마타의 입력과 출력은 종종 입력 테이프와 출력 테이프로 표현됩니다.일부 기계에는 튜링 기계, 선형 경계 자동 장치로그 공간 변환기를 포함한 추가 작업 테이프가 있습니다.
전이 함수
  • 결정론:주어진 현재 상태 및 입력 심볼에 대해 오토마톤이 하나의 상태만으로 점프할 수 있다면 결정론적 오토마톤이다.
  • 비결정적:입력 기호를 읽은 후 전환 관계에 의해 라이센스가 부여된 여러 상태로 점프할 수 있는 자동 장치입니다.전이함수라는 용어는 전이관계로 대체된다는 점에 유의하십시오.자동화는 비결정적으로 허용된 선택 중 하나로 뛰어들기로 결정합니다.이러한 오토마타를 비결정적 오토마타라고 합니다.
  • 대체:이 생각은 나무 자동과 매우 비슷하지만 직교입니다.자동화는 동일한 다음 읽기 기호에서 여러 복사본을 실행할 수 있습니다.이러한 오토마타는 교대 오토마타라고 불립니다.입력을 수락하려면 이러한 복사본의 모든 실행에서 수락 조건이 충족되어야 합니다.
수용조건
  • 한정된 단어의 수용: 위의 비공식적인 정의에서 설명한 것과 같습니다.
  • 무한단어 수용: 무한단어는 절대 끝나지 않기 때문에 γ-자동은 최종 상태를 가질 수 없습니다.오히려, 단어의 수용 여부는 실행 중 방문한 상태의 무한 시퀀스를 보고 결정됩니다.
  • 확률론적 수용:자동화는 입력을 엄격히 받아들이거나 거부할 필요는 없습니다.0과 1 사이의 확률로 입력을 받아들일 수 있습니다.예를 들어, 양자 유한 오토마타, 기하학적 오토마타 및 미터법 오토마타는 확률론적 수용을 가진다.

상기의 다양한 종류의 조합에 의해서, 많은 클래스의 오토마타가 생성됩니다.

오토마타 이론은 다양한 종류의 오토마타의 특성을 연구하는 주제이다.예를 들어, 특정 유형의 오토마타에 대해 다음과 같은 질문을 연구합니다.

  • 어떤 종류의 오토마타가 인식할 수 있는 정식 언어 클래스는 무엇입니까?(인식 가능한 언어)
  • 공식 언어의 통합, 교차 또는 보완 하에 특정 오토마타가 폐쇄되어 있습니까?(폐쇄성)
  • 오토마타의 일종인 오토마타는 정식 언어의 클래스를 인식하는 데 있어서 얼마나 표현적인가?그리고 상대적인 표현력은? (언어 계층)

오토마타 이론은 또한 다음과 같은 문제를 해결하기 위해 효과적인 알고리즘의 유무를 연구합니다.

  • 자동이 적어도1개의 입력 워드를 받을 수 있습니까?(유예성 검사)
  • 인식된 언어를 변경하지 않고 주어진 비결정적 자동화를 결정론적 자동화로 변환할 수 있습니까? (결정화)
  • 특정 공식 언어에서 이를 인식하는 최소 자동화는 무엇입니까? (최소화)

오토마타의 종류

다음은 오토마타 유형의 불완전한 목록입니다.

오토마톤 인식 가능한 언어
비결정론적/결정론적 유한상태기계(FSM) 정규 언어
결정론적 푸시다운 오토마톤(DPDA) 결정론적 문맥이 없는 언어
푸시다운 오토마톤(PDA) 문맥이 없는 언어
LBA(Linear Bounded Automaton) 문맥에 민감한 언어
튜링 기계 재귀적으로 열거할 수 있는 언어
결정론적 뷔치 오토마톤 제한 언어
비결정론적 뷔치 오토마톤 § 정규 언어
Rabin automaton, Streett automaton, 패리티 automaton, Muller automaton
가중 오토마톤

이산, 연속 및 하이브리드 오토마타

일반적으로 자동 자동이론은 추상적인 기계의 상태를 설명하지만, 각각 디지털 데이터, 아날로그 데이터 또는 연속 시간 또는 디지털 및 아날로그 데이터를 사용하는 이산 자동, 아날로그 자동 또는 연속 자동 또는 하이브리드 이산-연속 자동이 있습니다.

파워에 관한 계층

다음은 서로 다른 유형의 가상 시스템 전원과 관련하여 불완전한 계층입니다.계층은 시스템이 허용할 [14]수 있는 중첩된 언어 범주를 반영합니다.

오토마톤
결정론적 유한자동화(DFA) -- 최저전력

(동일한 전원) {\ (동일한 전원)
비결정적 유한 오토마톤(NFA)
(위는 약함){\ {\ (위는 약함)
결정론적 푸시다운 오토마톤(DPDA-I)
푸시다운 스토어 1개 포함

비결정론적 푸시다운 오토마톤(NPDA-I)
푸시다운 스토어 1개 포함

LBA(Linear Bounded Automaton)

결정론적 푸시다운 오토마톤(DPDA-II)
2개의 푸시다운 스토어 포함

비결정적 푸시다운 오토마톤(NPDA-II)
2개의 푸시다운 스토어 포함

결정론적 튜링 머신(DTM)

비결정적 튜링 머신(NTM)

확률론적 튜링 머신(PTM)

멀티테이프 튜링 머신(MTM)

다차원 튜링 기계

적용들

오토마타 이론의 각 모델은 여러 응용 분야에서 중요한 역할을 합니다.유한 오토마타는 텍스트 처리, 컴파일러 및 하드웨어 설계에 사용됩니다.문맥 자유 문법(CFG)은 프로그래밍 언어와 인공지능에 사용됩니다.원래 CFG는 인간의 언어 연구에 사용되었다.셀 오토마타인공생명체 분야에서 사용되는데, 가장 유명한 예가콘웨이삶의 게임입니다.생물학에서 오토마타 이론을 사용하여 설명될 수 있는 다른 예로는 연체동물과 솔방울의 성장과 색소 침착 패턴이 있습니다.더 나아가, 우주 전체가 일종의 이산 오토마톤에 의해 계산된다는 이론은 일부 과학자들에 의해 주장되고 있다.이 아이디어는 콘라드 주세의 작품에서 시작되었고, 에드워드 프레드킨에 의해 미국에서 대중화 되었다.오토마타는 또한 유한장 이론에서도 나타난다: 2차 다항식의 구성이라고 쓰여질 수 있는 환원 불가능한 다항식의 집합은 사실 정규 [15]언어이다.오토마타가 사용될 수 있는 또 다른 문제는 정규 언어의 도입이다.

오토마타 시뮬레이터

오토마타 시뮬레이터는 오토마타 이론을 가르치고, 배우고, 연구하는 데 사용되는 교육 도구입니다.오토마타 시뮬레이터는 오토마톤의 기술을 입력으로 받아들여 임의의 입력 문자열에 대해 그 동작을 시뮬레이트한다.자동화에 대한 설명은 여러 가지 방법으로 입력할 수 있습니다.오토마톤은 심볼릭 언어로 정의될 수도 있고, 그 사양을 미리 지정된 형태로 입력할 수도 있고, 마우스를 클릭하여 드래그함으로써 그 전이도를 그릴 수도 있다.잘 알려진 오토마타 시뮬레이터에는 Turing's World, JFLAP, VAS, TAGS 및 Sim Studio가 [16]있습니다.

카테고리 이론과의 관련성

오토마타 분류에 이어 이전 섹션에서 설명한 여러 가지 유형의 오토마타를[17] 정의할 수 있습니다.결정론적 오토마타, 순차적 오토마타 또는 순차적 오토마타, 오토마타 사이의 화살표를 정의하는 오토마타 동형사상을 가진 튜링 머신의 수학적 범주는 데카르트 닫힌 [18][19]범주이며, 범주적 한계와 콜리밋을 모두 가지고 있다.오토마타 동형사상은 오토마톤i A의 5배수를 다른 오토마톤j A의 [20]5배수에 매핑한다.오토마타 동형사상은 오토마타 변환 또는 반그룹 동형사상으로 간주될 수 있으며, 오토마톤의 상태 공간 S반그룹g S로 정의되어 있을 때는 반그룹 동형사상은 오토마타 변환 또는 반그룹 동형사상으로 간주될 수 있다.모노이드는 모노이드 [21][22][23]범주에서 오토마타에 적합한 설정으로 간주됩니다.

가변 오토마타의 카테고리

Norbert Wiener저서 "Ai (의 A_ A_에서 가변 오토마톤을 정의할 수도 있다.그러면 그러한 가변 오토마타 동형사상이 수학적 그룹을 형성한다는 것을 보여줄 수 있다.단, 비결정론적 또는 기타 복잡한 종류의 오토마타의 경우, 후자의 내형성 세트는 가변 오토마톤 그룹로이드가 될 수 있다.따라서, 가장 일반적인 경우, 모든 종류의 가변 자동 범주는 그룹 또는 그룹 범주범주이다.또, 가역 오토마타의 카테고리는 2개의 카테고리이며, 그룹오이드의 2개의 카테고리, 즉 그룹오이드의 서브 카테고리이기도 하다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Mahoney, Michael S. "The Structures of Computation and the Mathematical Structure of Nature". The Rutherford Journal. Retrieved 2020-06-07.
  2. ^ Booth, Taylor (1967). Sequential Machines and Automata Theory. New York: John Wiley & Sons. p. 1-13. ISBN 0-471-08848-X.
  3. ^ Ashby, 윌리엄 로스(1967-01-15)."장소는 두뇌의 세계 자연에서"(PDF).근대 생물학에 Currents.1(2):95–104. doi:10.1016(67)90021-4. PMID 6060865.:.machine"(길, 1962년)의"noiseless transducer"(Shannon과 위버 1949년)의"state-determined system"(Ashby, 1952년),"sequential circuit"본질적으로 상동이 있다.""의 그 이론들은, 지금 발달되어,"finite-state.
  4. ^ Ashby, W. R.; et al. (1956). C.E. Shannon; J. McCarthy (eds.). Automata Studies. Princeton, N.J.: Princeton University Press.
  5. ^ a b c d e Arbib, Michael (1969). Theories of Abstract Automata. Englewood Cliffs, N.J.: Prentice-Hall.
  6. ^ Li, Ming; Paul, Vitanyi (1997). An Introduction to Kolmogorov Complexity and its Applications. New York: Springer-Verlag. p. 84.
  7. ^ Chomsky, Noam (1956). "Three models for the description of language" (PDF). IRE Transactions on Information Theory. 2 (3): 113–124. doi:10.1109/TIT.1956.1056813.
  8. ^ Nerode, A. (1958). "Linear Automaton Transformations". Proceedings of the American Mathematical Society. 9 (4): 541. doi:10.1090/S0002-9939-1958-0135681-9.
  9. ^ Rabin, Michael; Scott, Dana (Apr 1959). "Finite Automata and Their Decision Problems" (PDF). IBM Journal of Research and Development. 3 (2): 114–125. doi:10.1147/rd.32.0114. Archived from the original on 2010-12-14.{{cite journal}}: CS1 유지보수: 부적합한 URL(링크)
  10. ^ a b c Hartmanis, J.; Stearns, R.E. (1966). Algebraic Structure Theory of Sequential Machines. Englewood Cliffs, N.J.: Prentice-Hall.
  11. ^ Hartmanis, J.; Stearns, R. E. (1964). "Computational complexity of recursive sequences" (PDF).
  12. ^ Fortnow, Lance; Homer, Steve (2002). "A Short History of Computational Complexity" (PDF).
  13. ^ Moore, Cristopher (2019-07-31). "Automata, languages, and grammars". arXiv:1907.12713 [cs.CC].
  14. ^ Yan, Song Y. (1998). An Introduction to Formal Languages and Machine Computation. Singapore: World Scientific Publishing Co. Pte. Ltd. pp. 155–156. ISBN 9789810234225.
  15. ^ Ferraguti, A.; Micheli, G.; Schnyder, R. (2018), Irreducible compositions of degree two polynomials over finite fields have regular structure, The Quarterly Journal of Mathematics, vol. 69, Oxford University Press, pp. 1089–1099, arXiv:1701.06040, doi:10.1093/qmath/hay015, S2CID 3962424
  16. ^ Chakraborty, P.; Saxena, P. C.; Katti, C. P. (2011). "Fifty Years of Automata Simulation: A Review". ACM Inroads. 2 (4): 59–70. doi:10.1145/2038876.2038893. S2CID 6446749.
  17. ^ 지리 아다멕과 비라 트른코바, 1990년오토마타와 알헤브라는 카테고리에 속합니다.Kluwer 학술 출판사:도르트레흐트 프라하
  18. ^ Mac Lane, Saunders (1971). Categories for the Working Mathematician. New York: Springer. ISBN 9780387900360.
  19. ^ 데카르트 폐쇄 카테고리 2011년 11월 16일 Wayback Machine에 보관
  20. ^ 2011년 9월 15일 Wayback Machine에서 아카이브된 오토마타
  21. ^ http://www.math.cornell.edu/~worthing/asl2010.pdf James Worthington.2010.모노이드 카테고리의 결정, 망각 및 자동화.ASL 북미 연차총회, 2010년 3월 17일
  22. ^ M. Aguiar, M. 및 Mahajan, S. 2010. "모노이드 펑터, 종, 그리고 홉프 알헤브라"
  23. ^ Meseguer, J., Montanari, 미국: 1990 Petri 그물은 모노이드입니다.정보계산 88:105 ~155

추가 정보

외부 링크