авпрол. Задачі Теор_автоматів. Завдання для самостійної роботи
 Скачать 495.5 Kb.
|
|
ЗАВДАННЯ ДЛЯ САМОСТІЙНОЇ РОБОТИ 1. Побудувати таблиці переходів і виходів, граф автомата P, що за допомогою своїх станів запам'ятовує три останні символи (двійкові розряди), які було подано на його вхід. Вихідним сигналом є останній символ, що"забувається". 2. Побудувати таблиці переходів і виходів, граф автомата B, на виході якого з'являється сигнал1 тоді й лише тоді, коли на його вхід була подана послідовність символів, що відповідає числовій константі– дійсному числу зі знаком і фіксованою крапкою; в іншому разі вихідним сигналом є0. Вхідні сигнали автомата B: x1– знак, x2 – цифра, x3– крапка, x4– будь-який ін-ший символ. 3. Побудувати автомат затримки, тобто такий, вихідний сиг-нал якого в момент часу t+ 1 дорівнює вхідному сигналу в мо-мент часу t, X= Y= {0, 1}. 4. Побудувати автомат для X= Y= {0, 1}, на виході якого з'являється сигнал 1 тоді й лише тоді, коли п'ять останніх вхід-них сигналів– це01101. 5. Побудувати генератор парності, тобто автомат, що функці-онує в алфавітах X= Y= {0, 1} і реалізує такий алгоритм. На йо-го вхід надходять слова довжиною3, розділені якимось симво-лом a, a∈X. На виході автомат має повторити вхідну трійку си-мволів, замінивши розділовий символ a на1 тоді й лише тоді, коли кількість одиниць у даній трійці парна. 6. Побудувати автомат, що перевіряє відповідність лівих і правих дужок у вхідному слові, яке задає певний алгебричний вираз. Найбільша дозволена вкладеність дужок– n. Вхідні сиг-нали автомата: x1– ліва дужка, x2 – права дужка, x3– будь-який інший символ, x4– символ, що позначає кінець виразу. 7. Побудувати автомат, що керує роботою ліфта в чотирипо-верховому будинку. Станами автомата є номери поверхів. Вхід-ний сигнал– номер потрібного поверху, вихідний сигнал– на-прямок руху(угору, униз, не рухатись). 8. Побудувати детермiнований скiнченний автомат Мура, який всi букви бiнарного слова ! 2 f0; 1g⁄, що стоять на непарних позицiях, замiнює на букву a, а на парних – на букву b. 9. Нехай X = Y = {0; 1}. Побудуємо детермiнований скiнченний автомат, який "шифрує" всi бiтовi рядки з 0 та 1, замiнюючи всi бiти, якi стоять на позицiях кратних 3, на протилежнi. 10. Приклад 3. На вхід пристрою подаються цифри: 0, 1, 2. Пристрій являється суматором за модулем три. Синтезувати абстрактний автомат. 11.  12  13   14.  15  16.  17  18  19  |