추상적 수용자 가족

추상적인 수용자 가족(AFA)은 일반화된 수용자의 그룹이다.비공식적으로, 수용자는 유한 상태 제어, 유한한 수의 입력 기호를 가진 장치, 그리고 읽기 및 쓰기 기능을 가진 내부 저장소를 말한다.각 수용자는 출발 상태와 일련의 수용 상태를 가진다.장치는 각 입력 기호에 대해 상태에서 상태로 전환하면서 일련의 기호를 읽는다.기기가 수용 상태로 끝나면 기호의 순서를 받아들인다고 한다.수용자 가족이란 내부 매장이 같은 유형의 수용자 집단을 말한다.AFA에 대한 연구는 AFL 이론의 일부다.^[1]

형식 정의

AFA 스키마

${\displaystyle \mathrm{AFA}}$ 스키마는 주문된 4-투플(${\displaystyle }$is , I , f${\displaystyle }$, ${\displaystyle g}$) ${\displaystyle(\Gamma ,I,f,g)$이며$,$ 여기서

1. ${\displaystyle \mathrm{\gamma }}$ ${\displaystyle \Gamma }$ 및 $I{\displaystyle }$ ${\displaystyle I}$은(는) 비어 있지 않은 추상 집합이다.
2. ${\displaystyle f}$ ${\$displaystyle $f}$은(는) $쓰기{\displaystyle }$ 함수: f ${\displaystyle :}$ ${\displaystyle {}^{}}$→ × I →${\displaystyle {\mathrm{}}^{}\mathrm{}{}^{}}$ ${\displaystyle$ f$:\Gamma ^{*}\time I\rightarrow$\grow \$gamma ^{*}\$cup $\\\\\\\\\\cup$ \{\{\\\\\\\\\\\\\\\\cup$}}}}}}}}}}}}}}}}}}}}}}}}}}$
3. ${\displaystyle g}$ is the read function, a mapping from ${\displaystyle \Gamma ^{*}}$ into the finite subsets of ${\displaystyle \Gamma ^{*}}$, such that ${\displaystyle g(\epsilon )=\{\epsilon \}}$ and ${\displaystyle \epsilon }$ is in ${\displaystyle g(\gamma )}$ if$\gamma {\displaystyle }$= ${\displaystyle ϵ}$ ${\displaystyle \gamma =\epsilon }$ .$$(N.B. $ϵ{\displaystyle }$ ${\displaystyle \epsilon }$이(가) 빈 단어일 경우에만$$ 해당).
4. For each ${\displaystyle \gamma }$ in ${\displaystyle g(\Gamma ^{*})}$, there is an element ${\displaystyle 1_{\gamma }}$ in ${\displaystyle I}$ satisfying ${\displaystyle f(\gamma ',1_{\gamma })=\gamma '}$ for all ${\displaystyle \gamma '}$ such that${\displaystyle \gamma }$ ${\displaystyle \gamma$}이$($가) $g($${\displaystyle {}^{}}$) )${\displaystyle$g(\displaystyle g$(\property')}$에 있음
5. For each u in I, there exists a finite set ${\displaystyle \Gamma _{u}}$ ⊆ ${\displaystyle \Gamma }$, such that if ${\displaystyle \Gamma _{1}}$ ⊆ ${\displaystyle \Gamma }$, ${\displaystyle \gamma }$ is in ${\displaystyle \Gamma _{1}^{*}}$, and ${\displayst$$yle f(\gamma,u)\neq \emptyset$ 그 다음 $f{\displaystyle (}$ ${\displaystyle ,,}$ ${\displaystyle {\mathrm{}}_{}}$${\displaystyle }$)$${\$displaystyle$ f$(\$displaystyle$){\$에 있다$.$

추상적 수용자 가족

추상적 수용자 제품군(AFA)은 다음과 같은$$ 순서 쌍$({\displaystyle \mathrm{\Omega }}$, ${\displaystyle D}$) ${\displaystyle(\Oomega ,{\mathcal{D})$이다.

1. ${\displaystyle \mathrm{\Omega }}$ ${\displaystyle \Oomega}$은(는) 6투플($K{\displaystyle \mathrm{}}$ ${\$$displaystyle$$\$$Sigma },$ $\gamma {\displaystyle \mathrm{}}$ ${\$$displaystyle$ \Gamma$$}, I {\$displaystyle{\displaystyle }$I}, f {\$displaystystyf$ {\g}, {\displaystystystystystystystystystystystystystystytype g}, ${\$},$$ {\$down$ g$},$ {
   1. ( ${\displaystyle \mathrm{}}$ ${\displaystyle \Gamma$ $\},$ $I{\displaystyle }$ ${\displaystyle$ I$\},$ f ${\displaystyle f$ $g{\displaystyle }$ ${\displaysty g$는 AFA 스키마로서,
   2. ${\displaystyle K}$ ${\displaystyle K}$ 및$$ $\sigma {\displaystyle \mathrm{}}$ ${\displaystyle \Sigma}$은(는) 무한 추상 집합임
2. ${\displaystyle {\mathcal {D}}}$ is the family of all acceptors ${\displaystyle D}$ = (${\displaystyle K_{1}}$, ${\displaystyle \Sigma _{1}}$, ${\displaystyle \delta }$, ${\displaystyle q_{0}}$, ${\displaystyle F}$), where
   1. ${\displaystyle K_{1}}$ and ${\displaystyle \Sigma _{1}}$ are finite subsets of ${\displaystyle K}$, and ${\displaystyle \Sigma }$ respectively, ${\displaystyle F}$ ⊆ ${\displaystyle K_{1}}$, and ${\displaystyle q_{0}}$ is in ${\displaystyle K_{1}}$; and
   2. ${\displaystyle \delta }$ (called the transition function) is a mapping from ${\displaystyle K_{1}\times (\Sigma _{1}\cup \{\epsilon \})\times g(\Gamma ^{*})}$ into the finite subsets of ${\displaystyle K_{1}\times I}$ such that the set ${\displaystyle$$G_{D}=\\\\gamma$${\displaystyle (q}$, ${\displaystyle a}$ ,${\displaystyle \gamma }$) ${\displaystyle \delta (q,a,\gamma )}$ ≠$$ ø 일부 $q{\displaystyle }$ ${\displaysty$ $q$$}$ 및 a$$${\displaystyle \}}$ ${\displaysty$ a$\}$는 유한하다$$.

For a given acceptor, let ${\displaystyle \vdash }$ be the relation on ${\displaystyle K_{1}\times \Sigma _{1}^{*}\times \Gamma ^{*}}$ defined by: For ${\displaystyle a}$ in ${\displaystyle \Sigma _{1}\cup \{\epsilon \}}$, ${\dis$$playstyle (p,aw,\gamma )\vdash (p',w,\gamma ')}$ if there exists a ${\displaystyle {\overline {\gamma }}}$ and ${\displaystyle u}$ such that ${\displaystyle {\overline {\gamma }}}$ is in ${\displaystyle g(\gamma )}$, ${\displaystyle (p',u)}$ is in ${\d$$isplaystyle \delta(p,a,{\overline {\gamma }})$와 $f{\displaystyle (u}$)${\displaystyle }$=${\displaystyle {}^{}}$ ${\$ f$(\gamma,u)=\gamma '}}.$$$let ${\displaystyle \vdash ^*}$의 전이적 폐쇄를 나타낸다$$$.$

Let ${\displaystyle (\Omega ,{\mathcal {D}})}$ be an AFA and ${\displaystyle D}$ = (${\displaystyle K_{1}}$, ${\displaystyle \Sigma _{1}}$, ${\displaystyle \delta }$, ${\displaystyle q_{0}}$, ${\displaystyle F}$) be in ${\displaystyle D}$. Define ${\displaystyle L(D}$${\displaystyle L(D)}$ to be the set ${\displaystyle \{w\in \Sigma _{1}^{*} \exists q\in F.(q_{0},w,\epsilon )\vdash ^{*}(q,\epsilon ,\epsilon )\}}$. For each subset ${\displaystyle {\mathcal {E}}}$ of ${\displaystyle {\mathcal {D}}}$, let${\displaystyle L\mathcal{}}$( E${\displaystyle }$)${\displaystyle }$=${\displaystyle }${ ${\displaystyle L}$ ${\displaystyle (D}$) ${\displaystyle D}$ ${\displaystyle \in }$ ${\displaystyle E\}}$ ${\displaystyle {\mathcal{{\mathcal{E}}}=\{L(D)$ D$\in {\mathcal {E$

Define ${\displaystyle L_{f}(D)}$ to be the set ${\displaystyle \{w\in \Sigma _{1}^{*} \exists (q\in F)\exists (\gamma \in \Gamma ^{*}).$$(q_{0},w,\epsilon )\vdash ^{*}(q,\epsilon ,\gamma )\}}$. For each subset ${\displaystyle {\mathcal {E}}}$ of ${\displaystyle {\mathcal {D}}}$, let ${\displaystyle {\mathcal {L}}_{f}({\mathcal {E}})=\{L_{f}(D) D\in {\mathcal {E}}\}}$.

비공식 토론

AFA 스키마

AFA 스키마는 읽기 및 쓰기 기능이 있는 저장소와 메모리를 정의한다.$\gamma {\displaystyle \mathrm{}}$ ${\displaystyle \Gamma}$의 기호를$$ 스토리지 기호라고 하고, $I{\displaystyle }${\$displaystyle$I}의$$ 기호를 지침이라고 한다.쓰기 함수 $f{\displaystyle }$ ${\displaystyle f}$은(는) 현재 스토리지 상태와 명령이 지정된 새 스토리지 상태를 반환하며$$,읽기 함수 $g{\displaystyle }$ ${\displaystyle g}$은(는) 현재 메모리 상태를 반환한다$$.상태 (3)은 빈 저장소 구성이 다른 구성과 구별되도록 보장한다.조건 (4)은 수신자가 상태를 변경하거나 입력을 진전시키는 동안 메모리 상태를 변경하지 않고 유지할 수 있는 ID 명령이 필요하다.조건 (5)은 주어진 수용자에 대한 저장 기호 세트가 유한함을 보장한다.

추상적 수용자 가족

AFA는 주어진 AFA 스키마에 의해 정의된 동일한 저장 메커니즘을 가진 입력 알파벳과 특정 상태 쌍에 걸친 모든 수용자의 집합이다.$▼{\displaystyle }$ ${\displaystyle \vdash }$ 관계는$$ 수용자 작동의 한 단계를 정의한다.${\displaystyle L_{}}$ ${\displaystyle f_{}}$( ${\displaystyle D}$) ${\displaystyle L_{f}(D)}$은(는) 수락자가 수락 상태를 입력하도록 하여$$ 수락자 $D{\displaystyle }$ ${\displaystyle D}$에 의해 수락된 단어 모음입니다$$.${\displaystyle L}$( ${\displaystyle D}$) ${\displaystyle L(D)}$은(는) 수락자가 수락 상태로 동시에 들어가 빈 저장소를 가지도록 하여$$ 수락자 $D{\displaystyle }$ ${\displaystyle D}$에서 수락한 단어 모음입니다.

AFA에 의해 정의된 추상적 수용자는 다른 유형의 수용자(예: 유한 상태 자동자, 푸시다운 자동자 등)의 일반화다.그들은 다른 오토마타처럼 유한한 상태 제어장치를 가지고 있지만, 그들의 내부 저장장치는 고전적인 오토마타에서 사용되는 스택과 테이프와는 매우 다를 수 있다.

AFL 이론의 결과

The main result from AFL theory is that a family of languages ${\displaystyle {\mathcal {L}}}$ is a full AFL if and only if ${\displaystyle {\mathcal {L}}={\mathcal {L}}({\mathcal {D}})}$ for some AFA ${\displaystyle (\Omega ,{\mathcal {D}})}$. Equally important is the result that ${\displaystyle }$${\displaystyle {\mathcal {L}}}$ is a full semi-AFL if and only if ${\displaystyle {\mathcal {L}}={\mathcal {L}}_{f}({\mathcal {D}})}$ for some AFA ${\displaystyle (\Omega ,{\mathcal {D}})}$.

오리진스

Southern California 대학의 Symour Ginsburg와 하버드 대학의 Sheila Greibach는 1967년 IEEE 제8차 연례 전환 및 오토마타 이론 심포지엄에서 AFL 이론 논문을 처음 발표했다.^[2]

참조