ЗМІСТ
Введення
1.Абстрактний синтез кінцевого автомата
1.1Формування алфавітного оператора
1.2Приведення оператора до автоматної увазі
1.3Побудова графа переходів абстрактного автомата
1.4Мінімізація абстрактного автомата
2. Структурнийсинтез кінцевого автомата
2.1Кодування станів, вхідних і вихідних сигналів
2.2Формування функцій збудження і вихідних сигналів структурного автомата
Висновок
Списоклітератури
В ВЕДЕННЯ
Теорія автоматів - цетеорія, на якій засновані експериментальні методи дослідження вкібернетиці. При підході до теорії автоматів, як до частини теорії алгоритмів,центральною проблемою є вивчення можливостей автоматів в термінахмножин слів, з якими працюють автомати.
Можна виділити дваосновних аспекти роботи автомата.
1.Автомати-розпізнавача,які розпізнають вхідні слова, тобто відповідають на питання, чи належитьподане на вхід слово даним безлічі.
2.Автомати-перетворювачі,які перетворять вхідні слова у вихідні, тобто реалізують автоматнівідображення.
Одним із завдань теоріїавтоматів є задача опису автомата і його реалізації, тобтопредставлення автомата як структури, що складається з об'єктів фіксованоюскладності. У цьому відношенні теорія автоматів виявилося найбільш розвиненою галуззютеорії алгоритмів.
Загальна теорія автоматівпідрозділяється на абстрактну теорію і структурну теорію автоматів.Абстрактна теорія автоматів займає проміжне положення між алгеброю ілогікою. З точки зору додатків значення абстрактної теорії автоматів аж ніякне зводиться до задоволення запитів однієї лише обчислювальної техніки.Сучасна теорія автоматів являє собою математичний апарат длявирішення широкого класу комбінаторних проблем.
Структурна теоріяавтоматів дозволяє реалізувати абстрактний автомат на елементах, що належатьдо заздалегідь заданому класу.
Дляперетворення дискретної інформації в різних областях техніки використовуютьсяцифрові автомати. До цифровим автоматам відносяться окремі вузли і блокиспеціалізованих і універсальних ЦВМ і ЦВМ в цілому. Цифровими автоматамиможуть бути названі також пристрої, в автоматиці, телемеханіки, радіолокації іінших областях техніки, в яких вимагається виконувати перетворення надсигналами, представлені в дискретної (цифровій) формі.
Першеправило функціонування автоматів полягає в наступному. Автоматнеобов'язково повинен запам'ятовувати вхідні історії. Цілком достатньо, щобавтомат запам'ятав клас еквівалентностей, до якого доводиться дана історія.
Другеправило функціонування автоматів полягає в тому, що на один і той же вхіднийсигнал кінцевий автомат може реагувати по-різному, залежно від того, вякому стані він перебуває зараз.
Кінцевийавтомат - це пристрій, що працює в дискретні моменти часу, або такти.На вхід кінцевого автомата в кожному такті надходить один з можливихвхідних сигналів, а на його виході з'являється вихідний сигнал, який єфункцією його поточного стану і надійшов вхідного сигналу.
Внутрішністану автомата також змінюються. Моменти спрацьовування (такти), визначаютьсяабо примусово тактирующие синхросигналами, або асинхронно, настаннямзовнішнього події, тобто приходом сигналу.
Існуєдва види реалізації кінцевого автомата - апаратна і програмна. У першучергу, реалізація кінцевого автомата вимагає побудови пристрою пам'яті длязапам'ятовування поточного стану автомата. Зазвичай використовуються двійкові елементипам'яті, або тригери, що запам'ятовують значення одного двійкового розряду.
1.А БСТРАКТНИЙ СИНТЕЗ КІНЦЕВОГО АВТОМАТА
1.1Формування алфавітного оператора
Для визначенняпараметрів завдання необхідно ввести первинну інформацію:
- порядковий номер вжурналі;
- рік вступу;
- номер групи;
Для даного завдання цевідповідно:
21,08, 02.
З цих цифр необхідноскласти правильну десяткову дріб, в якій ці цифри йдуть відразу післякоми:
Y1 =0,210802
Вторинна інформація Y, Y3, Y4виходять шляхом зведення 1в степені 2, 3, 4 і видаленням в дробу всіх нулів між комою і першоюзначущою цифрою.
Y2= 0,444374
Y3= 0,93675
Y4= 0,19747
Для отримання значень вхіднихі вихідних сигналів автомата необхідно отримані десяткові дробиперетворити в двійковий код до шістнадцятого знака.
В результатіперетворень отримані наступні значення заданих сигналів.
Y1= 0011010111110111
Y2= 0111000111000010
Y3 =1110111111001110
Y4= 0011001010001101
Отримані значеннязаписуються у стовпцях: перші 8 значень в лівій частині, другі 8 - у правійчастини. Алфавітний оператор відповідності представлений в таблиці 1.
Таблиця 1. Алфавітнийоператор відповідності
Вхідні сигнали
Вихідні сигнали
0010
1111
0110
1110
1111
1000
1101
1000
0010
0011
1010
1011
0011
1110
1110
1001
1.2 Приведення оператора до автоматної увазі
Для того щоб операторперетворився до автоматної увазі, необхідне виконання трьох умов:
1. Будь-яким двомоднаковим початковим відрізкам вхідних слів повинні відповідати однаковіпочаткові відрізки вихідних слів;
2. Довжина вхідного словаповинна дорівнювати довжині вихідного слова;
3. Останній символповинен повертати автомат в початковий стан.
Даний оператор ужевирівняний, так як довжина кожного з вхідних слів дорівнює довжині відповідноговихідного слова. Кожному вхідному слову тут зіставляються не більше одноговихідного слова, тому оператор однозначний. Однак він не задовольняєумові повноти.
Таким чином,автоматний вид оператора прийме, наступний вигляд:
Таблиця 2. Автоматнийвид
Вхідні сигнали
Вихідні сигнали
0010
1111
0110
1110
1111
1000
1101
1000
00100000
11110011
1010
1011
0011
1110
1110
1001
1.3 Побудова графа переходів абстрактного автомата
Побудуємо за таблицею 2граф переходів автомата. При цьому передбачається, що останній символ кожноговхідного слова повинен переводить автомат в початковий стан.
Граф переходівабстрактного автомата представлений у додатку 1.
1.4 Мінімізація абстрактного автомата
За графу переходівпобудуємо таблицю переходів-виходів заданого автомата (таблиця 3).
Таблиця 3. Таблицяпереходів-виходів автомата
a (t-1)
0
1
a 0
a 1 /1
a 2 /1
a ...
