Автомат (дискретна математика)

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Схема автомата.png

Автомат - схематизований алгоритм.

Процес, у якому переходи виконуються під впливом зовнішніх дій, моделюється за допомогою автомата. Використовуючи автомати, можна моделювати багато машин, включаючи компоненти комп'ютера, також можна дослідити питання розв'язності і складності різних задач.

Основні поняття[ред. | ред. код]

Автомат складається з:

  • вхідна стрічка;
  • керуючий пристрій;
  • допоміжна / робоча пам'ять.

Вхідна стрічка[ред. | ред. код]

Рисунок: Вхідна стрічка та вхідна голівка

Її можна розглядати як лінійну послідовність кліток, або комірок, причому кожна комірка точно містить один вхідний символ з деякого скінченного вхідного алфавіту. За допомогою вхідної стрічки зображується інформація, що поступає на вхід автомата.

Вхідна голівка[ред. | ред. код]

у кожний момент вона читає одну вхідну комірку. За один крок роботи автомата вхідна голівка може зміститися на одну комірку вліво, вправо або залишитися нерухомою. Автомат, що не переміщує свою голівку називається одностороннім.

Пам'ять[ред. | ред. код]

Пам'ять автомата - структура, в якій записуються, зберігаються і зчитуються додаткові дані, що використовуються автоматом при роботі. Для кожного виду автоматів строго визначено тип пам'яті. Автомат може не мати назву, - тип пам'яті часто визначає назву автомата.

Робота автомата складається з послідовності тактів. Кожен такт складається з таких дій:

  1. Читається поточний вхідний символ.
  2. За допомогою функції доступу досліджується пам'ять, і до неї заноситься деяка інформація.
  3. Змінюється стан керуючого пристрою.
  4. Записується вихідна інформація у комірки вхідної стрічки.
  5. Вхідна голівка зміщується на одну комірку вліво, вправо або зберігається у початковому стані.

Поточний вхідний символ та інформація, що витягнута з пам'яті, разом з поточним станом керуючого пристрою визначають, яким повинен бути цей такт. Таким чином, на кожному такті визначається поточна конфігурація автомата, до якої входять:

  • поточний стан керуючого пристрою;
  • поточний зміст вхідної стрічки;
  • поточний зміст робочої пам'яті.

Конфігурація автомата змінюється на кожному такті під впливом керуючого пристрою.


Керуючий пристрій[ред. | ред. код]

Складається зі скінченної множини станів S = {s0...sn} і відображень, які залежно від попередньої конфігурації дозволяють визначити нову конфігурацію автомата, напрямок переміщення вхідної голівки(якщо вона не одностороння), інформацію на друку(якщо в автоматі передбачено функцію друку), інформацією, що заносять у пам'ять і витягують звідти(якщо автомат має робочу пам'ять).


Є два види керуючого пристрою:

  • Недетермінований - для кожної конфігурації існує скінченна множина можливих конфігурацій(більше однієї), так що в будь-яку з них автомат може перейти на наступному кроці.
  • Детермінований - для кожної конфігурації існує не більше однієї можливої наступної конфігурації.

Див. також[ред. | ред. код]

*Розпізнавачі *Машина Тьюрінга *Автомат лінійний
*Скінченні автомати *Лінійно-обмежені автомати *Автомати з магазинною пам'яттю
*Теорія автоматів


Література[ред. | ред. код]

  1. Комп'ютерна дискретна математика/М.Ф.Бондаренко, Н.В.Білоус, А.Г.Руткас. - Х.:Компанія СМІТ, 2004.-385с.