Використання цифрових автоматів у проектуванні навчальних систем

Міністерство  освіти і науки, молоді та спорту України

Кіровоградський державний педагогічний університет  імені Володимира Винниченка 

Кафедра інформатики 
 

Використання  цифрових автоматів  у проектуванні навчальних систем

Курсова робота з прикладної математики 
Шевченка  Ігоря  Віталійовича 
студента 36 групи 
фізико-математичного факультету 
спеціальність 6.040302 Інформатика                      Науковий керівник               Баранюк  О. Ф. 

Кіровоград  - 2011

ЗМІСТ 

ВСТУП 3

РОЗДІЛ  І. ОСНОВНІ ПОНЯТТЯ ТА СИНТЕЗ ЦИФРОВИХ АВТОМАТІВ 5

    1.1 Класифікація Цифрових автоматів 5

         1.1.1Акцептори і розпізнавачі. 5

         1.1.2 Перетворювачі (Трансдруктори) 6

         1.1.3 Детермінованість 7

    1.2 Математична  модель СА 8

    1.3 Синтез  цифрових автоматів 9

         1.3.1 Формалізація завдання 10

         1.3.2 Кодування станів 11

         1.3.3 Синтез комбінаційної схеми 11

 РОЗДІЛ ІІ. РОЗРОБКА ТА СИНТЕЗ ЦА ДЛЯ РЕАЛІЗАЦІЇ ПРОГРАМИ-СИМУЛЯТОРА КЕРУВАННЯ РОБОТОМ 12

     2.1 Постановка задачі та вибір  методів її реалізації 12

     2.2 Синтез ЦА для керування роботом 12

     2.3 Реалізація прграми-симулятора 16

         2.3.1 Вибір методів та засобів  для реалізації програми 16

ВИСНОВКИ 26

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ 27 
 
 
 

ВСТУП

     В наш час цифровий світ став набагато яскравіший та цікавіший ніж це було 15-20 років тому. На сьогодні вже мало хто пам’ятає про термінали, програми на перфокартах, програмування у машинних кодах і т.д. Сучасне програмування вже не потребує від програміста пам’ятати команди процесора, самостійно контролювати процеси від лагодження та компіляції програм. В сучасних мовах програмування високого рівня за невелику кількість маніпуляцій та кілька рядків власно написаного програмного коду можна одержати чудовий прикладний продукт(програму), яка має яскравий, зрозумілий для звичайного користувача інтерфейс. Але це тільки інтерфейс для діалогу користувач-комп’ютер, а сам комп’ютер, як і раніше працює з двійковими даними, а це повертає програміста до вивчення все тієї не двійкової системи числення, команд  процесора, регістрів пам’яті та іншого, що побачити візуально не вдається, а тому сприймається для вивчення набагато гірше, ніж об’єктно-орієнтоване програмування в Delphi, C++ чи C#.

     Метою даної курсової роботи є допомога у вивчені системного програмування  студентами. Надати студентові змогу  наглядно побачити системне програмування  пристроїв, об’єктів, які існують  фізично, але в рамках навчальної програми не можуть використовуватись. Тому студентові надається можливість програмувати та керувати пристроями у так званих програмах-симуляторах. Дані програми дають змогу запрограмувати та керувати пристроєм без його наявності, а у майбутньому, якщо це буде потрібно, використовувати дану програму вже на фізично існуючому пристрої[8].  
 
 

     Для досягнення мети сформульовані такі завдання:

• Розробити цифровий автомат для реалізації програми-симулятора поведінки об’єктів;
• Реалізація програми-симулятора програмними засобами Delphi.

      РОЗДІЛ І. ОСНОВНІ ПОНЯТТЯ ТА СИНТЕЗ ЦИФРОВИХ АВТОМАТІВ

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

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

1. Класифікація цифрових автоматів

Існує дві різних групи автоматів: Акцептори/Розпізнавачі і  Перетворювачі(Трансдуктори).

1.1.1 Акцептори і розпізнавачі

Акцептори і розпізнавачі (також виявлювачі послідовностей) продукують двійковий вихід, кажучи або так або ні на питання прийняті автоматом вхідні дані чи ні. Всі стани СА можуть бути або допустимі або ні. Коли всі вхідні дані оброблені і поточний стан є допустимим, значить вхід прийнятий; інакше відхилений. Як правило на вхід подаються символи (літери); дії не використовуються. Приклад на рис.1 показує СА який приймає слово «nice». В цьому СА єдиний допустимий стан це 7.

Рис.1

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

1.1.2 Перетворювачі  (Трансдуктори)

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

Автомат Мура

СА використовує тільки вхідні дії, тобто, вихід базується  тільки на стані. Перевагою моделі Мура є спрощення поведінки. Уявімо двері підйомника. Автомат розпізнає дві команди: "відчинити" і "зачинити", які викликають зміну стану. Вхідна дія (E:) в стані «Відчиняються» змушує двигун відчиняти двері, вхідна дія в стані «Зачиняються» змушує двигун зачиняти двері. Стани Відчинено і Зачинено зупиняють мотор коли двері повністю відчинені або зачинені. Вони повідомляють зовнішній світ (наприклад, інші автомати) ситуація: «двері відчинені» або «двері зачинені». 

Автомат Мілі

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

На практиці часто використовується суміш моделей. 

Рис.2 СА перетворювач: приклад моделі Мілі

1.1.3 Детермінованість

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

2. Математична модель СА

Згідно із загальною класифікацією, дані наступні визначення:

детермінований  скінченний автомат або детермінований скінченний автомат акцептор є п'ятіркою (Σ,S,s0,δ,F), де:

Σ— вхідна абетка (скінченний, не порожній набір символів).

S — скінченний, не порожній набір станів.

s0 — початковий  стан, елемент з S.

δ — функція  переходу:  (в недетермінованих скінченних автоматах це буде , тобто, δ повертає набір станів).

F набір кінцевих  станів, (можливо порожня) підмножина S.

Для обох детермінованих і недетермінованих СА, зручно дозволити δ бути неповною функцією, тобто δ(q,x) не має бути визначеною для кожної комбінації  and . Якщо СА M знаходиться в стані q, наступний символ x і δ(q,x) не визначена, тоді M може повідомити про помилку (тобто відхілити ввід).

скінченний перетворювач це шістка (Σ,Γ,S,s0,δ,ω), де:

Σ — вхідна абетка (скінченний, не порожній набір символів).

Γ — вихідна  абетка (скінченний, не порожній набір  символів).

S — скінченний, не порожній набір станів.

s0 — початковий  стан, елемент з S (в недетермінованих  скінченних автоматах, s0 це набір початкових станів).

δ — функція  переходу .

ω функція виходу.

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

1.3 Синтез цифрових автоматів

Рис.3 Структурна схема ЦА

Узагальнена структурна схема ЦА показана на рисунку 3. Вихідний код Y,який формується КС, є функцією не лише вхідного коду X, але і коду стану Z, який зберігається в регістрі станів RGZ. Цей регістр і є пам'яттю автомата. Новий стан Zi+1, в який переходить автомат після кожної вхідної дії, тобтоновий вміст RGZ, задається кодом переходу F. Код F, також як і вихідний код Y, є функцією і вхідних сигналів, і стану автомата безпосередньо перед його перехо-дом в новий стан.Задачу синтезу автомата зручно розбити на три частини: формалізація завдання, кодування станів, синтез комбінаційної схеми. Інколи ці частини не зовсім автономні, робота над однією з них може привести до необхідності корекції результатів інших. 

1.3.1 Формалізація  завдання

Процес  формалізації завдання зручно розділити на декілька етапів:

1 етап – формування списку вхідних сигналів X та вихідних Y.

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

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

4 етап  – побудова повного графа автомата. Формальний опис, одержаний на

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

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

1.3.2 Кодування  станів

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

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

1.3.3 Синтез  комбінаційної схеми

Останнім етапом є безпосередньо синтез комбінаційних  схем автомата: одна

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

РОЗДІЛ  ІІ. РОЗРОБКА ТА СИНТЕЗ ЦА ДЛЯ РЕАЛІЗАЦІЇ ПРОГРАМИ-СИМУЛЯТОРА КЕРУВАННЯ РОБОТОМ

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

В якості об’єкта в даній роботі запропонований робот, який пересувається по заданому полю та виконує ряд нескладних команд, які йому надсилає користувач. Керування здійснюється за допомогою програми-клієнта, яка надсилає повідомлення програмі-симулятору робота, яка в свою чергу наглядно демонструє зміну станів робота у результаті реагування на вхідні сигнали[8]. 

2.1 Постановка  задачі та вибір методів її реалізації

Створити  програму-симулятор керування роботом. Для цього розробити схему  ЦА для керування роботом. На вхід даного автомату подаються команди  керування роботом, а на виході ЦА мають бути різні стани в яких перебуває робот у результаті виконання команд.

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

2.2 Синтез  ЦА для керування роботом

1 етап  – формування списку вхідних  сигналів Х та вихідних Y. В нашому випадку вхідними будуть так звані команди керування роботом: зробити один крок вперед, повернути вліво, повернути вправо, завантажити предмет, розвантажити. Формально дані сигнали можна записати так:

Х (вперед, вліво, вправо, завантажити, розвантажити).

Вихідними сигналами нашого ЦА є стани нашого автомата, а саме стани в яких може перебувати робот: дивитися вгору і бути порожнім, дивитися вгору і бути завантаженим, дивитися вниз і бути порожнім, дивитися вниз і бути завантаженим і т.д. Таким чином формально вихідні сигнали можна записати так: Y(вперед_зав., назад_зав., вліво_зав., вправо_зав., вперед_розв., назад_розв., вліво_розв., вправо_розв.)

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

В –  вперед, Л – вліво, П – вправо, З – завантажити, Р – розвантажити, таким чином маємо:  Х(В, Л, П, З, Р); ВЗ – вперед завантажений, НЗ –  назад завантажений, ЛЗ – вліво завантажений, ПЗ – вправо завантажений, аналогічно ВР, НР, ЛР, ПР, таким чином маємо

Y(ВЗ, НЗ, ЛЗ, ПЗ, ВР, НР, ЛР, ПР).

2 етап  – визначення необхідного числа  станів. Наш автомат може перебувати, як і робот у 8-ми різних незалежних станах, а саме: дивитися вгору і бути порожнім, дивитися вгору і бути завантаженим, дивитися вниз і бути порожнім, дивитися вниз і бути завантаженим і т.д. Інших станів бути не може за умовами задачі. Позначимо ці стани Z0, Z1, Z2, Z3, Z4, Z5, Z6, Z7.

3 етап – побудова графа автомата, та таблиці переходів автомата. Вихідні сигнали ВЗ,НЗ, ЛЗ, ПЗ, ВР, НР, ЛР, ПР однозначно пов’язані зі станами автомату Z0, Z1, Z2, Z3, Z4, Z5, Z6, Z7. Граф представляє символічне відображення словесного опису автомата визначеного завданням. В даному випадку це означає, що при зміні вхідного сигналу на інший автомат змінює свій стан на той в який повинен перейти робот при виконані даної команди. Щоб не ускладнювати задачу будемо вважати що одна команда вперед пересуває нашого робота на одну клітинку в той бік в який він дивиться, команда вліво повертає нашого робота навколо своєї осі на 90° проти годинникової стрілки, команда вправо – повертає нашого робота на 90° за годинниковою стрілкою, команда розвантажити залишає на місці нашого робота вантаж (предмет), не рухаючи при цьому самого робота, команда завантажити – завантажує предмет за умови що в тій клітинці де знаходиться робот знаходиться й вантаж і теж не рухає робота. На рис.4 показано граф, який демонструє всі існуючі стани автомату  та переходи з одного стану в інший. Переходи, які не змінюють стану автомату на графі не показані, але їх наявність мається на увазі. 

Рис.4 Граф переходів автомата

Крім  графового використовують табличне представлення функціонування автомата (табл.1). 

Таблиця 1

Порожні клітинки в таблиці свідчать про те, що в деяких станах за умовою задачі деякі вхідні команди ігноруються, так як їх виконання неможливе у поточному стані. Наприклад: не можна у стані Z0 (дивитися вгору і бути завантаженим) – завантажитись, чи у стані Z4 – ще раз розвантажитись.

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

Таблиця 2

2.3 Реалізація  програми-симулятора

Для реалізації програми використовуємо програмне  середовище Delphi.

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

2.3.1 Вибір  методів та засобів для реалізації програми

Програма-симулятор  складається з трьох частин: програми-керування, програми яка візуально показує  поточний стан автомату та безпосередньо  програми-симулятора робота. Всі дані програми зв’язуються між собою  за допомогою так званих системних повідомлень Windows. Існує цілий ряд функцій API Windows, які працюють з вікнами – всі вони неявно використовують різні повідомлення Windows. Але взаємодію наших програмних додатків можливо організувати і явним способом через повідомлення Windows.

      Додатки Windows складаються з множини об’єктів, які взаємодіють один з одним, обмінюючись повідомленнями (messages). Джерелом цих повідомлень можуть бути: користувач, оперуючий клавіатурою і мишою, середовище Windows, посилаюче повідомлення додаткам, інші додатки, які обмінюються повідомленнями з нашим і на останнє наша програма посилаюча повідомлення своїм компонентам.

 Більшість повідомлень Delphi обробляє саме, а тому нам достатньо використовувати обробники стандартних повідомлень компонентів.  Якщо ж стандартними повідомленнями не можна вирішити задачу розробник може використовувати власні повідомлення, власноруч їх відправляючи та опрацьовуючи. В Windows API існує цілий ряд функцій дозволяючи відправлення повідомлень. В роботі використана одна з них а саме: function SendMessage(hWnd: HWnd; Msg, wParam: word; lParam: longInt): LongInt;

Параметр  hWnd – дескриптор вікна, якому передається повідомлення. Параметр Msg визначає повідомлення, яке передається. Параметри wParam і lParam містять в нашому випадку корисну інформацію, а саме код команди (вхідні параметри для нашого автомата).

Дескриптор  вікна, якому треба передати повідомлення можна визначити за допомогою  функції FindWindows якій передаються два параметри: клас вікна та назва вікна, а функція повертає дескриптор даного вікна [4]. В моїй програмі дана функція має наступний вигляд: FindWindow('Tform1','Робот'); а сама функція SendMessage записується так: sendmessage (FindWindow ('Tform1','Робот'), WM_User,3,3); де WM_User – ідентифікатор мого повідомлення, а параметри 3, 3 – коди команд.

Код програми, яка посилає різні повідомлення, тобто різні команди:

procedure Tclient.BitBtn1Click(Sender: TObject);

begin

sendmessage(FindWindow('Tform1','Робот'),WM_User,1,1);

end; 

procedure Tclient.BitBtn2Click(Sender: TObject);

begin

sendmessage(FindWindow('Tform1','Робот'),WM_User,2,2);

sendmessage(FindWindow('Tform1','Робот'),WM_User,2,2);

sendmessage(FindWindow('Tform1','Робот'),WM_User,1,1);

end; 

procedure Tclient.BitBtn3Click(Sender: TObject);

begin

sendmessage(FindWindow('Tform1','Робот'),WM_User,2,2);

end; 

procedure Tclient.BitBtn4Click(Sender: TObject);

begin

sendmessage(FindWindow('Tform1','Робот'),WM_User,3,3);

end; 

procedure Tclient.BitBtn5Click(Sender: TObject);

begin

sendmessage(FindWindow('Tform1','Робот'),WM_User,4,4);

end; 

procedure Tclient.BitBtn6Click(Sender: TObject);

begin

sendmessage(FindWindow('Tform1','Робот'),WM_User,5,5);

end; 

Обробка повідомлень. В усіх віконних компонентах  існують обробники повідомлень  Windows за замовчуванням. Але для власного повідомлення слід використовувати і власний обробник. Тому достатньо самому написати функцію обробник повідомлення яка має наступний вигляд:

Procedure <ім’я процедури> (var <параметр>: <тип параметру> ); message <повідомлення>; Тут <тип параметру> - це тип структури параметрів повідомлення. Зазвичай ім’я цього типу відповідає імені обробленого повідомлення з додаванням префіксу Т. Після ключового слова message записується тип повідомлення[4].