확률론적 자동화

이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다. 기술 세부 정보를 삭제하지 않고 비전문가가 이해할 수 있도록 개선하십시오.(2021년 1월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

수학과 컴퓨터 과학에서 확률론적 자동화(PA)는 비결정론적 유한 자동화의 일반화로서, 전환함수로 전환되어 전환 매트릭스로 전환될 확률을 포함한다.따라서 확률론적 자동화는 또한 마르코프 체인과 유한 유형의 하위 교대조의 개념을 일반화한다.확률론적 오토마타에 의해 인식된 언어들을 확률 언어라고 부른다; 이것들은 부분집합으로서의 정규 언어를 포함한다.확률적인 언어의 수는 헤아릴 수 없다.

이 개념은 1963년 마이클 O. 라빈에 의해 도입되었다.^[1] 특정한 특별한 경우는 라빈 오토마타(Ω-automata, 일명 라빈 오토마타)의 하위 등급과 혼동하지 않는 경우도 있다.최근 몇 년 동안, 양자 유한 자동인 양자 확률 측면에서 변종이 형성되었다.

비공식 설명

주어진 초기 상태와 입력 문자에 대해 결정론적 유한자동화(DFA)는 정확히 하나의 다음 상태를 가지며, 비결정론적 유한자동화(NFA)는 일련의 다음 상태를 가진다.확률론적 자동자(PA)는 대신 다음 상태의 가중 집합(또는 벡터)을 가지며, 여기서 가중치는 1로 합해야 하므로 확률로 해석할 수 있다(가연성 벡터가 된다).개념 상태와 허용도 이러한 가중치의 도입을 반영하도록 수정해야 한다.주어진 단계로서 기계의 상태는 또한 이제 확률적인 상태의 벡터로 표현되어야 하며, 전체 수용가능성이 어느 정도 컷오프를 초과할 경우 허용되는 상태가 된다.

PA는 어떤 의미에서 결정론에서 비결정론적인 단계로, 다음 주들의 집합은 허용하지만 가중치에 제한이 있기 때문이다.그러나 PA는 실제 숫자의 개념을 이용하여 DFA와 NFA의 정의에 모두 없는 가중치를 정의하기 때문에 이것은 다소 오해의 소지가 있다.이러한 추가적인 자유는 그들이 비합리적인 파라미터를 가진 p-adic 언어와 같이 규칙적이지 않은 언어를 결정할 수 있게 해준다.이와 같이 PA는 DFA와 NFA 둘 다(유명히 동등하게 강력한 것으로 알려져 있다)보다 더 강력하다.

형식 정의

The probabilistic automaton may be defined as an extension of a nondeterministic finite automaton ${\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}$, together with two probabilities: the probability ${\displaystyle P}$ of a particular state transition taking place, and with the initial state ${\disp$$레이스타일 q_{0}}}$은(는) 주어진 초기 상태에 자동이 존재할 확률을 제공하는 확률 벡터로 대체된다$$.

일반적인 비결정론적 유한 자동화에 대해서는 다음과 같이 한다.

• 상태의 $유한{\displaystyle }$집합 Q {\$displaystyle$ Q$}$
• 유한 집합의 입력 기호$\sigma {\displaystyle \mathrm{}}$ {\$displaystyle$ \$Sigma }$
• 전환 함수 $\Delta {\displaystyle }$: ${\displaystyle Q}$ ${\displaystyle \times }$ ${\displaystyle \mathrm{\sigma }}$→ ${\displaystyle \mathrm{\wp }}$( Q${\displaystyle }$) ${\displaystyle \delta$:$Q\time \Sigma \to \wp(Q)}$
• 승인(또는 최종)으로 구분되는$$ 상태 $F{\displaystyle }$ ${\displaystyle F}$의 집합 F${\displaystyle \mathrm{states}}$ Q ${\displaystyle F\subseteq$ Q$\}.$

여기서 $\wp {\displaystyle \mathrm{}}$( ${\displaystyle Q}$) ${\displaystyle \wp (Q)}$은 $Q{\displaystyle }$ ${\displaystyle Q$의 전원 세트를 나타낸다.

커서를 사용함으로써 전환함수 $\Delta {\displaystyle }$: ${\displaystyle Q}$ ${\displaystyle \times }$ ${\displaystyle \mathrm{\sigma }}$→ ${\displaystyle \mathrm{\wp }}$ ${\displaystyle (Q}$) ${\displaystyle \delta$:비결정적 유한 자동화의 $Q$$\time \Sigma \to \wp (Q)}$은(는) 멤버쉽 함수로 쓸 수 있다.

$[\displaystyle \property :Q\time \Sigma \time Q\to \{0,1\}}$

따라서 $\Delta {\displaystyle (q}$,${\displaystyle a}$ ,${\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {}^{}}$ )${\displaystyle }$= ${\displaystyle 1}${\$displaystyle \delta (q$${\displaystyle ,}$$a,$q^{\$prime }=1},$ $a$}, q,premium $Δ$에서 ${\$premium Δ(prime$){}\premium$ $0}$인 경우.큐레이션된 전환 함수는 매트릭스 항목이 있는 매트릭스로 이해할 수 있다.

${\displaystyle \left[\theta _{a}\right]_{q^{\prime }=\premium(q,a,q^{\prime }})}$

매트릭스 ${\$는 정사각형 매트릭스로$$, 이 매트릭스의 항목은 0이거나 1이며, 전환 $q{\displaystyle \stackrel{}{}}$→ q →$${\$displaystystyle q{a}{\rightarrow q^{\prime}}}}}}}}}}}}$이 NFA에서 허용되는지 나타낸다.그러한 전환 매트릭스는 항상 비결정적 유한 자동화에 대해 정의된다.

확률론적 자동화는 이러한 행렬을 알파벳 ${\displaystyle \Sigma }$의 각 기호 a에$$대해 오른쪽 확률론적 행렬 ${\displaystyle P_{}}$ $a{\displaystyle {}_{}}$ ${\$의 패밀리로$$ 대체하여 전환 확률을 다음과 같이 제공한다.

${\displaystyle \left[P_{a}\right]_{q^{\prime }}$

어떤 주에서 어떤 주(州)로 주(州)가 바뀌려면 당연히 확률 1과 함께 일어나야 하고, 따라서 사람은 반드시

${\displaystyle \sum _{q^{\premy }}\왼쪽[P_{a}\right]_{q^{\primy }}=1}$

모든 입력 문자 $a{\displaystyle }$ ${\displaystyle a}$ 및 내부$$ 상태 $q{\displaystyle }$ ${\displaystyle q$ 확률론적 자동화의 초기 상태는 1:에 $추가$된 개별 초기 상태 q {\displaystyle $q$의 확률인 행 벡터 v$$${\displaystyle$ $v}$에 의해 주어진다$.$

${\displaystyle \sum _{q}\왼쪽[v\right]_{q}=1}$

전환 매트릭스는 오른쪽에 작용하여, ${\displaystyle \mathrm{입력}}$ 문자열을 $소비$한 후, 확률론적 자동화의 상태가 b ${\displaystyle c}$ ${\displaystyle abc}$이$($가) 될 것이다.

${\displaystyle vP_{a}P_{b}P_{c}}}$

특히 확률론적 자동화의 상태는 어떤 두 개의 확률론적 매트릭스의 산물이 확률론적 매트릭스이고, 확률론적 벡터와 확률론적 매트릭스의 산물이 다시 확률론적 벡터이기 때문에 항상 확률론적 벡터다.이 벡터를 상태 분포라고 부르기도 하는데, 이는 이산 확률 분포임을 강조한다.

형식적으로 확률론적 자동화의 정의는 비결정론적 자동화의 역학을 요구하지 않으며, 이 역학은 폐기될 수 있다.Formally, a probabilistic automaton PA is defined as the tuple ${\displaystyle (Q,\Sigma ,P,v,F)}$. A Rabin automaton is one for which the initial distribution ${\displaystyle v}$ is a coordinate vector; that is, has zero for all but one entries, and the remaining entry being one.

스토카틱어군

확률론적 오토마타가 인정하는 언어 집합을 확률언어라고 한다.그것들은 하위 집합으로서 정규 언어를 포함한다.

Let $F{\displaystyle }$= ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle Q}$ ${\displaystyle F=Q_{\text{accept}\subseteq Q}$는 자동화의 "수락" 또는 "최종" 상태의 집합이다$$.표기법 남용으로 $Q{\displaystyle {}_{}}$ ${\$$accept$$}}}$은$($는) Q accept {\$displaystyle$Q_{\$text{$accept$}}$의 멤버십 함수인 컬럼 벡터로 이해될$$ 수 있다$.$ 즉, Q ${\displaystyle {\text{accept}}_{}}${\$displaystystylease Q_{{{{{\}$에 해당하는 위치에 1이 있다$.$그녀의 지혜이 벡터는 스칼라를 형성하기 위해 내부 상태 확률과 수축될 수 있다.그런 다음 특정 자동화에 의해 인식되는 언어는 다음과 같이 정의된다.

${\displaystyle L_{\eta }=\{s\in \Sigma ^{*}\vert vP_{s}Q_{\text{accept}}\eta \}}}}}$

여기서 $\sigma {\displaystyle {\mathrm{}}^{}}$ $∗{\$은 $알파벳{\displaystyle \mathrm{}}$ {$${\$displaystyle \Sigma$}의 모든 문자열 집합이다$$($$따라서 *는 클레인 별이다).언어는 일반적으로 ≤< 1 < 1 ${\displaystyle$0\leq $\eta$ <1}의범위 내에 있는 것으로 간주되는$$컷포인트 $\eta {\displaystyle }$ ${\displaystyle \eta }$의 값에 따라 달라진다

A language is called η-stochastic if and only if there exists some PA that recognizes the language, for fixed ${\displaystyle \eta }$. A language is called stochastic if and only if there is some ${\displaystyle 0\leq \eta <1}$ for which ${\displaystyle L_{\eta }}$ is η-stochastic.

컷포인트는 과 같은 > 0 $[\displaystyle \delta >0}$이(가) 존재하는 경우에만 절연 컷포인트라고 한다.

${\displaystyle \vert vP_{\text{accept}-\eta \vert \geq \delta }$

${\displaystyle {\mathrm{}}^{}}$ s ${\displaystyle \in }$ ∗ ${\displaystyle {\ast }^{}}$ ${\$에 대해

특성.

모든 정규어는 확률적이며, 더욱 강하게 모든 정규어는 language-stochastic이다.약한 반향은 모든 0-stochastic 언어가 규칙적이라는 것이다. 그러나 일반적인 반향은 규칙적이지 않은 확률적 언어가 있다.

모든 η-stopchastic 언어는 약 < $<<\displaystyle 0><\eta <1}$에 대해 확률적이다

모든 확률적인 언어는 라빈 오토매틱으로 대표할 수 있다.

{ ${\displaystyle \eta$}이$($가) 분리된 절단점이라면$$ L ${\displaystyle l_{}}$ ${\$은(는) 정규 언어다$$.

p-adic 언어

p-adic 언어는 규칙적이지 않은 확률적 언어의 예를 제공하며, 확률적 언어의 수가 헤아릴 수 없다는 것도 보여준다.p-adic 언어는 문자열 집합으로 정의된다.

${\displaystyle L_{\eta }=\{n_{1}n_{2}n_{3}\ldots \vert 0\leq n_{k}<p{\text{ 및 }}{0.n_{1}n_{2}n_{3}\ldots >\eta \}}}}}}}.$

$0{\displaystyle \mathrm{},}$ ${\displaystyle 1}$,${\displaystyle 2}$,${\displaystyle }$…${\displaystyle }$(${\displaystyle p}$- ${\displaystyle 1}$) ${\displaystyle 0,1,2,\ldots,$ ($p-1$에 .

즉, p-adic 언어는 기초-p로 작성된 [0, 1]의 실수의 집합에 불과하며, $they{\displaystyle }$ ${\displaystyle \eta }$보다 크므로$,$ 모든 p-adic 언어가 확률적이라는 것을 보여주는 것은 간단하다.^[2]특히 확률적 언어의 수가 헤아릴 수 없다는 것을 암시한다.p-adic 언어는 $\eta {\displaystyle }$ ${\displaystyle \eta }$이(가) 합리적인$$ 경우에만 정규 언어다.

일반화

확률론적 자동화는 기하학적 해석을 가지고 있는데, 상태 벡터는 직교 코너와 반대되는 표준 심플렉스 면에 사는 점으로 이해할 수 있다.전환 매트릭스는 그 점에 작용하는 단조로운 형태를 형성한다.이것은 어떤 일반적인 위상학적 공간에서 나온 점을 갖는 것에 의해 일반화될 수 있는 반면, 전환 매트릭스는 위상학적 공간에 작용하는 연산자의 집합에서 선택되어 반유토마톤을 형성한다.컷포인트가 적절히 일반화되면 위상적인 자동화를 갖게 된다.

그러한 일반화의 예는 양자 유한 자동이다. 여기서 자동 상태는 복잡한 투영 공간의 한 점에 의해 표현되는 반면 전환 매트릭스는 단일 집단에서 선택한 고정 집합이다.컷포인트는 양자 각도의 최대값의 한계로 이해된다.

메모들

참조

• Salomaa, Arto (1969). "Finite nondeterministic and probabilistic automata". Theory of Automata. Oxford: Pergamon Press.