결정론적 유한 오토마톤

3의 배수인 이진수만 받아들이는 결정론적 유한 자동화의 예제입니다.상태₀ S는 시작 상태와 수락 상태 모두입니다.예를 들어 문자열 '1001'은 상태₀ 시퀀스₁ S₂, S₁, S, S₀, S로 이어지기 때문에 받아들여진다.

계산 이론에서, 결정론적 유한 자동자(DFA), 결정론적 유한 상태 기계(DFSM), 또는 결정론적 유한 상태 자동자(DFSA)라고도 알려진 결정론적 유한 자동자(Definistic Finite-State Automaton)는 주어진 기호를 실행함으로써 받아들이거나 거부하는 유한 상태 기계이다.스트링에 ^[1]의해 일의로 결정되는 스테이트시퀀스결정론은 계산 실행의 고유성을 나타냅니다.유한 상태 기계를 포착하기 위한 가장 단순한 모델을 찾기 위해,^[2]^[3] 워렌 맥컬록과 월터 피츠는 1943년에 유한 오토마타와 유사한 개념을 도입한 최초의 연구자들 중 하나였다.

그림은 상태도를 사용한 결정론적 유한 오토마톤을 나타낸다.이 자동화 예에서는 S₁, S 및 S₂(그래픽으로 원으로 표시됨)의₀ 세 가지 상태가 있습니다.자동화는 0과 1의 유한 시퀀스를 입력으로 받아들입니다.각 상태에 대해 0과 1 모두 다음 상태로 이어지는 전환 화살표가 있습니다.기호를 읽을 때 DFA는 전환 화살표를 따라 한 상태에서 다른 상태로 결정적으로 점프합니다.예를 들어 오토마톤이 현재 상태₀ S이고 현재 입력 기호가 1이면 결정적으로 상태₁ S로 점프합니다.DFA는 연산이 시작되는 시작 상태(그림으로 표시됨)와 연산이 성공하는 시기를 정의하는 데 도움이 되는 일련의 수락 상태(그림으로 표시됨)를 가진다.

DFA는 추상적인 수학적 개념으로 정의되지만 어휘 분석 및 패턴 매칭과 같은 다양한 특정 문제를 해결하기 위해 하드웨어와 소프트웨어에 구현되는 경우가 많습니다.예를 들어 DFA는 이메일 주소와 같은 온라인 사용자 입력이 구문적으로 ^[4]유효한지 여부를 결정하는 소프트웨어를 모델링할 수 있습니다.

DFA는 비결정적 유한 오토마타(NFA)로 일반화되었으며, 상태로부터 시작하는 동일한 라벨의 여러 화살표가 있을 수 있습니다.파워셋 구성 방식을 사용하면 모든 NFA를 동일한 언어를 인식하는 DFA로 변환할 수 있습니다.DFA 및 NFA는 정규 ^[1]언어 집합을 정확하게 인식합니다.

형식적 정의

결정론적 유한 $오토마톤$ M은 ( $Q, δ, δ 0$ , q, $F)$ 5-튜플이다.

상태 $Q$ 의 유한 집합
알파벳 $δ$ 라고 하는 입력 기호 집합
전이 함수 $θ$ : Q × δ→ $Q$
초기 또는 시작 $q_{0}\in Q$ $q_{0}\in Q$ 0 $q_{0}\in Q$ Q $q_{0}\in Q$ { $displaystyle q$ _ { $0$ } \ $in$ Q $q_{0}\in Q$ }
일련의 $F\subseteq Q$ 상태 F $F\subseteq Q$ Q \ $displaystyle$ F \ $subseteq$ }

w = $aa 12 \dots a$ 를_n 알파벳 $σ$ 위에 문자열로 $둡니다$ .자동 $M$ 은 일련의 상태 $r 0, r 1$ , $\dots,$ $r$ 이_n Q에 $존재$ 하는 경우 $문자열$ w를 받아들입니다.다음 조건은 다음과 같습니다.

$r 0 = q 0$
$r i +1 = µ$ ( $r i,$ $a i +1),$ $i$ = $0, \dots,$ n - $1$ 의 $경우$
$r_{n}\in F$ n $r_{n}\in F$ F { $displaystyle r$ _ { $n$ } $r_{n}\in F$ \ in F 。

즉, 첫 번째 조건은 기계가 시작 $상태 0$ q에서 시작된다는 것입니다.두 번째 조건은 $문자열$ w의 각 문자가 주어지면 이행함수 $δ$ 에 따라 기계가 상태 간에 이행하는 것이다.마지막 조건에서는 w의 $마지막$ 입력으로 인해 머신이 허용 상태 중 하나로 정지할 경우 머신이 w를 $받아들인다고$ 합니다.그렇지 않으면 자동이 문자열을 거부한다고 합니다.M이 $받아들이는$ 문자열 세트는 M이 $인식$ 하는 언어이며 이 언어는 L $(M)$ 로 표시됩니다.

수용상태가 없는 결정론적 유한오토마톤과 시작상태가 없는 것을 전이계 또는 반자동마톤이라고 한다.

정식 정의에 대한 보다 포괄적인 소개는 자동 이론(automata theory)을 참조하십시오.

예

다음 예시는 $DFA$ M의 바이너리 알파벳으로 입력에 짝수 0이 포함되어 있어야 합니다.

M의 상태 다이어그램

$M$ = ( $Q, δ, δ 0$ , q, $F)$ 여기서

$Q = {S 1, S 2}$
$δ = {0, 1)$
$q 0 1 = S$
$F$ = { $S 1}$ 및
is $δ$ 、 다음 상태 전이 테이블로 정의됩니다.

	0	1
S₁	S₂	S₁
S₂	S₁	S₂

$상태 1$ S는 지금까지 입력에 짝수 0이 존재했음을 $나타내며 2$ , S는 홀수를 나타냅니다.입력의 1이 되어도, 자동의 상태는 바뀌지 않습니다.입력이 종료되면 상태는 입력에 짝수 0이 포함되었는지 여부를 나타냅니다.입력에 짝수 0이 포함되어 있는 경우 $M은$ 상태 $S 1$ (수용 상태)로 종료되므로 입력 문자열이 받아들여집니다.

M이 $인식$ 하는 언어는 정규 표현에 의해 주어지는 정규 언어이다. (1*) (0 (1*) 0 (1*))*,어디에*클린 스타입니다.1*는, 연속하는 1의 임의의 번호(소수 0)를 나타냅니다.

바리에이션

완전하고 불완전하다

위의 정의에 따르면, 결정론적 유한 오토마타는 항상 완전하다. 즉, 각 상태로부터 각 입력 심볼에 대한 전이를 정의한다.

이것이 가장 일반적인 정의이지만, 일부 저자는 약간 다른 개념, 즉 각 상태와 각 입력 기호에 대해 최대 하나의 전이를 정의하는 자동화를 위해 결정론적 유한 자동화라는 용어를 사용한다. 전이 함수는 부분적으로 ^[5]허용된다.이행을 정의하지 않으면 이러한 자동화는 정지합니다.

로컬 오토마타

로컬 오토마톤은 DFA이며, 반드시 완전한 것은 아닙니다.이 경우 라벨이 동일한 모든 에지는 하나의 정점으로 이어집니다.로컬 오토마타는 해당 ^[6]^[7]언어의 단어 구성원이 해당 단어에 길이 2의 "슬라이딩 창"에 의해 결정되는 로컬 언어 클래스를 받아들입니다.

알파벳 A 위의 Myhill 그래프는 정점 집합 A와 "시작" 및 "마침"으로 레이블이 지정된 정점의 하위 집합을 가진 방향 그래프입니다.Myhill 그래프에 의해 받아들여지는 언어는 시작 정점에서 종료 정점까지의 방향 경로 집합입니다.그래프는 오토마톤 ^[6]역할을 합니다.Myhill 그래프에서 허용되는 언어 클래스는 현지 ^[8]언어 클래스입니다.

랜덤성

시작 상태 및 수락 상태가 무시되면 n개의 상태와 크기 $k$ 의 $알파벳$ 의 DFA는 모든 정점에 1, $\dots,$ $k$ (k-out digraph)라는 라벨이 붙은 k개의 $정점$ 의 digraph로 볼 수 있습니다.k ≤ $2가$ 높은 확률의 고정 $정수일$ 때 무작위로 균일하게 선택된 k-out 디그래프에서 가장 큰 강접속 성분(SCC)은 선형 크기이며 모든 ^[9]정점에 도달할 수 있는 것으로 알려져 있다.또한 k가 $n$ 의 증가에 따라 증가할 수 있는 $경우$ 전체 이중그래프는 ^[10]접속에 대한 Erdss-Rényi 모델과 유사한 강력한 접속을 위한 위상 천이를 갖는 것으로 증명되었다.

랜덤 DFA에서 하나의 정점에서 도달 가능한 최대 정점 수는 높은 ^[9]^[11]확률로 가장 큰 SCC의 정점 수에 매우 가깝습니다.이는 1코어의 ^[10]유도 버전으로 볼 수 있는 최소 인도의 가장 큰 유도 서브그래프에도 해당된다.

닫힘 속성

왼쪽 위 자동화는 "00"을 하나 이상 포함하는 모든 이진 문자열의 언어를 인식합니다.오른쪽 아래 자동화는 짝수 "1"을 가진 모든 이진 문자열을 인식합니다.왼쪽 아래 오토마톤은 앞의 두 언어의 산물로 얻어진 것으로, 두 언어의 교집합을 인식합니다.

DFA가 DFA 인식 가능한 언어에 대해 연산을 적용하여 얻은 언어를 인식하면 DFA는 연산에 의해 폐쇄된다고 한다.DFA는 다음의 조작으로 닫힙니다.

유니언
교차로^[12]^{: 59–60}(그림 참조)
연결
부정
클린 클로저
반전
초기화
몫^{[citation needed]}
대체^{[citation needed]}
동형사상^{[citation needed]}

각 조작에 대해 상태 복잡성 연구에서 상태 수와 관련된 최적의 구성이 결정되었다.DFA는 비결정론적 유한 오토마타(NFA)와 동일하기 때문에 이러한 폐쇄는 NFA의 폐쇄 특성을 사용하여 증명할 수도 있다.

전이모노이드로서

소정의 DFA의 실행은 전이함수의 매우 일반적인 공식의 일련의 조성으로 볼 수 있다.여기서 그 기능을 구축합니다.

특정 입력 $a\in \Sigma$ {\ $displaystyle$ a $\in \Sigma$ 에 대해 변환 함수 $\delta _{a}:Q\rightarrow Q$ a : $\delta _{a}:Q\rightarrow Q$ $\delta _{a}:Q\rightarrow Q$ \ $displaystyle \sigma$ _ ${a}$ 를 구성할 수 있습니다.Q $\rightarrow$ Q $}$ 는 $\delta _{a}:Q\rightarrow Q$ 모든 Q $(\displaystyle$ Q $\in$ $q\in Q$ 에 대해 " $\delta _{a}(q)=\delta (q,a)$ q $,$ $)$ { $displaystyle \displaystyle$ _ ${a}(q,a)=$ \display( $q$ , $a$ $)}"$ 를 정의함으로써 커링이라고 부릅니다.이러한 관점에서 $\delta _{a}$ §는 Q의 상태에 대해 다른 상태를 생성하기 위해 "actionsysisplay \ $delta$ _ { $a$ } $\delta _{a}$ 。그 후, $\delta _{a}$ 한 $\delta _{a}$ $「\$ _ ${a$ $\delta _{b}$ 「 $\displaystyle$ \ $delta _{$ b $\delta _{b}$ 등에 반복적으로 적용되는 기능 구성의 결과를 생각할 수 있습니다. $a,b\in \Sigma$ 와 $b의 쌍$ 으로 $a,b\in \Sigma$ 함수 $a,b\in \Sigma$ ${\widehat {\delta }}_{ab}=\delta _{a}\circ \delta _{b}$ ${\widehat {\delta }}_{ab}=\delta _{a}\circ \delta _{b}$ $a,b\in \Sigma$ ${\widehat {\delta }}_{ab}=\delta _{a}\circ \delta _{b}$ ${\widehat {\delta }}_{ab}=\delta _{a}\circ \delta _{b}$ （ $displaystyle$ ） ${\widehat {\delta }}_{ab}=\delta _{a}\circ \delta _{b}$ displaystyle ） b { displaystyle { $widehat } _$ { $ab$ } = \ $displaystyle _$ { $a$ } = \ displaystyle _ { $b$ $}$ ）를 $\circ$ 정의할 수 있습니다.여기서 $\circ$ "\ $displaystyle$ 。

^ ${\widehat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q$ : ${\widehat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q$ × ${\widehat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q$ ${\widehat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q$ $→$ ${\widehat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q$ \ $display$ style \ $widehat \$ 의 재귀적 정의를 내리면서 이 프로세스를 재귀적으로 계속할 수 있습니다. $Q\times \Sigma ^{\star}\$ 오른쪽 $화살표$ Q ${\widehat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q$

{\widehat {\delta }}(q,\epsilon )=q

(

{\widehat {\delta }}(q,\epsilon )=q

,

{\widehat {\delta }}(q,\epsilon )=q

)

{\widehat {\delta }}(q,\epsilon )=q

)

{\widehat {\delta }}(q,\epsilon )=q

=

q

{

displaystyle

{

widehat

} （

q

, \ silon ）

{\widehat {\delta }}(q,\epsilon )=q

=

{\widehat {\delta }}(q,\epsilon )=q

q } 。

여기서 { displaystyle

\ silon

\epsilon

}은

\epsilon

빈 문자열이고,

{\widehat {\delta }}(q,wa)=\delta _{a}({\widehat {\delta }}(q,w))

(

{\widehat {\delta }}(q,wa)=\delta _{a}({\widehat {\delta }}(q,w))

,

{\widehat {\delta }}(q,wa)=\delta _{a}({\widehat {\delta }}(q,w))

a )

{\widehat {\delta }}(q,wa)=\delta _{a}({\widehat {\delta }}(q,w))

=

{\widehat {\delta }}(q,wa)=\delta _{a}({\widehat {\delta }}(q,w))

(

{\widehat {\delta }}(q,wa)=\delta _{a}({\widehat {\delta }}(q,w))

^ (

q

,

{\widehat {\delta }}(q,wa)=\delta _{a}({\widehat {\delta }}(q,w))

w

{\widehat {\delta }}(q,wa)=\delta _{a}({\widehat {\delta }}(q,w))

) {

displaystyle

{

widehat } =

\

{\widehat {\delta }}(q,wa)=\delta _{a}({\widehat {\delta }}(q,w))

display

_

{ a } ( { \

widehat

} } （ q , w

{\widehat {\delta }}(q,wa)=\delta _{a}({\widehat {\delta }}(q,w))

）。

여기

서 w

w\in \Sigma ^{*},a\in \Sigma

σ

σ

a 、 \

sigma

、 \

style w ^

}

$^$ {\ $displaystyle {\$ $delta$ $}$ 은 ${\widehat {\delta }}$ $w\in \Sigma ^{*}$ 는 $w\in \Sigma ^{*}$ $w\in \Sigma ^{*}$ 단어에 대해 정의됩니다.DFA 실행은 $^$ ${\displaystyle$ ${\$ $delta$ $}$ 의 ${\widehat {\delta }}$ ${\widehat {\delta }}$ 의 구성입니다.

반복된 기능 구성은 모노이드를 형성합니다.전이 함수의 경우, 이 모노이드는 전이 모노이드 또는 변환 반군으로 알려져 있습니다. $^(\$ 을 지정하면 $^(\displaystyle\delta$ 을 재구성할 수 있으므로 두 설명은 동일합니다.

장점과 단점

DFA는 입력 스트림에서 DFA를 시뮬레이션하는 간단한 선형 시간, 일정 공간, 온라인 알고리즘이 있기 때문에 가장 실용적인 계산 모델 중 하나입니다.또, DFA 를 검출하기 위한 효율적인 알고리즘도 있습니다.

특정 DFA가 인정하는 언어의 보완어.
두 개의 DFA가 인정하는 언어의 결합/교차.

DFA는 표준 형식(최소 DFA)으로 축소할 수 있기 때문에 다음 사항을 결정하는 효율적인 알고리즘도 있습니다.

DFA가 문자열을 받아들일지 여부(엠프티니스 문제)
DFA가 모든 문자열을 받아들일지 여부(범용성 문제)
두 DFA가 동일한 언어를 인식하는지 여부(균등성 문제)
DFA에 의해 인식된 언어가 두 번째 DFA에 의해 인식된 언어에 포함되는지 여부(포용 문제)
특정 정규 언어의 최소 상태 수를 가진 DFA(최소화 문제)

DFA는 비결정적 유한 오토마타(NFA)와 동등한 처리 능력입니다.이는 우선 모든 DFA도 NFA이기 때문에 NFA는 DFA가 할 수 있는 일을 할 수 있기 때문입니다.또한, NFA는 ^[13]^[14]NFA보다 기하급수적으로 많은 주를 가질 수 있지만, 파워셋 구조를 사용하여 NFA와 동일한 언어를 인식하는 DFA를 구축할 수 있다.그러나 NFA는 계산상 DFA와 동등하지만 위에서 언급한 문제가 NFA에 대해서도 반드시 효율적으로 해결되는 것은 아니다.NFA의 비범용성 문제는 지수 크기에서 가장 짧은 거부 단어를 가진 작은 NFA가 있기 때문에 PSPACE가 완전하다.DFA는 모든 상태가 최종 상태일 경우에만 범용이지만 NFA에는 적용되지 않습니다.동등성, 포함성 및 최소화 문제도 NFA의 보완성을 요구하기 때문에 PSPACE가 완료되어 크기가 ^[15]기하급수적으로 커집니다.

한편, 유한 상태 오토마타는 그들이 인식할 수 있는 언어에서 엄격히 제한된 힘을 가지고 있습니다. 해결하는데 일정한 공간 이상을 필요로 하는 문제를 포함한 많은 간단한 언어들은 DFA에 의해 인식될 수 없습니다.DFA가 인식할 수 없는 간단한 설명 언어의 전형적인 예는 괄호 또는 다이크 언어입니다. 즉, 단어("")와 같이 적절히 쌍을 이룬 대괄호로 구성된 언어입니다. 직감적으로, DFA는 다이크 언어를 인식할 수 없습니다. DFA와 같은 오토마톤은 어떤 상태를 나타낼 필요가 있기 때문입니다.ble "현재 열려 있는" 괄호 수. 즉, 무제한의 상태가 필요합니다.또 다른 간단한 예는 유한하지만 임의의 수의 a에 대해 ab 형식의ⁿⁿ 문자열로 구성된 언어이며, 그 뒤에 같은 수의 ^[16]b가 뒤따른다.

라벨 부착 단어에서 DFA 식별

$S^{+}\subset \Sigma ^{*}$ + $S^{+}\subset \Sigma ^{*}$ display $、$ { $displaystyle$ S^ { + } \ $subset$ \ $Sigma ^$ { * } $S^{-}\subset \Sigma ^{*}$ display $S^{+}\subset \Sigma ^{*}$ S - $S^{-}\subset \Sigma ^{*}$ $\$ \ $Sigma ^$ { * } $displaydisplaydisplaydisplaydisplaydisplaydisplay$ S $S^{+}$ ^ { * } $S^{-}\subset \Sigma ^{*}$ 문제는 DFA 식별(합성, 학습)이라고 불립니다.일부 DFA는 선형 시간으로 구성할 수 있지만, 최소 상태의 DFA를 식별하는 문제는 ^[17]NP-complete입니다.최소 DFA 식별을 위한 첫 번째 알고리즘은 에서 Trakhtenbrot와 Barzdin에^[18] 의해 제안되었으며 TB 알고리즘이라고 불립니다.단, TB 알고리즘에서는 $\Sigma$ \ $displaystyle$ \ $Sigma }$ 에서 $\Sigma$ 소정의 길이까지의 모든 단어가 $S^{+}\cup S^{-}$ S + $S^{+}\cup S^{-}$ S - $S^{+}\cup S^{-}$ \ $displaystyle$ S^ { + } \ $cup$ S $^$ { - $S^{+}\cup S^{-}$ } 중 $S^{+}\cup S^{-}$ 에 포함되어 있다고 가정합니다.

이후 K. Lang은 S $S^{+}$ + $S^{+}$ {\ $displaystyle$ S $^{+}$ 및 $S^{+}$ $S^{-}$ - $S^{-}$ {\ $displaystyle$ S $^{-}$ 의 $S^{-}$ ^[19]TB 알고리즘의 확장을 제안했습니다.그러나 Traxbar는 구성된 DFA의 최소성을 보장하지 않습니다.E.M. Gold는 또한 그의 연구에서^[17] 최소한의 DFA 식별을 위한 휴리스틱 알고리즘을 제안했다.Gold 알고리즘에서는 S $S^{+}$ + {\ $displaystyle$ S $^{+}$ 및 $S^{-}$ - {\ $displaystyle$ S $^{-}}$ 가 $S^{-}$ $S^{+}$ 정규 언어의 특성 세트를 포함하고 있는 $S^{+}$ 을 전제로 하고 있습니다.그렇지 않으면 작성된 DFA는 $S^{+}$ S $S^{+}$ + {\ $displaystyle$ S $^{+}}$ $S^{-}$ S $S^{-}$ \ $displaystyle$ S $S^{-}$ 와 $S^{+}$ 하지 않습니다.기타 주의할 수 있는 DFA 식별 알고리즘.ms에는 RPNI 알고리즘,^[20] Blue-Fringe 증거 기반 스테이트머징 알고리즘,^[21] Windowed-EDSM이 ^[22]포함됩니다.알고리즘의 또 다른 연구 방향을 적용한 것: 똑똑한 상태 진화 algorithm[23]은 훈련 데이터( 가져오거나 설정한 S+{\displaystyle S^{+}}과 S−{\displaystyle S^{-}})이 몇몇의 단어에 기인합니다에 시끄럽다 한정자가 지정된 지연 재생 청력 검사 식별 문제 풀기 위해 표지.wr옹클래스

그러나 Marjin J. H. H. Heule과 S.의 SAT 해결사 적용으로 또 다른 진전이 있었다.Verwer: 최소 DFA 식별 문제는 부울 ^[24]공식의 충족 가능성을 결정하는 것으로 감소됩니다.주요 아이디어는 입력 세트를 기반으로 증강된 프리픽스 트리 수용체(해당 라벨이 있는 모든 입력 단어를 포함하는 트리)를 구축하여 C $(\displaystyle$ C $)$ $C$ 의 $C$ DFA를 찾는 문제를 줄이고 C $(\$ displaystyle C $)$ 상태의 트리 정점을 C(\ $displaystyle$ C) $C$ 로 $C$ 색칠하는 것입니다.생성된 오토마톤은 $S^{+}$ $S^{-}$ 이며 $S^{+}$ + {\ $displaystyle$ S^{+}} $S^{-}$ 및 S - {\ $displaystyle$ S $S^{-}$ 에 준거합니다.이 접근방식은 최소한의 DFA를 찾을 수 있지만 입력 데이터의 크기가 커지면 실행 시간이 기하급수적으로 증가하게 됩니다.따라서 Heule과 Verwer의 초기 알고리즘은 나중에 SAT 솔버 실행 전에 EDSM 알고리즘의 여러 단계를 만들면서 강화되었습니다.^[25] 즉, DFASAT 알고리즘이다.이를 통해 문제의 검색 공간을 줄일 수 있지만 최소 보장성을 잃게 됩니다.검색 공간을 줄이는 또 다른 방법은 폭 우선 검색 알고리즘에 기초한 새로운 대칭 해제 술어를 사용하여 제안되었습니다^[26]. 즉, 검색된 DFA 상태는 초기 상태에서 시작된 BFS 알고리즘에 따라 번호가 지정되도록 제한됩니다.이 접근방식은 동형 오토마타를 제거하여 C $!(\displaystyle$ C $!)$ 서치 $C!$ 공간을 $줄입니다$ .

동등한 모델

읽기 전용 오른쪽 이동 튜링 기계

읽기 전용 오른쪽 이동 튜링 기계는 오른쪽으로만 움직이는 튜링 기계의 특정 유형입니다; 이것들은 거의 DFA와 동일합니다.^[27]단일 무한 테이프에 기반한 정의는 7-tuple입니다.

M=\langle Q,\Gamma,b,\Sigma,\sigma,q_{0},F\rangle,

어디에

(\displaystyle

Q

)

는

Q

유한한 상태의 집합입니다.

γ

\

displaystyle

\

\Gamma

Gamma

\Gamma

}는 테이프 알파벳/기호의 유한 세트입니다.

∈(\displaystyle b\in\Gamma)

는

b\in \Gamma

공백 기호(계산 중 어느 단계에서나 테이프에 무한히 자주 발생할 수 있는 유일한 기호)입니다.

\Sigma

σ

\ displaystyle \

\Sigma

Sigma }

\Gamma

、 b를 포함하지 않는 including \

displaystyle

\

\Gamma

Gamma

\Gamma

}의 서브셋인

σ

\

displaystyle

\ Sigma

\Sigma

,는 입력 기호 세트입니다.

R

Q\times

\

Gamma \to

Q

\times

\

Gamma \times \{R\}

는

\delta :Q\times \Gamma \to Q\times \Gamma \times \{R\}

전이 함수라고 불리는 함수이며, R은 오른쪽 이동(오른쪽 이동)입니다.

q_{0}\in Q

0

q_{0}\in Q

qQ

q_{0}\in Q

{

displaystyle q

_ {

0

} \

in

Q

q_{0}\in Q

。

F\subseteq Q

Q ( \

displaystyle

F \

subseteq

)는

F\subseteq Q

최종 상태 또는 수용 상태의 집합입니다.

그 기계는 항상 정규 언어를 받아들인다.언어를 공백으로 두지 않으려면 $집합$ F(HALT 상태)의 요소가 하나 이상 존재해야 합니다.

3스테이트, 2심볼 읽기 전용 튜링 머신의 예

테이프 기호	기입 기호	테이프의 이동	다음 상태	기입 기호	테이프의 이동	다음 상태	기입 기호	테이프의 이동	다음 상태
	현재 상태 A			현재 상태 B			현재 상태 C
0	1	R	B	1	R	A	1	R	B
1	1	R	C	1	R	B	1	N	정지하다

Q=\{A,B,C,\text{HALT}}\};

\Gamma =\{0,1\};

b=0

b=0

(디스플레이 스타일

b

=0

"빈칸";

σ

∅ {

displaystyle

\

Sigma

= \

\Sigma =\varnothing

varnothing

\Sigma =\varnothing

} , 빈

\Sigma =\varnothing

;

=

(\

displaystyle

\displaystyle

\delta =

=)

위

의 상태 표를

\delta =

하십시오.

q_{0}=A

0

=

(\displaystyle q_{0

}=

A

초기

q_{0}=A

;

F=

=

{\

displaystyle

F=} 최종

F=

상태의 단일 요소 세트

\{{\text{HALT}}\}

{

\{{\text{HALT}}\}

}

{\

displaystyle \{\text}

HALT

「」를 참조해 주세요.

메모들

^ ^a ^b Hopcroft 2001:
^ McCulloch와 Pitts(1943) :
^ Rabin과 Scott(1959) :
^ Gouda, Prabhakar, Application of Finite automata
^ Mogensen, Torben Ægidius (2011). "Lexical Analysis". Introduction to Compiler Design. Undergraduate Topics in Computer Science. London: Springer. p. 12. doi:10.1007/978-0-85729-829-4_1. ISBN 978-0-85729-828-7.
^ ^a ^b 로슨 (2004) 페이지 129
^ 사카로비치 (2009) 페이지 228
^ 로슨 (2004) 페이지 128
^ ^a ^b Grusho, A. A. (1973). "Limit distributions of certain characteristics of random automaton graphs". Mathematical Notes of the Academy of Sciences of the USSR. 4: 633–637. doi:10.1007/BF01095785. S2CID 121723743.
^ ^a ^b Cai, Xing Shi; Devroye, Luc (October 2017). "The graph structure of a deterministic automaton chosen at random". Random Structures & Algorithms. 51 (3): 428–458. arXiv:1504.06238. doi:10.1002/rsa.20707. S2CID 13013344.
^ Carayol, Arnaud; Nicaud, Cyril (February 2012). Distribution of the number of accessible states in a random deterministic automaton. STACS'12 (29th Symposium on Theoretical Aspects of Computer Science). Vol. 14. Paris, France. pp. 194–205.
^ John E. Hopcroft and Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Reading/MA: Addison-Wesley. ISBN 0-201-02988-X.
^ 사카로비치 (2009) (105)
^ 로슨 (2004) 페이지 63
^ https://www7.in.tum.de/um/courses/auto/ws1718/slides1718/04-Implementations_sets.pdf^{[베어 URL PDF]}
^ 로슨 (2004) 페이지 46
^ ^a ^b Gold, E. M. (1978). "Complexity of Automaton Identification from Given Data". Information and Control. 37 (3): 302–320. doi:10.1016/S0019-9958(78)90562-4.
^ De Vries, A. (28 June 2014). Finite Automata: Behavior and Synthesis. ISBN 9781483297293.
^ Lang, Kevin J. (1992). "Random DFA's can be approximately learned from sparse uniform examples". Proceedings of the fifth annual workshop on Computational learning theory - COLT '92. pp. 45–52. doi:10.1145/130385.130390. ISBN 089791497X. S2CID 7480497.
^ Oncina, J.; García, P. (1992). "Inferring Regular Languages in Polynomial Updated Time". Pattern Recognition and Image Analysis. Series in Machine Perception and Artificial Intelligence. Vol. 1. pp. 49–61. doi:10.1142/9789812797902_0004. ISBN 978-981-02-0881-3.
^ Lang, Kevin J.; Pearlmutter, Barak A.; Price, Rodney A. (1998). "Results of the Abbadingo one DFA learning competition and a new evidence-driven state merging algorithm". Grammatical Inference (PDF). Lecture Notes in Computer Science. Vol. 1433. pp. 1–12. doi:10.1007/BFb0054059. ISBN 978-3-540-64776-8.
^ Beyond EDSM Proceedings of the 6th International Colloquium on Grammatical Inference: Algorithms and Applications. 23 September 2002. pp. 37–48. ISBN 9783540442394.
^ Lucas, S.M.; Reynolds, T.J. (2005). "Learning deterministic finite automata with a smart state labeling evolutionary algorithm". IEEE Transactions on Pattern Analysis and Machine Intelligence. 27 (7): 1063–1074. doi:10.1109/TPAMI.2005.143. PMID 16013754. S2CID 14062047.
^ Heule, M. J. H. (2010). "Exact DFA Identification Using SAT Solvers". Grammatical Inference: Theoretical Results and Applications. Grammatical Inference: Theoretical Results and Applications. ICGI 2010. Lecture Notes in Computer Science. Lecture Notes in Computer Science. Vol. 6339. pp. 66–79. doi:10.1007/978-3-642-15488-1_7. ISBN 978-3-642-15487-4.
^ Heule, Marijn J. H.; Verwer, Sicco (2013). "Software model synthesis using satisfiability solvers". Empirical Software Engineering. 18 (4): 825–856. doi:10.1007/s10664-012-9222-z. hdl:2066/103766. S2CID 17865020.
^ Ulyantsev, Vladimir; Zakirzyanov, Ilya; Shalyto, Anatoly (2015). "BFS-Based Symmetry Breaking Predicates for DFA Identification". Language and Automata Theory and Applications. Lecture Notes in Computer Science. Vol. 8977. pp. 611–622. doi:10.1007/978-3-319-15579-1_48. ISBN 978-3-319-15578-4.
^ Davis, Martin; Ron Sigal; Elaine J. Weyuker (1994). Second Edition: Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science (2nd ed.). San Diego: Academic Press, Harcourt, Brace & Company. ISBN 0-12-206382-1.

레퍼런스

Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Introduction to Automata Theory, Languages, and Computation (2 ed.). Addison Wesley. ISBN 0-201-44124-1. Retrieved 19 November 2012.
Lawson, Mark V. (2004). Finite automata. Chapman and Hall/CRC. ISBN 1-58488-255-7. Zbl 1086.68074.
McCulloch, W. S.; Pitts, W. (1943). "A Logical Calculus of the Ideas Immanent in Nervous Activity". Bulletin of Mathematical Biophysics. 5 (4): 115–133. doi:10.1007/BF02478259. PMID 2185863.
Rabin, M. O.; Scott, D. (1959). "Finite automata and their decision problems". IBM J. Res. Dev. 3 (2): 114–125. doi:10.1147/rd.32.0114.
Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge: Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177.
Sipser, Michael (1997). Introduction to the Theory of Computation. Boston: PWS. ISBN 0-534-94728-X.. 섹션 1.1: 유한 오토마타, 페이지 31-47.섹션 4.1의 "일반언어에 관한 결정 가능한 문제" 서브섹션: 결정 가능한 언어, 페이지 152–155.4.4 DFA는 정규언어만을 받아들일 수 있다.

[Hopcroft_2001-1] Hopcroft 2001:

[2] McCulloch와 Pitts(1943) :

[3] Rabin과 Scott(1959) :

[4] Gouda, Prabhakar, Application of Finite automata

[Mogensen-5] Mogensen, Torben Ægidius (2011). "Lexical Analysis". Introduction to Compiler Design. Undergraduate Topics in Computer Science. London: Springer. p. 12. doi:10.1007/978-0-85729-829-4_1. ISBN 978-0-85729-828-7.

[Law129-6] 로슨 (2004) 페이지 129

[Sak228-7] 사카로비치 (2009) 페이지 228

[Law128-8] 로슨 (2004) 페이지 128

[Grusho-9] Grusho, A. A. (1973). "Limit distributions of certain characteristics of random automaton graphs". Mathematical Notes of the Academy of Sciences of the USSR. 4: 633–637. doi:10.1007/BF01095785. S2CID 121723743.

[Cai-10] Cai, Xing Shi; Devroye, Luc (October 2017). "The graph structure of a deterministic automaton chosen at random". Random Structures & Algorithms. 51 (3): 428–458. arXiv:1504.06238. doi:10.1002/rsa.20707. S2CID 13013344.

[11] Carayol, Arnaud; Nicaud, Cyril (February 2012). Distribution of the number of accessible states in a random deterministic automaton. STACS'12 (29th Symposium on Theoretical Aspects of Computer Science). Vol. 14. Paris, France. pp. 194–205.

[12] John E. Hopcroft and Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Reading/MA: Addison-Wesley. ISBN 0-201-02988-X.

[Sak105-13] 사카로비치 (2009) (105)

[Law63-14] 로슨 (2004) 페이지 63

[15] ttps://www7.in.tum.de/um/courses/auto/ws1718/slides1718/04-Implementations_sets.pdf^{[베어 URL PDF]}

[Law46-16] 로슨 (2004) 페이지 46

[Complexity_of_Automaton_Identificat-17] Gold, E. M. (1978). "Complexity of Automaton Identification from Given Data". Information and Control. 37 (3): 302–320. doi:10.1016/S0019-9958(78)90562-4.

[18] De Vries, A. (28 June 2014). Finite Automata: Behavior and Synthesis. ISBN 9781483297293.

[19] Lang, Kevin J. (1992). "Random DFA's can be approximately learned from sparse uniform examples". Proceedings of the fifth annual workshop on Computational learning theory - COLT '92. pp. 45–52. doi:10.1145/130385.130390. ISBN 089791497X. S2CID 7480497.

[20] Oncina, J.; García, P. (1992). "Inferring Regular Languages in Polynomial Updated Time". Pattern Recognition and Image Analysis. Series in Machine Perception and Artificial Intelligence. Vol. 1. pp. 49–61. doi:10.1142/9789812797902_0004. ISBN 978-981-02-0881-3.

[21] Lang, Kevin J.; Pearlmutter, Barak A.; Price, Rodney A. (1998). "Results of the Abbadingo one DFA learning competition and a new evidence-driven state merging algorithm". Grammatical Inference (PDF). Lecture Notes in Computer Science. Vol. 1433. pp. 1–12. doi:10.1007/BFb0054059. ISBN 978-3-540-64776-8.

[22] Beyond EDSM Proceedings of the 6th International Colloquium on Grammatical Inference: Algorithms and Applications. 23 September 2002. pp. 37–48. ISBN 9783540442394.

[23] Lucas, S.M.; Reynolds, T.J. (2005). "Learning deterministic finite automata with a smart state labeling evolutionary algorithm". IEEE Transactions on Pattern Analysis and Machine Intelligence. 27 (7): 1063–1074. doi:10.1109/TPAMI.2005.143. PMID 16013754. S2CID 14062047.

[HW1-24] Heule, M. J. H. (2010). "Exact DFA Identification Using SAT Solvers". Grammatical Inference: Theoretical Results and Applications. Grammatical Inference: Theoretical Results and Applications. ICGI 2010. Lecture Notes in Computer Science. Lecture Notes in Computer Science. Vol. 6339. pp. 66–79. doi:10.1007/978-3-642-15488-1_7. ISBN 978-3-642-15487-4.

[25] Heule, Marijn J. H.; Verwer, Sicco (2013). "Software model synthesis using satisfiability solvers". Empirical Software Engineering. 18 (4): 825–856. doi:10.1007/s10664-012-9222-z. hdl:2066/103766. S2CID 17865020.

[26] Ulyantsev, Vladimir; Zakirzyanov, Ilya; Shalyto, Anatoly (2015). "BFS-Based Symmetry Breaking Predicates for DFA Identification". Language and Automata Theory and Applications. Lecture Notes in Computer Science. Vol. 8977. pp. 611–622. doi:10.1007/978-3-319-15579-1_48. ISBN 978-3-319-15578-4.

[RORMTM-27] Davis, Martin; Ron Sigal; Elaine J. Weyuker (1994). Second Edition: Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science (2nd ed.). San Diego: Academic Press, Harcourt, Brace & Company. ISBN 0-12-206382-1.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[24]

[25]

[26]

[27]

Search

결정론적 유한 오토마톤

네임스페이스

더

목차

형식적 정의

예

바리에이션

완전하고 불완전하다

로컬 오토마타

랜덤성

닫힘 속성

전이모노이드로서

장점과 단점

라벨 부착 단어에서 DFA 식별

동등한 모델

읽기 전용 오른쪽 이동 튜링 기계

3스테이트, 2심볼 읽기 전용 튜링 머신의 예

「」를 참조해 주세요.

메모들

레퍼런스

Search

결정론적 유한 오토마톤

형식적 정의

예

바리에이션

완전하고 불완전하다

로컬 오토마타

랜덤성

닫힘 속성

전이모노이드로서

장점과 단점

라벨 부착 단어에서 DFA 식별

동등한 모델

읽기 전용 오른쪽 이동 튜링 기계

3스테이트, 2심볼 읽기 전용 튜링 머신의 예

「 」를 참조해 주세요.

메모들

레퍼런스

「」를 참조해 주세요.