1. Поняття кінцевого автомата

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

По вхідному каналу кожен момент часуt=1, 2, . пристрійМнадходять вхідні сигнали (з деякого кінцевого безлічі сигналів). Задається закон зміни стану до наступного моменту часу в залежності від вхідного сигналу та стану пристрою у поточний момент часу. Вихідний сигнал залежить від стану та вхідного сигналу у поточний момент часу (рис. 1).

Кінцевий автомат є математичною моделлю реальних дискретних пристроїв із переробки інформації.

безлічX=a1, .am> називаєтьсявхідним алфавітом, а його елементи -вхідними сигналами, їх послідовності - вхідними словами;

безлічY=b1, .bp> називаєтьсявихідним алфавітом, його елементи -вихідними сигналами, їх послідовності -вихідними словами>;

З кінцевим автоматом асоціюється уявний пристрій, який працює в такий спосіб. Воно може перебувати в стані з множиниQ, сприймати сигнали з множиниXі видавати сигнали з множиниY.

2. Способи завдання кінцевогоавтомата

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

---