14.5: Машина моноїда

Last updated
Save as PDF

Page ID: 64994

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Будь-який скінченний моноїд$[M;*]$ може бути представлений у вигляді скінченної машини з вхідними та державними наборами, рівними Вихід машини тут буде проігнорований, так як він буде повторювати поточний стан машини.$M\text{.}$ Машини такого типу називаються державними машинами. Можна показати, що все, що можна зробити за допомогою кінцевої машини, можна зробити з державною машиною; однак існує компроміс. Зазвичай державні машини, що виконують певну функцію, більш складні, ніж загальні скінченностанні машини.

Визначення $\PageIndex{1}$: Machine of a Monoid

Якщо$[M;*]$ є скінченним моноїдом, то машина$M\text{,}$ позначеного стану$m(M)\text{,}$ - це державна машина з набором$M\text{,}$ вхідних даних$M\text{,}$ та функцією наступного стану,$t : M\times M \to M$ визначеною$t(s, x) = s * x\text{.}$

Приклад$\PageIndex{1}$

Ми побудуємо машину моноїда$\left[\mathbb{Z}_2;+_2\right]\text{.}$ Як згадувалося вище, набір стану і вхідний набір обидва$\mathbb{Z}_2\text{.}$ Наступна функція стану визначається діаграмою$t(s, x) = s +_2 x\text{.}$ переходу для$m\left(\mathbb{Z}_2\right)$ відображається на рис$\PageIndex{1}$. Зверніть увагу, як вона ідентична діаграмі переходу перевірки парності, яка має асоційований моноїд, який був ізоморфним до$\left[\mathbb{Z}_2;+_2\right].$

$clipboard_eb6f73f09a57dc4e31cc62aa414f8f062.png$ Малюнок$\PageIndex{1}$: Машина$[\mathbb{Z}_2;+_{2}]$

Приклад$\PageIndex{2}$

Діаграма переходу моноїдів$\left[\mathbb{Z}_2;\times _2\right]$ і$\left[\mathbb{Z}_3;\times _3\right]$ відображається на рис$\PageIndex{2}$.

$clipboard_ec12ddd668fd136247ffd94b51ad2f18b.png$ Малюнок$\PageIndex{2}$: Машини$[\mathbb{Z}_2;\times_{2}]$ і$\mathbb{Z}_{3};\times_{3}]$

Приклад$\PageIndex{3}$

$U$Дозволяти моноид, який ми отримали від одиниці часу затримки машини (приклад 14.4.2). Ми бачили, що машина моноїда перевірки парності по суті є перевіркою парності. Чи отримаємо ми машину затримки одиниці часу, коли ми будуємо машину$U\text{?}$ Ми не можемо очікувати отримати точно таку ж машину, тому що машина затримки одиниці часу не є державною машиною, а машина моноїда - державна машина. Однак ми побачимо, що наша нова машина здатна повідомити нам, який вхід був отриманий у попередній період часу. Операційна таблиця для моноїда служить таблицею для визначення функції переходу для машини. Заголовки рядків - це значення стану, а заголовки стовпців - це вхідні дані. Якби ми намалювали схему переходу з усіма можливими входами, діаграма була б занадто важкою для читання. Так як$U$ генерується двома елементами,$T_0$ і$T_1\text{,}$ ми будемо включати тільки ті входи. Припустимо, що ми хотіли прочитати функцію переходу для входу$T_{01}\text{.}$ Так як$T_{01}=T_0T_1\text{,}$ в будь-якому стані$s, t\left(s, T_{01}\right) = t\left(t\left(s, T_0\right), T_1\right).$ діаграма переходу з'являється на рис$\PageIndex{3}$.

$clipboard_e16231856685687ab526113b5e78ce41e.png$ Малюнок $\PageIndex{3}$: Скопіюйте та вставте підпис тут. (Авторське право; автор через джерело)

Якщо ми почнемо читати рядок 0 і 1 в той час як в стані$T_{\lambda }$ і перебуваємо в стані в$T_{ab}$ будь-який час, вхід з попереднього періоду часу (не вхід, який послав нас в$T_{ab}\text{,}$ той перед цим)$a\text{.}$ в станах$T_{\lambda }, T_0$ і$T_1\text{,}$ не існує попередніх вхідних даних.

14.5.1: Вправи

Вправа$\PageIndex{1}$

Намалюйте схеми переходів для машин наступних моноїдів:

$\displaystyle \left[\mathbb{Z}_4;+_4\right]$
Прямий продукт$\left[\mathbb{Z}_2;\times _2\right]$ з собою.

Відповідь: $clipboard_efac3272bb2625461e4f5a90e1b503441.png$ Малюнок$\PageIndex{4}$: (a)

$clipboard_e6777df5d4d0f344d5553f8f8a674111c.png$ Малюнок$\PageIndex{5}$: (b)

Вправа$\PageIndex{2}$

Незважаючи на те, що моноїд може бути нескінченним, ми можемо візуалізувати його як нескінченну станову машину за умови, що він генерується кінцевою кількістю елементів. Наприклад, моноїд$B^*$ генерується 0 і 1. Розділ його перехідної діаграми можна отримати, дозволивши введення тільки з генеруючої установки. Моноїд цілих чисел, що додаються, генерується$\{-1, 1\}\text{.}$ множиною Діаграму переходу для цього моноїда можна візуалізувати, намалювавши невелику його частину, як на малюнку$\PageIndex{6}$. Те ж саме справедливо і для адитивного моноїда цілих чисел, як показано на малюнку$\PageIndex{7}$.

$clipboard_e5e73a9006a935f62c7d27f55bfb9dd49.png$ Малюнок$\PageIndex{6}$: Нескінченна машина$B^*$

$clipboard_e4229df79efe29293f745684b410ab873.png$ Малюнок$\PageIndex{7}$: Нескінченна машина$[\mathbb{Z};+]$

Намалюйте схему переходу для$\{a, b, c\}$
Намалюйте схему переходу для$[\mathbb{Z}\times \mathbb{Z};\textrm{componentwise addition}]\text{.}$
Намалюйте схему переходу для$[\mathbb{Z};+]$ генераторної установки$\{5,-2\}\text{.}$