Автомат вільний

Автома́т ві́льний — автомат можна розглядати як унарну універсальну алгебру A = <A, f₁, …, f_k>. Автомат називається вільним, якщо алгебра A — вільна.

Наприклад, нехай дано дві множини Ω та Χ які не перетинаються. Утворимо множину слів Λ таких, що перша їхня літера — елемент множини Ω а решта (якщо вони є) — елементи множини Χ.

Утворимо тепер із отриманої множини слів Λ автомат ${\mathfrak {A}}(\Omega ,\mathrm {X} )$ таким чином: кожне слово із Λ назвемо станом автомату ${\mathfrak {A}}(\Omega ,\mathrm {X} )$, кожний елемент x ∈ Χ назвемо входом автомату ${\mathfrak {A}}(\Omega ,\mathrm {X} )$, та, згідно із визначенням, будемо вважати, що стан q ∈ Λ під дією входу x переходить в стан qx де qx — слово із Λ, отримане приписуванням справа до слова q літери x. Отриманий автомат буде вільним автоматом (з множиною вільноутворюючих станів Ω і вільноутворючих входів Χ).

Вірне твердження: будь-який інший автомат (з множиною творючих станів Ω і творючих входів Χ) є гомоморфним образом вільного автомату.

Джерела інформації

• Енциклопедія кібернетики, Кратко М. І., т. 1, с. 26.

Див. також

• Способи задання автоматів