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