Кінцеві автомати та способи їх завдання. Автомати Методи завдання Основні визначення n Кінцевим. Стандартні або автоматичні мови опису

Як зазначалося раніше, Y (x, q)задає порядок перетворення вхідних символів та стану автомата на попередньому такті у стан на наступному, a Q (x, q) -перетворення вхідних символів та стану автомата на поточному такті у вихідний символ. Якщо q 0 - початковий стан автомата, а i- Номер такту, то його робота описується системою:

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

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

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

У табличному способіавтоматичні функції задаються двома кінцевими таблицями, що називаються відповідно матрицею переходіві матрицею виходів.У цих таблицях рядки позначаються літерами вхідного алфавіту, а стовпці - літерами внутрішнього алфавіту (символами, що кодують внутрішній стан автомата). У матриці переходів на перетині рядка (x k)та стовпця (q r)містяться значення функції Y ( q r, x k),а у матриці виходів - значення функції Q (q r, x k).

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

План:

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 двійкових наборів довжини п.Для логічних комбінаційнихавтоматів функція виходу має вигляд системи п логічних функцій від тзмінних.

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

По вхідному каналу в кожний момент часу t =1, 2, ... пристрій М надходять вхідні сигнали (з деякої кінцевої множини сигналів). Задається закон зміни стану до наступного моменту часу в залежності від вхідного сигналу та стану пристрою у поточний момент часу. Вихідний сигнал залежить від стану та вхідного сигналу у поточний момент часу (рис. 1).

Кінцевий автомат є математичною моделлю реальних дискретних пристроїв із переробки інформації.

Кінцевим автоматом називається система А = (X , Q , Y ,  ,  ), де X , Q , Y - довільні непусті кінцеві множини, а  і   функції, з яких:

безліч X ={a 1 , ..., a m ) називається вхідним алфавітом , а його елементи - вхідними сигналами , їх послідовності - в хідними словами ;

безліч Q ={q 1 , ..., q n ) називається безліччю станів автомата, а його елементи - станами ;

безліч Y ={b 1 , ..., b p ) називається вихідним алфавітом , його елементи - вихідними сигналами , їх послідовності - вихідними словами ;

функція  : X  Q Q називається функцією переходів ;

функція  :X  Q Y називається функцією виходів .

Таким чином,  (x , q )Q ,  (x , q )Y для  x X , q Q .

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

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

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

2.1.Таблічне завдання автомата

З визначення автомата слід, що його можна задати таблицею з двома входами, що містить т рядків та п стовпців, де на перетині стовпця q та рядки а стоять значення функцій  (a i , q j ),  (a i , q j ).

2.2. Завдання автомата діаграмою Мура

Інший спосіб завдання кінцевого автомата – графічний, тобто за допомогою графа. Автомат зображується як позначеного орієнтованого графа Г(Q , D ) з безліччю вершин Q і безліччю дуг D ={(q j ,  (a i , q j ))| q j Q , a i X ), при цьому дуга ( q j ,  (a i , q j )) позначається парою ( a i ,  (a i , q j )). Таким чином, при цьому способі стану автомата зображують кружками, які вписують символи станів q j (j = 1, …, n ). З кожного гуртка проводиться т стрілок (орієнтованих ребер) взаємно-однозначно відповідних символам вхідного алфавіту X ={a 1 , ..., a m ). Стрілці, що відповідає літері a i X і виходить із гуртка q j Q , приписується пара ( a i ,  (a i , q j )), причому ця стрілка веде до гуртка, відповідного  (a i , q j ).

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

Рекомендуємо почитати

Сантехніка

Два тести показали дві смужки: принцип роботи тесту на вагітність, інструкція із застосування, результат, проведення УЗД та консультація гінеколога Що робити тест показує дві смужки

Меблі

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

Меблі

Які краплі в ніс щоб. Види назальних крапель. Краплі бурякові від нежитю

Заміський будинок

У чому причина постійного бажання пити?

Шпалери

Централізована бібліотечна система хайбуллінського району республіки башкортостан Б'янка Ігор Куберський

Оздоблення

Сир з козячого сиру в домашніх умовах