Задания на практические работы по дисциплине
«Моделирование систем»
Санкт-Петербург
2009
Содержание
Модели конечных автоматов относятся к классу дискретных детерминированных моделей функционирования. Автомат можно представить как некоторое устройство, на которое поступают входные сигналы xi Î C и снимаются выходные сигналы yj Î Y. Сам автомат имеет некоторые внутренние состояния sk Î S. Конечным автоматом называется автомат, у которого множества X, Y, S конечны
При рассмотрении логической структуры автоматов считают, что переменные изменяются мгновенно в некоторые моменты времени, называемые тактами. Функционирование автомата рассматривается на некотором интервале времени T. Интервалы между тактами на данном интервале могут быть различными, но без потери общности их можно считать равными Dt. Предполагается, что тактовые моменты времени t(i+1) = t(i) + Dt определяются синхронизирующими сигналами. Таким образом, вводится дискретное автоматное время t(i) (i = 0, 1, 2, 3,…) и вместо непрерывных x(t) рассматриваются дискретные x(i) .
Абстрактно конечный детерминированный автомат можно представить пятеркой A = < X, Y, S, T, d, l >, где d - функция переходов, l - функция выходов. С помощью данных функций задаются два уравнения: уравнение переходов s(i+1) = d(s(i), x(i)) и уравнение выходов y(i) = l (s(i), x(i)). Здесь под индексом i понимается такт времени. Такое общее определение автомата связывают обычно с автоматом первого рода (автоматом Мили). Если выходные переменные являются функцией только состояния, то имеем автомат второго рода (автомат Мура). Для него уравнение выходов имеет вид: y(i) = l(s(i)).
Задача 1.1 Построить конечный автомат Мили, описывающий работу двухразрядного счетчика, входящего в состав преобразователя «код - временной интервал». Использовать графический способ задания автомата.
Решение: На счетный вход счетчика поступают импульсы с генератора.
Выходом счетчика является сигнал переполнения. Определим входной и выходной
алфавит автомата: 
Ноль на входе означает отсутствие входного сигнала на входе счетчика.
Единица, наоборот, свидетельствует о наличии входного сигнала. В множестве Y ноль означает отсутствие переполнения, а единица –
сигнал переполнения счетчика. Так как двухразрядный счетчик может находиться в
четырех состояниях, то поэтому множество возможных состояний автомата будет
состоять из четырех элементов. Обозначим их 
Существует несколько способов задания автомата, но наиболее известными из них являются: табличный, графический и матричный. При графическом способе задания автомата используется ориентированный граф, вершины которого соответствуют состояниям графа. Если входной сигнал хi вызывает переход из состояния sk в состояние si, то на графе существует дуга, обозначаемая хi, которая соединяет эти две вершины. Для автоматов Мили дуга, кроме того, помечается значением выходного сигнала yj. Для данного примера граф, описывающий конечный автомат, имеет вид, как показано на рис.1.
 |
Рисунок 1
Задача 1.2. Построить автомат, моделирующий управление курсором на знаковом табло автоматизированного рабочего места. Предполагается, что знаковое табло состоит из трех строк, на одной из которых отображается маркер в виде светящегося прямоугольника. Данный маркер может перемещаться вверх или вниз по строкам табло. Для этого используются две кнопки управления перемещением маркера: «вверх» и «вниз». Если маркер находится в верхней строке, то он может перемещаться только вниз. При нажатии кнопки «вверх» никаких изменений в местонахождении маркера не происходит. Аналогичная картина происходит при нахождении маркера в нижней строке.
Решение: Используя графический способ задания автомата, построим автомат Мура. В отличие от автомата Мили, для автомата Мура выходной сигнал yi помечается около вершины sk.
Определим алфавиты, которые использует
конечный автомат:
Здесь входное множество при условии
синхронной работы автомата предусматривает три элемента: 0 – нажатие кнопки
«вверх», 1 – нажатие кнопки «вниз», 2 – отсутствие нажатия кнопки. Состояние
автомата предполагает нахождение маркера в одной из трех строк: 1 – в верхней строке,
2 – в средней строке, 3 – в нижней строке. Граф, описывающий конечный автомат
Мура, состоит из трех вершин, соответствующих трем состояниям автомата (рис.2).
Так как выходное множество определено как пустое множество, то эти вершины не
помечены выходными сигналами. При задании входных сигналов на графе использована
логическая операция «ИЛИ».
Рисунок 2
Задача 1.3. Построить конечный автомат, решающий задачу сканирования слов языка программирования и позволяющий распознать, есть ли в в последовательности сканируемых символов ключевое слово «end».
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
