Визначення та властивості скінченого автомату

Скінченний автомат служить математичною моделлю реальних дискретних перетворювачів інформації.

Визначення 2. Скінченним автоматом A називається система , де – вхідний алфавіт; – вихідний алфавіт; – алфавіт станів; f(s,x) – функція переходів, що є відображенням множини XS в алфавіт S і визначає вибір наступного стану; g(x s) – функція виходів, що є відображенням множини XS в алфавіт Y і визначає вихідний символ; – початковий стан керуючого пристрою,  S ; F – множина завершальних станів, F  S.

Функція переходів має вигляд , де t=1,2,… – номер такту (кроку, дискретного моменту часу).

Множина Y і функція виходів g можуть бути відсутніми, якщо не передбачено видачі вихідної інформації. Маємо автомат без виходу. У ньому голівка тільки читаюча (без друку – не створює вихідного слова).

Якщо автомат містить множину Y і функцію g виходів, то маємо автомат з виходом. У ньому голівка читаюча і пишуча (з друком – створює вихідне слово).

Для опису функцій f і g аналітичний спосіб, як правило, не застосовується. Звичайно використовується табличне чи графічне подання.

Оскільки функції f і g визначені на скінченних множинах, то їх можна задавати таблицями з двома входами, де на перетині стовпця s і рядка x стоїть значення функції f( s,x) і g( s,x) відповідно. Функція f задається таблицею переходів, а функція g – таблицею виходів. Звичайно ці таблиці суміщають в одну, що називається таблицею автомату (автоматною таблицею). В автоматній таблиці на перетині стовпця s і рядка x стоїть пара наступний стан, вихідний символ.

Крім того, скінченний автомат можна задати орієнтованим графом (точніше псевдографом, оскільки можливі кратні дуги і петлі), що називається діаграмою (графом) автомату. Вершини відповідають станам, а дуги – переходам з одного стану в інший. Кожна дуга позначена відповідною парою вхідний символ, вихідний символ.

Для довільної діаграми автомату в кожній вершині справджуються наступні умови коректності:

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

2) Будь-яка вхідна літера зустрічається тільки на одній дузі, що виходить із (умова детермінованості).

Автомат A називається частковим (не повністю визначеним), якщо хоча б одна з двох його функцій f і g не повністю визначена, тобто для деяких пар x s, значення функцій f або g не визначені. У таблиці автомату його не повна визначеність проявляється в тому, що деякі її комірки незаповнені (порожні).

Частковий автомат застосовується, коли деякі пари x s, не можуть виникнути в реальних умовах функціонування. Для виконання різних перетворень частковий автомат довизначають, виходячи з міркувань зручності.

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

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

<== попередня сторінка	\|	наступна сторінка ==>
Скінченний автомат, як модель перетворювача дискретної інформації	\|	Автомат Мілі

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.