2방향 유한자동화

컴퓨터 과학에서, 특히 오토마타 이론에서, 2방향 유한 자동화는 그것의 입력을 다시 읽을 수 있는 유한 자동이다.

이원 결정론적 유한자동화

2방향 결정론적 유한자동화(2DFA)는 추상 기계로, 이미 처리된 문자를 재방문할 수 있는 결정론적 유한자동화(DFA)의 일반화된 버전이다.DFA에서와 같이, 현재 문자를 기준으로 이들 사이에 전환이 있는 상태는 한정되어 있지만, 각 전환에는 입력의 위치를 왼쪽, 오른쪽 또는 같은 위치로 이동할지 여부를 나타내는 값으로도 라벨을 표시한다.마찬가지로, 2DFA는 작업 테이프가 없고 읽기 전용 입력 테이프만 있는 읽기 전용 튜링 기계로 볼 수 있다.

2DFA는 라빈과 스콧이 1959년 발표한 논문에서 소개했는데,^[1] 이들은 이들이 일방 DFA와 동등한 힘을 갖고 있음을 증명했다.즉, 2DFA에 의해 인식될 수 있는 모든 공식 언어는 각 문자를 순서대로 검사하고 소비하는 DFA에 의해 인식될 수 있다.DFA는 분명히 2DFA의 특별한 경우이기 때문에, 이것은 두 종류의 기계들이 정규 언어의 클래스를 정확하게 인식한다는 것을 암시한다.그러나 2DFA의 동등한 DFA는 기하급수적으로 많은 상태를 요구할 수 있으며, 2DFA는 일부 일반적인 문제에 대한 알고리즘을 훨씬 더 실제적으로 표현하도록 한다.

또한 2DFA는 일정한 양의 정보를 제품 구조(작업 테이프 상태와 제어 상태의 각 조합에 대한 상태)를 통해 유한 제어 상태로 통합할 수 있기 때문에 작업 테이프의 일정한 공간만 사용하는 읽기 전용 튜링 기계와 동등하다.

형식 설명

형식적으로 양방향 결정론적 유한 자동화는 $다음$과 같은 8투플로 설명할 수 있다: M${\displaystyle }$=${\displaystyle }$( ${\displaystyle Q}$ , ${\displaystyle ,}$ ,${\displaystyle \mathrm{L}}$, ${\displaystyle R}$,${\displaystyle \Delta }$ , ${\displaystyle s}$, t${\displaystyle }$) ${\displaystyle M=(Q,\Sigma ,L, R,\delta ,s,t,r)$

• ${\displaystyle Q}$ ${\displaystyle Q}$은(는) 유한하고 비어 있지 않은 상태 집합임
• ${\displaystyle \mathrm{\sigma }}$ ${\displaystyle \Sigma}$은(는) 유한하고 비어 있지 않은 입력 기호 집합이다.
• ${\displaystyle L}$ ${\displaystyle L}$이(가) 왼쪽 끝마커임
• ${\displaystyle R}$ ${\displaystyle R}$이(가) 오른쪽 끝마커임
• $[\displaystyle \property :Q\time (\Sigma \cup \{L,R\}}\오른쪽 화살표 Q\time \{\mathrm {왼쪽, 오른쪽} \}}}})$
• ${\displaystyle s}$ ${\displaystyle s}$이(가) 시작 상태임$$
• ${\displaystyle t}$ ${\displaystyle t}$이(가) 종료 상태임
• ${\displaystyle r}$ ${\displaystyle r}$이(가) 거부 상태임

또한 다음 두 가지 조건도 충족해야 한다.

• 모든 $Q{\displaystyle }$∈ ${\displaystyle Q}$ ${\displaystyle q\in$ Q$}$에 대해

${\displaystyle \Delta (q}$, L${\displaystyle }$)${\displaystyle }$= (${\displaystyle {}^{}}$ ${\displaystyle {\prime \mathrm{}}^{}}$, ${\displaystyle r\mathrm{}}$ i ${\displaystyle \mathrm{g}}$ ${\displaystyle \mathrm{t}}$ )${\displaystyle \delta (q,L)=(q^{\primate }}\mathrm {right}}}}$ 일부 ${\displaystyle q{}^{}}$for$$ Q ${\displaystystyleq^{}}\premy }\in$ Q$}$

${\displaystyle \Delta (q}$, R${\displaystyle }$)${\displaystyle }$= (${\displaystyle {}^{}}$ ${\displaystyle {\prime \mathrm{}}^{}}$, l ${\displaystyle \mathrm{e}}$ ${\displaystyle \mathrm{t}}$) ${\displaystyle \delta (q,R)=(q^{\primate }}\mathrm {left}}}}$ 일부 $q{\displaystyle {}^{}\mathrm{q<img\; alt="\{\backslash displaystyle\; \backslash delta\; (q,R)=(q^\{\backslash prime\; \},\backslash mathrm\; \{left\}\; )\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/b87e1e68651f67e7d03e17727009b912fdcac0ef"\; style="vertical-align:\; -0.838ex;\; width:17.88ex;\; height:3.009ex;"\; papago-attr-id="56">}}$ Q ${\displaystystyleq^{}\premy }\in$ Q$}$

그것은 포인터가 입력 단어의 양쪽 끝에 도달했을 때 어떤 전환이 가능해야 한다고 말한다.

• 모든 기호 ${\displaystyle \mathrm{\sigma }}$ ${\displaystyle \in }$ ∪${\displaystyle \{}$ { ${\displaystyle L}$ ${\displaystyle \}}$ ${\displaystyle \sigma \in \Sigma$ \in \sigma $\cup \{L\}}}$에 대해

${\displaystyle \delta (t,\sigma )=(t,R)}$

${\displaystyle \delta(r,\sigma )=(r,R)}$

${\displaystyle \delta (t,R)=(t,L)}$

${\displaystyle \delta(r,R)=(r,L)}$

그것은 일단 자동화가 승인 또는 거부 상태에 도달하면, 그 안에 영원히 머무르고 포인터는 가장 오른쪽의 기호로 가서 무한히 그곳에서 순환한다고 말한다.^[2]

2방향 비결정론적 유한자동화

2방향 비결정론적 유한자동화(2NFA)는 동일한 구성에서 다중 전환이 정의될 수 있다.그것의 전환 기능은

• ${\$$$$Q\time (\Sigma \cup \{L,R\}}}\오른쪽 화살표$ 2$^{Q\times$\{\$mathrm {왼쪽, 오른쪽$

표준 단방향 NFA와 마찬가지로, 2NFA는 가능한 연산 중 적어도 하나가 허용될 경우 문자열을 허용한다.2DFA와 마찬가지로 2NFA도 정규 언어만 허용한다.

2방향 교대 유한자동화

2방향 교번 유한자동화(2AFA)는 교번 유한자동화(AFA)의 2방향 확장이다.그것의 상태 집합은

• ${\displaystyle Q}$${\displaystyle }$= ${\displaystyle {}_{}}$${\displaystyle {\mathrm{}}_{}}$${\displaystyle {}_{}}$ ∪ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\$$displaystyle{\displaystyle {}_{}}$ $Q_{\exists$ $cap Q_{}=\empt$ $\}\}\}\}\}.$

$Q$$∃{\$과 Q$\$ {\$displaystyle$ Q_${\all }}}$에 있는$$ 상태를 실존적 레스프라고 한다.만유의실존적 상태에서 2AFA는 비결정론적으로 NFA와 같은 다음 상태를 선택하고, 결과 연산 중 적어도 하나가 허용될 경우 이를 받아들인다.범용 상태에서 2AFA는 모든 다음 상태로 이동하며, 모든 결과 계산이 허용될 경우 이를 받아들인다.

주의 복잡성 트레이드오프

결정론적 및 비결정적 및 비결정적 및 교대적 이원 및 일원 유한 자동자는 동일한 종류의 정규 언어를 수용한다.그러나 한 유형의 자동화를 다른 유형의 동등한 자동화로 변환하면 상태 수가 증가하게 된다.Christos Kapoutsis는^[3] $최악$의 경우 n$${\$displaystyle$n$$} -state 2DFA를 동등한 DFA로 $변환$하려면$$n${\displaystyle }$( ${\displaystyle n^{}}$-${\displaystyle 1}$ ) $displaystyle n(n^{n^}-(n-1)^{n}}}$ 상태가$$ 필요하다고 결정했다.$n{\displaystyle }$ ${\displaystyle n}$ -state$$ 2DFA 또는 2NFA를 NFA로 변환하는 경우, 최악의 경우 필요한 상태 수는${\displaystyle }$(${\displaystyle \genfrac{}{}{0ex}{}{}{}}$+ ${\displaystyle \genfrac{}{}{0ex}{}{1}{}}$)${\displaystyle }$= ${\displaystyle O}$( ${\displaystyle \frac{{}^{}}{\sqrt{}}}$) ${\$$O{\displaystyle }$$\left({\frac {4^{n}}{\sqrt{$n}}}}{\sqrt{$n}}\right)$^[4]$$. 래드너, 립톤 및 스톡마이어.$$n {\$displaystyle$ $n}$ $-state$ 2AFA는 ${n2^{n}}}$ 상태로$$ 변환할 수 있음을 증명했다.2AFA에서 NFA로 변환하려면 $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {\theta \mathrm{}(n}^{}}$ ${\displaystyle {\log }^{}}$ ${\displaystyle n^{}}$) ${\$$세타(n\log n)}$는 최악의 경우 게퍼트와 오호틴을 참조한다.^[5]

주 수가 다항식적으로 증가하는 것만으로 모든 2NFA가 2DFA로 전환될 수 있는지는 공공연한 문제다.문제는 사코다와 시퍼에 의해 제기되었는데,^[6] 계산 복잡성 이론에서 이를 P 대 NP 문제와 비교하였다.베르만과 링가스는^[7] 이 문제와 L 대 L 사이의 공식적인 관계를 발견했다.NL 개방 문제, 정확한 관계는 Kapoutsis를^[8] 참조하십시오.

스윕오토마타

스위프 오토마타는 입력 문자열을 왼쪽에서 오른쪽에서 왼쪽으로 번갈아 스위프를 만들어 엔드마커에서만 회전시켜 처리하는 특별한 종류의 2DFA이다.Sipser는^[9] 일련의 언어를 만들었고, 각각 n-state NFA에 의해 받아들여졌지만, ${\displaystyle {2n}^{}}$ ${\$ 이하의 상태를$$ 가진 어떤 광범위한 오토마타에도 받아들여지지 않았다.

이원 양자 유한자동화

2DFA의 개념은 1997년에 John Watross의 "On the Power of 2Way Quantum Limited State Automata"에 의해 양자컴퓨팅으로 일반화되었는데, 그는 이 기계들이 비정규 언어를 인식할 수 있고 따라서 DFA보다 더 강력하다는 것을 증명했다.^[10]

양방향 푸시다운 오토매틱

입력 테이프에서 어느 쪽으로든 이동할 수 있는 푸시다운 자동화를 양방향 푸시다운 자동(Two-way pushdown automaton, 2PDA)^[11]이라고 하며, 하트매니스, 루이스, 스턴스(1965)에 의해 연구되었다.^[12]아호, 홉크로프트, 울만(1968)^[13] 및 쿡(1971)^[14]은 결정론(2DPDA)과 비결정론(2NPDA) 양방향 푸시다운 오토마타에 의해 인식 가능한 언어의 클래스를 특징지었고, 그레이, 해리슨, 이바라(1967)는 이러한 언어의 폐쇄성을 조사했다.^[15]

참조