Кінцевий автомат: теорія та реалізація. Кінцеві автомати: перетворювачі та розпізнавачі Інші способи опису

Сьогодні ми поговоримо про автомати, але аж ніяк не тих, що тримають у руках солдати російської армії. Йтиметься про такий цікавий стиль програмування мікроконтролерів як автоматне програмування. Точніше це навіть стиль програмування а ціла концепція, завдяки якій програміст мікроконтролерів може значно полегшити своє життя. Завдяки якій багато завдань представлені перед програмістом вирішуються набагато легше і простіше, позбавляючи програміста головного болю. До речі автоматне програмування найчастіше називають SWITCH-технологією.

Хочу зауважити, що стимулом написання цієї посади послужив цикл статей про SWITCH-технологію Володимира Татарчевського. Цикл статей називається «Застосування SWITCH-технології при розробці прикладного програмного забезпеченнядля мікроконтролерів» Так що в цій статті я постараюся здебільшого навести приклад робочого коду та його опис.

До речі я запланував ряд статей присвячених програмуванню, в яких докладно розглядатиму прийоми програмування під мікроконтролери АВР, НЕ пропустіть…. Ну, що ж поїхали!

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

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

А що тут такого? Все нормально - контролер, який у надрах вашого плеєра просто закінчив виконання своєї програми. Ось бачите незручно якось виходить.

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

Стилі програмування.

«Стилі програмування» — звучить якось незрозуміло, та гаразд. Що я хочу цим сказати? Уявимо, що людина ніколи раніше не займалася програмуванням, тобто взагалі повний чайник.

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

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

Спочатку я не замислювався про якісь конструктивні особливості програми. Я просто формував логіку програми – креслив блок-схему та писав код. Від чого постійно натикався на граблі. Але це був перший час коли я не парився і використовував стиль «просте зациклювання», потім став застосовувати переривання, далі автомати і пішло поїхало.

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

Void main(void) ( initial_AL(); //ініціалізація периферії while(1) ( Leds_BLINK(); //функція світлодіодної мигалки signal_on(); //функція включення сигналу signal_off(); //функція вимикання сигналу l=button( );// змінна відповідальна за натискання кнопок switch(l) // Залежно від величини змінної виконується та чи інша дія (case 1: (Deistvie1(); // Замість функції може бути умовний оператор Deistvie2(); //або ще кілька гілок switch case Deistvie3(); Deistvie4(); Deistvie5(); );case 2: ( Deistvie6(); Deistvie7(); Deistvie8(); Deistvie9(); Deistvie10(); ); . ) ) ) )

Робоча точка програми рухається по порядку. При цьому послідовно виконуються всі дії, умови та цикли. Код починає гальмувати, доводиться вставляти багато зайвих умов, ускладнюючи цим сприйняття.

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

З таким підходом я написав кілька програм, вони були не великі і цілком робочі, але наочність залишала бажати кращого. Щоб додати якусь нову умову, доводилося перелопачувати весь код, бо все було зав'язано. Це породжувало багато помилок та головного болю. Компілятор лаявся як тільки міг, налагодження такої програми перетворювалося на пекло.

2. Цикл + переривання.

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

Допустимо на переривання можна повісити обробку кнопок або відстеження важливої події. В результаті програма стає наочнішою але не менш заплутаною.

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

3. Автоматне програмування.

Ось ми і підбираємось до головної теми цієї статті. Програмування в кінцевих автоматах позбавляє програму недоліків властивих першим двом прикладам. Програма стає простішою, її легко модифікувати.

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

У грубому поданні це як вимикач освітлення. Є два стани включено та вимкнено, і дві умови включити та вимкнути. Ну а про все по порядку.

Реалізація багатозадачності у switch-технології.

Мікроконтролер здатний керувати навантаженням, моргати світлодіодами, відстежувати натискання клавіш та багато іншого. Але як це робити одночасно? Для вирішення цього питання існує багато рішень. Найпростіший із них я вже згадував це використання переривань.

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

Інший спосіб реалізації багатозадачності це використання операційних систем. Так справді стали вже з'являтися маленькі ОСьки, які можна застосувати на малопотужному контролері. Але найчастіше цей спосіб виходить дещо надлишковим. Адже навіщо витрачати ресурси контролера зайвою роботою, коли цілком можна обійтися малою кров'ю.

У програмах написаних за switch — технологією подібна «ілюзія» багатозадачності виходить завдяки системі обміну повідомлень. Я написав «ілюзія», тому що так і є насправді, адже програма фізично не може одночасно виконувати різні ділянки коду. Про систему обміну повідомленнями я розповім трохи далі.

Система обміну повідомленнями

Розрулити численні процеси та створити ілюзію багатозадачності можна за допомогою системи обміну повідомленнями.

Допустимо нам потрібна програма, в якій йде перемикання світлодіода. Ось у нас є два автомати, назвемо їх LEDON - автомат відповідальний за включення світлодіода і автомат LEDOFF - автомат відповідальний за вимикання світлодіода.

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

При активації одного автомата відбувається запалення світлодіода, при активації іншого гаситься світлодіод. Розглянемо невеликий приклад:

Int main(void) ( INIT_PEREF(); //ініціалізація периферії (світлодіоди) InitGTimers(); //ініціалізація таймерів InitMessages(); //ініціалізація механізму обробки повідомлень InitLEDON(); //ініціалізація автомата LEDON InitLEDOFF(); // ініціалізація автомата LEDOFF SendMessage(MSG_LEDON_ACTIVATE);// активуємо автомат LEDON sei(); // Дозволяємо переривання // Головний цикл програми while(1) ( ProcessLEDON(); // ітерація автомата LEDON ProcessLEDOFF(); (); //обробка повідомлень);

У рядках 3 -7 відбуваються різні ініціалізації, тому нас це зараз не особливо цікавить. А ось далі відбувається таке: перед запуском головного циклу (while(1)), ми надсилаємо повідомлення автомату

SendMessage(MSG_LEDON_ACTIVATE)

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

Невеликий відступ:

Повідомлення має три стани. А саме стан повідомлення може бути неактивним, але неактивним і активним станом.

Виходить, що повідомлення спочатку було неактивним, коли ми надіслали повідомлення, воно отримало стан «встановлене але неактивне». І це дає нам таке. При послідовному виконанні програми автомат LEDON повідомлення не отримує. Відбувається холостий ітерація автомата LEDON при якому повідомлення просто не може бути прийняте. Оскільки повідомлення має стан «встановлено, але неактивно», програма продовжує своє виконання.

Коли всі автомати в холосту протикають, черга доходить до функції ProcessMessages(). Ця функція завжди ставиться в кінці циклу після виконання всіх ітерацій автоматів. Функція ProcessMessages() просто переводить повідомлення зі стану «встановлено але неактивно» в стан «активно».

Коли нескінченний цикл виконує друге коло, картина стає зовсім інша. Ітерація автомата ProcessLEDON вже не буде неодруженою. Автомат зможе прийняти повідомлення, перейде у запалений стан і також відправить повідомлення. Воно буде адресовано автомату LEDOFF та життєвий циклповідомлення повториться.

Хочу зауважити, що повідомлення, які мають стан «активно», при зустрічі з функцією ProcessMessages знищуються. Тому повідомлення може бути прийняте лише одним автоматом. Є ще один тип повідомлень — це широкомовні повідомлення, але я їх розглядати не буду, у статтях Татарчевського вони також добре висвітлені.

Таймери

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

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

Все тому, що ми не продумали грамотне відпрацювання затримок. Адже нам мало поперемінного включення-вимкнення світлодіодів, світлодіод повинен затримуватися в кожному стані, допустимо на секунду.

Алгоритм буде наступним:

Можна натиснути, щоб збільшити

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

1. Входимо у стан у вигляді прийняття повідомлення.

2. Перевіряємо показання таймера/лічильника, якщо торкалося, то виконуємо дію, інакше просто надсилаємо повідомлення самому собі.

3. Надсилаємо повідомлення наступному автомату.

4. Вихід

У наступному вході все повторюється.

Програма з SWITCH-технології. Три кроки.

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

Програму я складатиму мовою СІ, але це зовсім не означати, що в кінцевих автоматах потрібно писати тільки на Сі, цілком можна використовувати будь-яку іншу мову програмування.

Програма буде у нас модульною і тому буде розбита на кілька файлів. Модулі у нас будуть наступні:

Модуль основного циклу програми містить файли leds_blink.c, HAL.c, HAL.h
Модуль таймерів містить файли timers.c, timers.h
Модуль обробки повідомлень містить файли messages.c, messages.h
Модуль автомата 1 містить файли ledon.c, ledon.h
Модуль автомата 2 містить файли ledoff.c, ledoff .h

Крок 1.

Створюємо проект і одразу підключаємо до нього файли наших статичних модулів: timers.c, timers.h, messages.c, messages.h.

Файл leds_blink.c модуля основного циклу програми.

#include "hal.h" #include "messages.h" //модуль обробки повідомлень #include "timers.h" //модуль таймерів //Перерив по таймеру //############## ################################################## ############################# ISR(TIMER0_OVF_vect) // перехід по вектору переривання (переповнення таймера лічильника T0) (ProcessTimers(); //Обробник переривань від таймера) //######################################## ################################################## int main(void) ( INIT_PEREF(); //ініціалізація переферії (світлодіоди) InitGTimers(); //ініціалізація таймерів InitMessages(); //ініціалізація механізму обробки повідомлень InitLEDON(); //ініціалізація автомата LEDON InitLEDOFF(); StartGTimer( TIMER_SEK); // Запуск таймера SendMessage (MSG_LEDON_ACTIVATE); // активуємо автомат FSM1 sei (); // Дозволяємо переривання // Головний цикл програми while (1) ( ProcessLEDON (); ); // обробка повідомлень );

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

З рядка int main (void) по суті починається основна програма. І починається вона з ініціалізації всього та вся. Тут ініціалізуємо периферію, тобто задаємо початкові значення портам введення виведення компаратору та решті вмісту контролера. Все це робить функція INIT_PEREF, тут її запускаємо, хоча її основне тіло знаходиться у файлі hal.c.

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

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

StartGTimer(TIMER_SEK); // Запуск таймера SendMessage (MSG_LEDON_ACTIVATE); //активуємо автомат FSM1

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

Hal.h – це заголовний файл модуля основного циклу програми.

#ifndef HAL_h #define HAL_h #include #include //Стандартна бібліотека включає переривання #define LED1 0 #define LED2 1 #define LED3 2 #define LED4 3 #define Komparator ACSR //компаратор #define ViklKomparator 1<

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

А ось файл Hal.c - це вже виконуваний файл, і як я вже згадував, в ньому міститься різна ініціалізація периферії.

#include "hal.h" void INIT_PEREF(void) ( //Ініціалізація портів введення-виводу //############################ ################################################## ##### Komparator = ViklKomparator;// ініціалізація компаратора - вимкнення DDRD = 1<

Ну що модуль основного циклу програми я показав тепер нам залишилося зробити останній крок, нам потрібно написати модулі самих автоматів.

Крок 3

Нам залишилося написати модулі кінцевих автоматів, у нашому випадку автомата LEDON та автомата LEDOFF. Для початку наведу текст програми автомата, що запалює світлодіод файл ledon.c.

//файл ledon.c #include "ledon.h" #include "timers.h" #include "messages.h" unsigned char ledon_state; //змінна стану void InitLEDON(void) ( ledon_state=0; //тут можна виконати ініціалізацію інших //змінних автомата за їх наявності ) void ProcessLEDON(void) ( switch(ledon_state) ( case 0: //неактивний стан if(GetMessage) (MSG_LEDON_ACTIVATE)) //якщо повідомлення є то воно буде прийнято ( //і піде перевірка таймера if(GetGTimer(TIMER_SEK)==one_sek) //якщо таймер засік 1сек то виконуємо ( StopGTimer(TIMER_SEK); PORTD = 1<

Тут у перших рядках як завжди підключаються бібліотеки та оголошуються змінні. Далі в нас вже пішли функції, з якими ми вже зустрічалися. Це функція ініціалізації автомата InitLEDON та функція вже самого обробника автомата ProcessLEDON.

У тілі обробника вже відбувається відпрацювання функцій із таймерного модуля та модуля повідомлень. А сама логіка автомата виконана з урахуванням конструкції switch-case. І тут можна помітити, що обробник автомата можна також ускладнити додавши кілька перемикачів case.

Заголовковий файл для автомата буде ще простіше:

//файл fsm1 #ifndef LEDON_h #define LEDON_h #include "hal.h" void InitLEDON(void); void ProcessLEDON(void); #endif

Тут підключаємо сполучний файл hal.h і вказуємо прототипи функцій.

Файл відповідальний за вимкнення світлодіода виглядатиме практично також тільки в дзеркальному відображенні, так що тут я його виводити не буду - небажання 🙂

Всі файли проекту ви можете завантажити за цим посиланням ====>>> ПОСИЛАННЯ.

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

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

Ну тепер у мене справді все, тому я бажаю вам удачі, прекрасного настрою та до нових зустрічей.

З н/п Володимир Васильєв

алфавіту: при i = 1, ..., n. Число букв у цій послідовності називається довжиноюслова та позначається | w | . Є одне спеціальне "порожнє" слово довжини 0. Позначатимемо його через На словах визначено операцію приписування одного слова після іншого, звана конкатенацією: якщо слово w = w 1 ... w n , а слово v = v 1 ... v m , то їх конкатенація - це слово w 1 ... w n v 1 ... v m довжини n + m. Зазвичай знак конкатенації опускатимемо і писатимемо просто w v (за аналогією зі знаком множення в алгебрі). Порожнє слово - це єдине слово таке, що для будь-якого слова w справедлива рівність. Операція конкатенації асоціативна: для будь-яких трьох слів w, v і u очевидно, має місце рівність: (w v)u = w(v u) . Тому дужки під час запису конкатенації кількох слів опускатимемо. Для представлення кількох конкатенацій одного й того ж слова використовують скорочену "статечну форму" запису: . Наприклад, a 3 b 4 c 2 - це скорочений запис слова aaabbbbcc.

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

Кінцеві автомати часто використовуються визначення тих чи інших властивостей слів , тобто . для розпізнавання мов: автомат, який розпізнає деяку мову L повинен за довільним словом w відповісти питання " ? ". Для вирішення такого завдання функція виходів може бути замінена на перевірку того, який стан переходить автомат після отримання вхідного слова w - "приймає" або "відкидає".

Визначення 4.3. Детермінований кінцевий автомат (ДКА) - розпізнавач - це система виду

що включає такі компоненти:

Функцію називають програмоюавтомата A і задають як список з m n командвиду .

Зручно також задавати функцію за допомогою описаної вище таблиці розміру n x m, рядки якої відповідають станам з Q, а стовпці - символам з вхідного алфавітуі в якій на перетині рядка q i і стовпця a j стоїть стан.

Як і автомати-перетворювачі, автомати-розпізнавальні можна представляти з допомогою розмічених орієнтованих графів, званих діаграмами .

Визначення 4.4. Діаграма ДКА- це орієнтований (мульти)граф D A = (Q, E) з поміченими ребрами, в якому виділена вершина- початковий стан q 0 з кожної вершини виходить ребер, позначених символами так, що для кожної та кожного символу є єдине ребро з q у вершину з міткою a.

Скажімо, що представлений послідовністю ребер шлях p = e 1 e 2 ... e t в діаграмі несе слово w = w 1 w 2 ... w t, якщо wi - це мітка ребра e i (1> = i> = t). Якщо q - початкова вершина (стан) цього шляху, а q" - його заключна вершина, то говоритимемо, що слово w перекладає q в q".

Робота кінцевого автомата-розпізнавателяполягає у читанні вхідного слова та зміні станів залежно від його символів.

Визначення 4.5. Назвемо конфігурацією ДКАдовільну пару виду (q, w) , в якій і .

На безлічі конфігурацій введемо відношення переходу за один крок:

Якщо, то покладемо кожному за: .

Через позначимо рефлексивне та транзитивне замикання .

Змістовно, означає, що автомат A , почавши роботу в стані q на слові w = w 1 ... w l через деяке кінцеве число кроків 0<= k <= l прочтет первые k символов слова w и перейдет в состояние q" , а w" =w k+1 ... w l - это непрочтенный остаток слова w .

Визначення 4.6. ДКА A розпізнає (допускає, приймає) слово w якщо для деякого

Тобто. після обробки слова w автомат переходить у стан, що приймає.

Мова L A , розпізнається (допускається, приймається) автоматично A складається з усіх слів, що розпізнаються цим автоматом.

У статті розглянуті прості кінцеві автомати та їх реалізація на C++ за допомогою switch-конструкцій, таблиць виконання та бібліотеки Boost Statechart.

Вступ

Грубо кажучи, кінцевий автомат (Finite State Machine), очима користувача – це чорна скринька, в яку можна щось передати і щось звідти отримати. Це дуже зручна абстракція, яка дозволяє приховати складний алгоритм, крім того, кінцеві автомати дуже ефективні.

Кінцеві автомати зображують як діаграм складаються з станів і переходів. Поясню на простому прикладі:

Як ви, напевно, здогадалися – це діаграма станів лампочки. Початковий стан позначається чорним кружком, переходи стрілками, деякі стрілки підписані – це події після яких автомат перетворюється на інший стан. Отже, відразу з початкового стану ми потрапляємо в стан Light Off– лампа не горить. Якщо натиснути кнопку, то автомат змінить свій стан і перейде за поміченою стрілкою Push Buttonу стан Light On– лампа горить. Перейти з цього стану можна знову ж таки за стрілкою, після натискання кнопки, в стан Light Off.

Також широко використовуються таблиці переходів:

Практичне застосування автоматів

Кінцеві автомати широко використовуються у програмуванні. Наприклад, дуже зручно уявити роботу пристрою у вигляді автомата. Це зробить код простішим і дозволить легко з ним експериментувати та підтримувати.

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

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

Розглянемо діаграму:

З початкового стану ми потрапляємо у стан Start. Перевіряємо поточний символ, і якщо він є буквою, переходимо в стан Wordза стрілкою поміченою як Letter. Цей стан передбачає, що ми розглядаємо слово, аналіз подальших символів, або підтвердить це припущення, або спростує. Отже, розглядаємо наступний символ, якщо він є буквою, стан не змінюється (зверніть увагу на кругову стрілку позначену як Letter). Якщо символ не є буквою, а відповідає пробельному символу, то це означає, що припущення було вірним і ми виявили слово (робимо перехід за стрілкою) Spaceу стан Start). Якщо символ не є, ні буквою, ні пробілом, значить ми помилилися в припущенні і послідовність, яку ми розглядаємо, не є словом (переходимо за стрілкою Unknownу стан Skip).

В стані Skipми знаходимося доти, доки не зустрінеться пробельний символ. Після того як пробіл був виявлений ми переходимо за стрілкою Spaceу стан Start. Це потрібно, щоб повністю пропустити рядок, що не відповідає нашому шаблону пошуку.

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

Автомат із використанням switch-інструкцій

Перше – можливі стани:

Після цього ми ітеруємо по рядку підсовуючи автомату поточний знак. Сам автомат є інструкцією switch спочатку виконує перехід у секцію поточного стану. Усередині секції є конструкція if-else, яка в залежності від події (символу, що прийшов) змінює поточний стан:

const size_t length = text.length(); for (size_t i = 0 ; i ! = length; ++ i) ( const char current = text [i] ; switch (state) ( case State_Start: if (std:: isdigit (current) ) ( state = State_Number; ) else if (std:: isalpha (current) ) ( state = State_Word; ) break ; case State_Number: if (std:: isspace (current) ) (

Тут дивимося на діаграму – поточний стан Номер, подія Space(зустрічений пробельний символ), а значить знайдено число:

FoundNumber(); state = State_Start; ) else if (! std:: isdigit (current)) (state = State_Skip;) break; case State_Word: if (std:: isspace (current) ) ( FoundWord() ; state = State_Start; ) else if (! std:: isalpha (current) ) ( state = State_Skip; ) break ; case State_Skip: if (std:: isspace (current) ) ( state = State_Start; ) break ; )

Підсумок:

Висока ефективність

Простота реалізації для простих алгоритмів

— Важко підтримувати

Інтерпретація часу виконання

Ідея даного підходу проста - треба створити таблицю переходів, заповнити її, і потім, при настанні події, знайди в таблиці такий стан і зробити перехід:

enum Events (Event_Space, Event_Digit, Event_Letter, Event_Unknown); void ProcessEvent(Events event); ... struct Transition ( States BaseState_; Events Event_; States TargetState_; ) ; void AddTransition(States fromState, Events event, States toState) ; ... typedef std:: vector< transition>TransitionTable; TransitionTable Transitions_; States CurrentState_;

Заповнення таблиці:

AddTransition(State_Start, Event_Digit, State_Number); AddTransition(State_Start, Event_Letter, State_Word); AddTransition(State_Number, Event_Space, State_Start) ; AddTransition(State_Number, Event_Letter, State_Skip); AddTransition(State_Number, Event_Unknown, State_Skip); AddTransition(State_Word, Event_Space, State_Start) ; AddTransition(State_Word, Event_Digit, State_Skip); AddTransition(State_Word, Event_Unknown, State_Skip); AddTransition(State_Skip, Event_Space, State_Start) ;

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

Щоб автомат, при настанні деяких подій, міг сповістити певний код, можна додати до структури з інформацією про перехід ( Transition) покажчик на функцію ( Action), яка буде викликатися:

typedef void (DynamicMachine:: * Action) () ; struct Transition ( States BaseState_; Events Event_; States TargetState_; Action Action_; ) ; ... void AddTransition(States fromState, Events event, States toState, Action action) ; ... AddTransition (State_Number, Event_Space, State_Start, & DynamicMachine:: FoundNumber ) ;

Підсумок:

Гнучкість та наочність

Простіше підтримувати

— Найменша продуктивність порівняно із switch-блоками

Інтерпретація часу виконання. Оптимізація за швидкістю

Чи можна поєднати наочність зі швидкістю? Зробити автомат настільки ефективним, як автомат на switch-блоках навряд чи вдасться, але скоротити розрив можна. Для цього треба з таблиці, побудувати матрицю, таку, щоб для отримання інформації про перехід не виконувати пошук, а зробити вибірку за номером стану та події:

Досягається результату, за рахунок витрати пам'яті.

Підсумок:

Гнучкість, наочність

Ефективний

- Витрата пам'яті (швидше за все несуттєво)

Boost Statechart

Ми обговорили кілька способів самостійної реалізації кінцевого автомата. Для різноманітності пропоную розглянути бібліотеку для побудови автоматів із Boost. Ця бібліотека дуже потужна, пропоновані можливості дозволяють побудувати складні кінцеві автомати. Ми ж розглянемо її досить швидко.

Отже, спочатку визначимо події:

namespace Events ( struct Digit : boost:: statechart :: event< Digit>( ); struct Letter : boost:: statechart :: event< Letter>( ); struct Space : boost:: statechart :: event< Space>( ); struct Unknown : boost:: statechart :: event< Unknown> { } ; }

Саму машину (зверніть увагу, що другий параметр шаблону – початковий стан):

struct Machine : boost:: statechart :: state_machine< Machine, States:: Start > { } ;

І власне самі статки. Усередині станів потрібно визначити тип описує переходи ( reactions), і якщо переходів кілька, то перерахувати в списку типів boost::mpl::list . Другий параметр шаблону simple_state- Тип описує машину. Переходи описуються параметрами шаблону transition, парою Подія — Наступний стан:

namespace States ( struct Start : boost:: statechart :: simple_state< Start, Machine> < boost:: statechart :: transition < Events:: Digit , States:: Number >< Events:: Letter , States:: Word >> reactions; ); struct Number : boost:: statechart :: simple_state< Number, Machine>( typedef boost:: mpl :: list< boost:: statechart :: transition < Events:: Space , States:: Start >, boost:: statechart :: transition< Events:: Letter , States:: Skip >, boost:: statechart :: transition< Events:: Unknown , States:: Skip >> reactions; ); struct Word : boost:: statechart :: simple_state< Word, Machine>( typedef boost:: mpl :: list< boost:: statechart :: transition < Events:: Space , States:: Start >, boost:: statechart :: transition< Events:: Digit , States:: Skip >, boost:: statechart :: transition< Events:: Unknown , States:: Skip >> reactions; ); struct Skip : boost:: statechart :: simple_state< Skip, Machine>( typedef boost:: statechart :: transition< Events:: Space , States:: Start >reactions; ); )

Машина побудована, залишилося лише ініціалізувати її і можна використати:

Machine machine; machine.initiate(); ... machine . process_event (Events:: Space () ) ;

Підсумок:

Гнучкість, розширюваність

- Ефективність

Швидкодія

Я написав тестову програму для перевірки швидкодії збудованих автоматів. Через автомати я прогнав текст розміром ~17 Мб. Ось результати прогону:

Loading text Text length: 17605548 bytes 0.19 s Running BoostMachine Words: 998002, numbers: 6816 0.73 s Running DynamicMachine Words: 998002, numbers: 6816 0.56 s 6816 0.29 s Running SimpleMachine Words: 998002, numbers: 6816 0.20 s

Що залишилося не розглянутим

Неохопленими залишилися ще кілька реалізацій кінцевих автоматів (рекомендую http://www.rsdn.ru/article/alg/Static_Finite_State_Machine.xml і http://www.rsdn.ru/article/alg/FiniteStateMachine.xml), генератори, що будують автомати з описів, бібліотека Meta State Machine із Boost версії 1.44.0, а також формальні описи кінцевих автоматів. З усім перерахованим цікавий читач може ознайомитись самостійно.

Теорія кінцевих автоматів

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

· Кінцевий автомат може вирішувати низку легких завдань компіляції. Лексичний блок майже завжди будується на основі кінцевого автомата.

· робота кінцевого автомата відрізняється високою швидкодією.

моделювання кінцевого автомата вимагає фіксованого обсягу пам'яті, що полегшує управління пам'яттю.

· Існує ряд теорем та алгоритмів, що дозволяють конструювати та спрощувати кінцеві автомати.

У літературі є кілька відмінних визначень кінцевого автомата. Однак, загальним у них є те, що кінцевий автомат моделює обчислювальний пристрій з фіксованим об'ємом пам'яті, який читає послідовності вхідних символів, що належать до деякої вхідної множини. Принципові відмінності у термінах пов'язані з тим, що автомат робить на виході. Виходом автомата може бути вказівка на те «допустима» чи ні цей вхідний ланцюжок. «Допустимою» називається правильно побудований або синтаксично правильний ланцюжок. Наприклад, ланцюжок, який повинен зображати числову константу, вважається побудованим неправильно, якщо він містить дві десяткові точки.

Визначення:Кінцевий автомат - це формальна система, яка задається за допомогою наступних об'єктів:

· Кінцевим безліччю вхідних символів;

· Кінцевим безліччю станів;

· функцією переходів, яка кожній парі (поточний стан, вхідний символ) ставить у відповідність новий стан;

· Початковим станом;

· Підмножиною станів, виділених як допускаючі або заключні.

приклад. Розберемо роботу контролера, що перевіряє парно чи непарно число одиниць у довільному ланцюжку, що складається з нулів та одиниць. Припустимо, що відповідний кінцевий автомат повинен «припускати» всі ланцюжки, що містять непарне число одиниць і «відкидати» ланцюжки з парним їх числом. Назвемо цей автомат "контролером парності". Вважаємо, що символи, відмінні від 0 та 1, не можна подавати на вхід автомата. Отже, вхідний алфавіт контролера є безліч (0, 1). Вважаємо, що в конкретний момент часу кінцевий автомат має справу лише з одним вхідним символом, а інформацію про попередні символи вхідного ланцюжка зберігає за допомогою кінцевої кількості станів. Як безліч станів будемо розглядати безліч (пар, непар), один з цих станів повинен бути обраний як початковий. Нехай їм буде стан (пар), оскільки на першому етапі число прочитаних одиниць дорівнює нулю, а нуль є парне число. При читанні чергового вхідного символу стан автомата або змінюється, або зберігається тим самим, новий його стан залежить від вхідного символу і поточного стану. Така зміна стану називається переходом.

Робота автомата може описуватися математично функцією переходів виду d(Sтек., x) = Sнов. Інакше це можна записати так:

d (чет., 0) = Чет. d (чет., 1) = непар.

d (непар., 0) = непар. d (непар., 1) = чет.

Контролер має єдиний стан, що допускає, НЕЧЕТ, а ЧЕТ є «відкидає» стан. Відобразимо послідовність переходів автомата при подачі на його вхід ланцюжка 1101.

ЧЕТ ® НЕЧЕТ ® ЧЕТ® ЧЕТ® НЕЧЕТ

Таблиця переходів такого автомата має вигляд:


честь	честь	непар
непар	непар	честь

Визначення.Кінцевий автомат – це формальна система

S = (A, Q, d, l, V),

об'єкти якої наступні:

* A - кінцева множина вхідних символів (множина

терміналів);

* Q - кінцева множина внутрішніх станів автомата

(Більшість нетерміналів);

* V - кінцева множина вихідних символів (вихідний алфавіт);

* d - функція переходів, для якої характерно A ' Q ® Q;

* l – функція виходів, що визначає відображення виду.

Елементи теорії автоматів

План:

1. Поняття автомата, принцип роботи автомата

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

3. Загальні завдання теорії автоматів

Теоретичні відомості

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

Поняття автомата, принцип роботи автомата

Концепція автоматрозглядається у двох аспектах:

1. Автомат – пристрійвиконує деякі функції без безпосередньої участі людини. Автомат це реальний пристрій, зрозумілий, чому і як він працює, хоча б для тих людей, які його сконструювали та виготовили. Автомобіль, трактор, літак, світлофор, телевізор, телефон – це автомати. У цьому вся аспекті ЕОМ слід розуміти як автомат, який працює за програмою, складеною людиною.

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

Будь-який автомат повинен мати деяку кількість входів, деяку кількість виходів та деяку кількість внутрішніх станів.

Алгебраїчна теорія автоматів є розділом теоретичної кібернетики, який вивчає дискретні автомати з абстрактної точки зору алгебри.

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

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

Предметом вивчення структурноїтеорії автоматів є структура автомата, а також структура вхідних та вихідних сигналів, наприклад, способи кодування вхідних та вихідних сигналів та ін.

Визначення кінцевих автоматів

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

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

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

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

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

Вкажемо кілька цікавих історичних фактів, пов'язаних із автоматами, як механічними пристроями.

1. Німецький філософ і алхімік Альберт Великий з 1216 по 1246, створював «залізного» слугу - автомат, який виконував у будинку обов'язки воротаря.

2. Астроном Йоганн Мюллер (Регіамонтан) (1436-1476) створив механічного орла, який вітав нахилом голови та рухом крил в'їзд до Нюрнберга імператора священної Римської імперії Максиміліана II.

3. Механік Жак де Вакансон (1709-1782) – автор першого у світі автоматичного ткацького верстата. Він створив образ механічної качки, точної копії свого живого двійника – плавало, чистило пір'я, ковтало з долоні зерна. Його механічний флейтист, який виконував одинадцять музичних п'єс, вражав людей, які жили в ті далекі роки.

4. Російський винахідник 19 ст. А. М. Гамулецький створив цілий механічний кабінет, у якому було багато сконструйованих ним автоматів. Тут у тому числі була і голова чарівника і амур, що грає на арфі, які вражали уяву сучасників.

5. Перший примітивний арифмометр сконструював 1641 р. Блез Паскаль. Поштовхом для відкриття були муки його батька – податкового, інспектора, який днями та ночами працював із великими обчисленнями. Винайшовши арифмометр, вісімнадцятирічний син позбавив батька від складних обчислень, а світу подарував перший калькулятор, який робить додавання та віднімання чисел.

6. Перший шаховий автомат був побудований 1890 р. іспанським інженером Торресом Кеведо. Такий автомат міг розіграти лише ладейний ендшпіль (король і тура проти короля).

7. Першу обчислювальну машину з автоматичним керуванням створив Чарльз Баббедж у 1822 р. Він спроектував арифмометр, який мав запам'ятовуючі та арифметичні пристрої. Ці устрою стали прототипами аналогічних пристроїв сучасним ЕОМ.

Види автоматів.

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

Будь-який автомат має власні базові множини,які включають:алфавіт входу, алфавіт виходу, безліч станів автомата.

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

У роботі кінцевих цифрових автоматів важливим поняттям є час.

Автомати можна класифікувати за різними ознаками.

1. За видом діяльності - автомати поділяються на: інформаційні, керуючі та обчислювальні.

Доінформаційним автоматамналежать різноманітні довідкові таблиці, інформаційні табло на стадіонах, пристрої аварійної сигналізації.

До керуючим автоматамприйнято відносити пристрої керувати деяким процесом, зокрема конкретно: ліфтом, конвеєром, верстатом, шлагбаумом.

До обчислювальним автоматамвідносяться мікрокалькулятори, процесори в ЕОМ та інші пристрої, що виконують обчислення.

Однак, строго кажучи, багато автоматів є настільки складними системами, що вони є одночасно і обчислювальними, і керуючими, і інформаційними автоматами.

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

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

4. Абстрактні автомати -що відображають безліч слів вхідного алфавіту Хвобезліч слів вихідного алфавіту Y.

Абстрактний автомат є:

~ МатематичнаМодель,

~ Алгоритмдії деякого перетворення кодових послідовностей,

~ Законперетворення вхідного алфавіту у вихідний.

5. Синхронні та асинхронні автомати. Залежно від того, одночасно або послідовно приймаються вхідний сигнал та сигнал зміни станів, автомати діляться насинхронні та асинхронні автомати.

У синхронних автоматахтривалість вхідних сигналів та час переходів узгоджено між собою. Вони використовують у обчислювальних комплексах, АСУ тощо.

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

6. Автомати діляться на кінцеві та нескінченні автомати.Якщо в основі класифікації лежить обсяг пам'яті,та відмінність полягає в тому, чи має автомат кінцевеабо нескінченнекількість внутрішніх станів.

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

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

У детермінованих автоматахповедінка і структура в кожний момент часу однозначно визначені поточною вхідною інформацією та станом самого автомата у попередній момент часу.

У імовірнісних автоматах ця залежність пов'язана ще з деяким випадковим вибором.

Ймовірніснийавтомат - це дискретний перетворювач інформації, функціонування якого у кожний час залежить тільки від станів пам'яті і описується статистичними законами.

8. Універсальний автомат.Теоретично автоматів доведено, що з виконання різних перетворень інформації досить побудувати універсальнийавтомат за допомогою програми та відповідного кодування, здатний вирішувати будь-які завдання.

Математична модель цифрового автомата з одним входом задається п'ятьма об'єктами:

X-кінцева множина вхідних символів, вхідний алфавіт:

Х = (x 1 (t), x 2 (t), …, x n (t));

Y-кінцева множина вихідних символів, вихідний алфавіт:

У = (y 1 (t), y 2 (t), …, y n (t));

Q ~кінцева безліч станів автомата:

Q = (q 0 (t), q 1 (t), q 2 (t), …, q n (t)), q 0- початковий стан;

δ(q, х) - функція переходу автомата з одного стану до іншого: ( Qх X)®Q;

λ(q, х) ~ функція виходу автомата: ( Q x Х) ® Y.

Таким чином, кінцевий автомат С = (X, Q,У, δ, λ.) визначається рекурентними співвідношеннями

q(0) = q 0 , q(t + I) = δ (g(t), х(t)), y(t) = λ (g(t), х(t)),

t-дискретизований момент часів або це є образ монотонної функції t:. Т® N, причому Т -звичайний безперервний час, N - безліч натуральних чисел.

Весь час роботи Трозбивається на кінцеве число інтервалів, межі яких відбувається зміна стану автомата. У цьому t(Г 0) – показує кількість змін, які відбулися на час Г 0 .

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

9. Синхронні автомати діляться на автомати Мілі та автомати Мура. Залежно від способу організації функції виходусинхронні автомати діляться на автомати Мілі (автомати I роду) та автомати Мура (автомати II роду).

В автоматах Мілі- вихідний сигнал y(t) x(t)та станом q(t- 1) автомата в попередній момент часу (t- 1). Математичною моделлю таких автоматів є система рівнянь:

q(t) = δ (q(t-1), х(t)) та y(t) = λ (q(t-1), х(t)),

В автоматах Муравихідний сигнал y(t)однозначно визначається вхідним сигналом x(t)та станом q(t)на даний момент часу t. Математичною моделлю таких автоматів є система:

q(t) = δ (q(t-1), х(t)) та y(t) = λ (q(t)),

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

10. Комбінаційні автомати– є автомати, у яких вихідний знак залежить від стану і визначається лише поточними вхідними символами, тобто. у цьому автоматі всі стани еквівалентні. У такому автоматі вироджено функцію переходу, вона принципово не важлива і в процесі функціонування незмінна. Тому мінімальний комбінаційний автомат має лише один стан.

11 Логічніавтомати - є автомати у яких вхідний алфавіт складається з 2 тдвійкових наборів довжини т,а вихідний - з 2 n двійкових наборів довжини п.Для логічних комбінаційнихавтоматів функція виходу має вигляд системи п логічних функцій від тзмінних.