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

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

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

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

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

    

Курсова робота з прикладної математики 
Шевченка  Ігоря  Віталійовича 
студента 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 Синтез  комбінаційної схеми