Абстрактная семья акцепторов

Абстрактное семейство акцепторов (AFA) — это группа обобщенных акцепторов . Неформально акцептор — это устройство с конечным управлением состоянием, конечным числом входных символов и внутренним хранилищем с функцией чтения и записи. Каждый акцептор имеет начальное состояние и набор принимающих состояний. Устройство считывает последовательность символов, переходя из состояния в состояние для каждого входного символа. Если устройство заканчивается в состоянии приема, говорят, что устройство принимает последовательность символов. Семейство акцепторов — это набор акцепторов с однотипным внутренним накопителем. Изучение AFA является частью теории AFL ( абстрактных семейств языков ).

Формальные определения

Расписание АФА

Схема AFA представляет собой упорядоченный кортеж из четырех $(\Gamma ,I,f,g)$, где

1. $\Gamma$ и $I$ являются непустыми абстрактными множествами.
2. $f$ это функция записи : $f:\Gamma ^{*}\times I\rightarrow \Gamma ^{*}\cup \{\emptyset \}$ (Примечание * — операция звезды Клини ).
3. $g$ — это функция чтения , отображение из $\Gamma ^{*}$ на конечные подмножества $\Gamma ^{*}$, такой, что $g(\epsilon )=\{\epsilon \}$ и $\epsilon$ находится в $g(\gamma )$ тогда и только тогда, когда $\gamma =\epsilon$. (Примечание $\epsilon$ это пустое слово).
4. Для каждого $\gamma$ в $g(\Gamma ^{*})$, есть элемент $1_{\gamma }$ в $I$ удовлетворяющий $f(\gamma ',1_{\gamma })=\gamma '$ для всех $\gamma '$ такой, что $\gamma$ находится в $g(\gamma ')$.
5. Для каждого u в I существует конечное множество $\Gamma _{u}$ ⊆ $\Gamma$, такой, что если $\Gamma _{1}$ ⊆ $\Gamma$, $\gamma$ находится в $\Gamma _{1}^{*}$, и $f(\gamma ,u)\neq \emptyset$, затем $f(\gamma ,u)$ находится в $(\Gamma _{1}\cup \Gamma _{u})^{*}$.

Абстрактная семья акцепторов

Абстрактное семейство акцепторов (AFA) представляет собой упорядоченную пару. $(\Omega ,{\mathcal {D}})$ такой, что:

1. $\Omega$ является упорядоченной шестеркой ( $K$, $\Sigma$, $\Gamma$, $I$, $f$, $g$), где
   1. ( $\Gamma$, $I$, $f$, $g$) — схема AFA; и
   2. $K$ и $\Sigma$ представляют собой бесконечные абстрактные множества
2. ${\mathcal {D}}$ это семья всех принимающих $D$ = ( $K_{1}$, $\Sigma _{1}$, $\delta$, $q_{0}$, $F$), где
   1. $K_{1}$ и $\Sigma _{1}$ являются конечными подмножествами $K$, и $\Sigma$ соответственно, $F$ ⊆ $K_{1}$, и $q_{0}$ находится в $K_{1}$; и
   2. $\delta$ (называемая функцией перехода ) представляет собой отображение из $K_{1}\times (\Sigma _{1}\cup \{\epsilon \})\times g(\Gamma ^{*})$ на конечные подмножества $K_{1}\times I$ такой, что набор $G_{D}=\{\gamma$ | $\delta (q,a,\gamma )$ ≠ ø для некоторых $q$ и $a\}$ конечно.

Для данного акцептора пусть $\vdash$ быть отношением к $K_{1}\times \Sigma _{1}^{*}\times \Gamma ^{*}$ определяется: Для $a$ в $\Sigma _{1}\cup \{\epsilon \}$, $(p,aw,\gamma )\vdash (p',w,\gamma ')$ если существует ${\overline {\gamma }}$ и $u$ такой, что ${\overline {\gamma }}$ находится в $g(\gamma )$, $(p',u)$ находится в $\delta (p,a,{\overline {\gamma }})$ и $f(\gamma ,u)=\gamma '$. Позволять $\vdash ^{*}$ обозначим замыкание транзитивное $\vdash$.

Позволять $(\Omega ,{\mathcal {D}})$ быть AFA и $D$ = ( $K_{1}$, $\Sigma _{1}$, $\delta$, $q_{0}$, $F$) быть в $D$. Определять $L(D)$ быть набором $\{w\in \Sigma _{1}^{*}|\exists q\in F.(q_{0},w,\epsilon )\vdash ^{*}(q,\epsilon ,\epsilon )\}$. Для каждого подмножества ${\mathcal {E}}$ из ${\mathcal {D}}$, позволять ${\mathcal {L}}({\mathcal {E}})=\{L(D)|D\in {\mathcal {E}}\}$.

Определять $L_{f}(D)$ быть набором $\{w\in \Sigma _{1}^{*}|\exists (q\in F)\exists (\gamma \in \Gamma ^{*}).(q_{0},w,\epsilon )\vdash ^{*}(q,\epsilon ,\gamma )\}$. Для каждого подмножества ${\mathcal {E}}$ из ${\mathcal {D}}$, позволять ${\mathcal {L}}_{f}({\mathcal {E}})=\{L_{f}(D)|D\in {\mathcal {E}}\}$.

Неформальное обсуждение

Расписание АФА

Схема AFA определяет хранилище или память с функциями чтения и записи. Символы в $\Gamma$ называются символами хранения , а символы в $I$ называются инструкциями . Функция записи $f$ возвращает новое состояние хранения с учетом текущего состояния хранилища и инструкции. Функция чтения $g$ возвращает текущее состояние памяти. Условие (3) гарантирует, что пустая конфигурация хранилища отличается от других конфигураций. Условие (4) требует наличия идентификационной инструкции, которая позволяет состоянию памяти оставаться неизменным, пока получатель меняет состояние или продвигает ввод. Условие (5) обеспечивает конечность множества символов хранения для любого данного акцептора.

Абстрактная семья акцепторов

AFA — это набор всех акцепторов по заданной паре алфавитов состояния и входных данных, которые имеют один и тот же механизм хранения, определенный данной схемой AFA. $\vdash$ Отношение определяет один шаг в работе акцептора. $L_{f}(D)$ набор слов, принятый акцептором $D$ заставляя принимающего войти в принимающее состояние. $L(D)$ набор слов, принятый акцептором $D$ за счет того, что акцептор одновременно переходит в принимающее состояние и имеет пустое хранилище.

Абстрактные акцепторы, определенные AFA, являются обобщениями других типов акцепторов (например, автоматов с конечным состоянием , автоматов с выталкиванием и т. д.). Они имеют конечное управление состоянием, как и другие автоматы, но их внутренняя память может сильно отличаться от стеков и лент, используемых в классических автоматах.

Результаты теории AFL

Главный результат теории AFL состоит в том, что семейство языков ${\mathcal {L}}$ является полным AFL тогда и только тогда, когда ${\mathcal {L}}={\mathcal {L}}({\mathcal {D}})$ для некоторых АФА $(\Omega ,{\mathcal {D}})$. Не менее важен и результат, который ${\mathcal {L}}$ является полным полу-AFL тогда и только тогда, когда ${\mathcal {L}}={\mathcal {L}}_{f}({\mathcal {D}})$ для некоторых АФА $(\Omega ,{\mathcal {D}})$.

Происхождение

Сеймур Гинзбург из Университета Южной Калифорнии и Шейла Грейбах из Гарвардского университета впервые представили свою статью по теории AFL на восьмом ежегодном симпозиуме IEEE по теории коммутации и автоматов в 1967 году.