Головна

Модифікації та види автоматів

  1. N Підготовка проводів в залежності від типу виробництва виконується вручну або за допомогою автоматів.
  2. Аллотропние модифікації вуглецю
  3. Аллотропние модифікації фосфору
  4. Базові модифікації лічильників Альфа
  5. Питання 5. Сучасні модифікації еволюційної теорії
  6. ПИТАННЯ N 66. Договір роздрібної купівлі-продажу з використанням автоматів вважається
  7. Концепція операційного і керуючого автоматів

Введене поняття автомата є досить загальним. У літературі з теорії автоматів (найчастіше під різними назвами) розглядаються більш приватні випадки, одержувані накладенням тих чи інших обмежень на компоненти Q, X, Y; Y, F автомата.

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

Наприклад, якщо у визначенні автомата під Y и F розуміти НЕ функції з Q ? X в Q і із Q ? X в Y, А відповідно відношення Y I Q ? X ? Q і ставлення F I Q ? X ? Y, То ми отримуємо більш загальне визначення - визначення так званого недетермінірованного автомата.

Автомат, визначення який ми ввели раніше, виглядає при цьому окремим випадком недетермінірованного автомата; і, якщо ми хочемо підкреслити цю обставину, ми говоримо, що наше попереднє поняття автомата - це визначення детермінованого автомата, одержуваного в тому спеціальному випадку, коли відносини Y I Q ? X ? Q и F I Q ? X ? Y вироджуються в відображення або, що те ж, коли зазначені відносини задовольняють умові детерміністичного (Однозначності).

Ми не будемо розглядати недетерміновані автомати.

Ще одна модифікація автомата - так званий асинхронний автомат. У нього в якості F замість відображення з Q ? X в Y використовується відображення з Q ? X в Y *.

І ще одна модифікація полягає в тому що, замістьY и F використовуються випадкові функції. Це так звані імовірнісні автомати.

Існують або винаходяться і багато інших модифікації.

Жодна з них не буде нами розглядатися.

Ми обмежимося вивченням різновидів звичайного детермінованого автомата.

Як уже сказано, різні приватні види автоматів виходять накладенням тих чи інших обмежень на компоненти Q, X, Y; Y, F автомата загального вигляду.

Дуже суттєвими є обмеження на потужності вживаних алфавітів. Зокрема, якщо всі безлічі Q, X, Y кінцеві, відповідний автомат називається кінцевим автоматом. У будь-якому іншому випадку він називається нескінченним.

Особливо відзначимо випадки виродження, коли той чи інший з алфавітів складається з однієї літери. У подібних випадках буває зручно розглядати спрощені визначення автомата, які виходять шляхом видалення вироджених компонент з п'ятірки (Q, X, Y; Y, F) І відповідної зміни інших компонент.

Загалом, предмет вивчення сучасної теорії автоматів можна схематично зобразити так.

Сучасна теорія автоматів

модифікації автоматів (детерміновані) автомати

н. А., а. А., ст. А., ... (к. Б.) А. Б. П., ав. А., а. Б. В., а. З., а. М.

н. А. Б. В., мн. А Б В.

Ліва гілка - не наша справа. Права - це наш план на весь курс (скільки встигнемо).

Тож почнемо.

А. Б. П. (Автомат без пам'яті). Автомат без пам'яті - Це трійка (X, Y; F ), Де F - Відображення вхідного алфавіту X в вихідний алфавіт Y, Т. Е F : X ® Y.

Інакше кажучи, команди автомата без пам'яті мають вигляд xr ® ys, де xr I X, ys I Y.

Рекурентні співвідношення (1) приймають в цьому випадку вид

y(T) = F[x(T)], (1а)

т. е вихідний символ на даному такті (для даного t) залежить тільки від вхідного символу на даному такті і анітрохи не залежить від інших символів.

Поняття инициального автомата в цьому випадку не потрібно, так як немає безлічі Q. Можна, звичайно, домовитися вважати, що безліч Q мається на увазі що складається всього з одного стану. Його і можна вважати перманентно виділеним, і, отже, вважати, що все ініціальні автомати без пам'яті дорівнюють один одному і збігаються з самим автоматом.

Іншими словами, кожен а. Б. П. реалізує єдиний словниковий (і єдиний сверхсловарний) оператор, який здійснює «політерний переклад» вхідних символів у вихідні. Такі оператори називаються істиннісними операторами або операторами без пам'яті.

Число всіх автоматів без пам'яті з даними кінцевими алфавітами X = {x1, x2, ..., xm}, Y = {y1, y2, ..., yn} дорівнює nm.

Ав. А. (Автономний автомат). автономний автомат - Це четвірка (Q, Y; Y, F ), Де Y и F відображають Q в Q и Q в Y відповідно.

Команди автономного автомата мають вигляд qi ® qj ys, А рекурентні співвідношення (1) -

q(T + 1) = Y[ q(T)],

y(T) = F[ q(T)]. (1б)

При кожній фіксації (2) початкового стану q(1) = q0 автономного автомата співвідношення (1б) однознчно визначають єдине вихідна Надслово y(1) y(2) ... і єдине внутрішнє Надслово q(1) q(2) ...

Очевидно, якщо автономний автомат кінцевий і число його станів одно k, То вже серед значень q(1) q(2) ... q(k + 1) знайдуться повторювані стану.

Отже, кожне з двох сверхслов y(1) y(2) ... і q(1) q(2) ... виявиться періодичним (не обов'язково чисто періодичним, т. Е, можливо, з деяким предперіодом) і з довжиною періоду, що не перевищує числа станів автомата.

Число автономних автоматів з даними алфавітами Q = {q1, ..., qk} і Y = {y1, y2, ..., yn} Дорівнює (nk)k.

А Б В. (Автомат без виходу). Автомат без виходу - Це трійка (Q, X; Y)., Де Y відображає Q ? X в Q.

Команди автомата без виходу приймають вид qi xr ® qj , А з рекурентних співвідношень (1) зберігається лише перше:

q(T + 1) = Y[ q(T), x(T)]. (1в)

Загальна кількість автоматів без виходу з алфавітами Q = {q1, ..., qk} і X = {x1, x2, ..., xm} дорівнює k mk.

Поведінка автомата без виходів не може бути охарактеризоване в термінах словникових (або сверхсловарних) операторів, переробних вхідні слова (надсловом) у вихідні слова (надсловом).

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

Однак для автоматів без виходу цікавіше визначити поведінка не в термінах операторів, а в термінах мов і сверх'язика.

Нехай для автомата M = (Q, X; Y) Зафіксовані стан q0, І вхідний слово x = x(1) x(2) x(3) ... x(R). Тоді рекурентні співвідношення

q(1) = q0, q(T + 1) = Y[ q(T), x(T)]

однозначно визначають внутрішнє слово q(1) q(2) ... q(r) q(r + 1). Зверніть увагу: слово x має довжину r, а слово q - Довжину r + 1.

Якщо при цьому q(r + 1) = q?, то будемо говорити, що слово x переводить стан q0 в стан q?.

налаштованим автоматом (Без виходу) називається трійка (M, q0, Q ?), де M - автомат без виходу, q0 - Деякий виділене його стан (початковий стан), Q ? - деяка підмножина безлічі Q його станів (Q ? - безліч фінальних станів).

Безліч (можливо порожній) всіх вхідних слів, кожне з яких переводить q0 в яке-небудь фінальне стан q I Q ?, називається мовою, репрезентованою налаштованим автоматом (M, q0, Q ?), або його поведінкою, І позначається через w (M, q0, Q ?).

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

А саме, подача вхідного слова x = x(1) x(2) x(3) ... x(R) на вхід автомата тлумачиться як питання: чи належить це слово, що цікавить нас мови?

Якщо в результаті подачі слова автомат виявиться в фінальному стані, то відповідь ствердна; в іншому випадку він негативний.

Тепер підемо далі.

Інший варіант поняття поведінки для автомата без виходу можна заснувати на розгляді вхідних сверхслов, Які автомат сприймає.

Нехай дано деякий Надслово a = a(1)a(2) ... в алфавіті A.

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

Наприклад, буква a - Граничний символ для надсловом bbaaaaa ..., А буква b - Чи не граничний символ для цього ж надсловом.

позначимо через lim x безліч всіх символів, граничних для надсловом x.

Зафіксуємо в автоматі M = (Q, X; Y) стан q0 і вхідний Надслово x = x(1) x(2) ...

Тоді рекурентне співвідношення (1в) плюс початкова умова q(1) = q0 однозначно визначають деякий внутрішнє Надслово q = q(1) q(2) ...

Ми могли б сказати, що автомат M з початковим станом q0 переводить вхідний Надслово x у внутрішнє Надслово q.

Але замість цього краще говорити, що вхідний Надслово x переводить стан q0 автомата M в граничне безліч станів Q ?, де Q ? = lim q.

Очевидно, що Q ? I Q.

Тепер, за аналогією з «настроюванням» автомата M, розглянемо «макронастройку» автомата, яка полягає у виділенні початкового стану і системи граничних множин станів.

Це призводить нас до наступних визначень.

макросостояніем автомата назвемо будь-яка підмножина його станів.

Макронастроенним автоматом називається трійка (M, q0, C), де M - автомат без виходу, q0 - Виділене (початкова) його стан, C - довільно виділене безліч його макросостояніе (званих граничними макросостояніе).

Нехай заданий макронастроенний автомат (M, q0, C). Тоді безліч всіх сверхслов, кожне з яких переводить q0 в якесь граничне макросостояніе Q ? I C, називається сверх'язика, що подаються до макронстроенном автоматі (M, q0, C), і позначається W (M, q0, C).

КІНЕЦЬ.

Загальне поняття автомата | Психологічні прийоми спрямовані на підвищення уваги.

© 2016-2022  um.co.ua - учбові матеріали та реферати