Специальная математика. Соловьев А.Е. - 41 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

Составители: 

Рубрика: 

- краткие и развернутые,
- полные и неполные.
Временные логики :
Высказывание А,
Р
А
- "было А"
F
A
- "будет A"
A B - "если А, то после этого В".
3. Теория Автоматов
3.1. Понятие автомата
Автомат - дискретный преобразователь информации, на вход которого поступают
входные последовательности сигналов (входные слова). Он формирует выходные
последовательности сигналов на основании своих внутренних состояний и входной
последовательности сигналов.
В курсе рассматривается абстрактная теория автоматов.
Нас будет интересовать их поведенческий аспект. Автомат для нас – математическая модель,
а не физическое устройство. Автоматы фактически позволяют реализовать логику,
зависящую от времени.
Не рассматриваемая здесь структурная теория автоматов занимается реализаций
абстрактного автомата с помощью физических сущностей, вроде элементов памяти
(например, триггеров) и комбинационных (логических) схем…
Будем иметь в виду две ключевые абстракции:
1. Автомат функционирует в абстрактном времени.
2. Все переходы происходят мгновенно.
Автомат есть система шести объектов:
= <X, Y, Q, f, , q
0
>
X = {x
1
,...,x
n
} - конечный входной алфавит (множество входных сигналов).
Y = {y
1
,...,y
m
} - конечный выходной алфавит (множество выходных сигналов).
Q = {q
0,
q
1
,...,q
k
} – множество состояния автомата.
Если множество конечно автомат называется конечным.
f (q, x) - функция переходов.
(q, x) - функция выходов.
q
0
Q - начальное состояние.
Законы функционирования автоматов
q(t) = f(q(t-1), x(t))
y(t) = (q(t-1), x(t))
q(t) = f(q(t-1), x(t))
y(t) = (q(t), x(t))
q(t) = f(q(t-1), x(t))
y(t) = (q(t))
3.2. Примеры автоматов
Замечание. Для удобства восприятия и сокращения описания будем говорить об автоматах
как об автоматических роботоподобных устройствах, хотя на самом деле это, как уже было
— 41 —
}
}
}
Автомат I-го рода (автомат Мили)
Автомат II-го рода
Правильный автомат II-го рода
(автомат Мура)
   - краткие и развернутые,
   - полные и неполные.

Временные логики :
   Высказывание А,
   РА - "было А"
   FA - "будет A"
  A      B - "если А, то после этого В".

                                    3. Теория Автоматов
                                     3.1. Понятие автомата

    Автомат - дискретный преобразователь информации, на вход которого поступают
входные последовательности сигналов (входные слова). Он формирует выходные
последовательности сигналов на основании своих внутренних состояний и входной
последовательности сигналов.
В курсе рассматривается абстрактная теория автоматов.
Нас будет интересовать их поведенческий аспект. Автомат для нас – математическая модель,
а не физическое устройство. Автоматы фактически позволяют реализовать логику,
зависящую от времени.
Не рассматриваемая здесь структурная теория автоматов занимается реализаций
абстрактного автомата с помощью физических сущностей, вроде элементов памяти
(например, триггеров) и комбинационных (логических) схем…
Будем иметь в виду две ключевые абстракции:
 1. Автомат функционирует в абстрактном времени.
 2. Все переходы происходят мгновенно.
  Автомат есть система шести объектов:
  =  0

  X = {x1,...,xn} - конечный входной алфавит (множество входных сигналов).
  Y = {y1,...,ym} - конечный выходной алфавит (множество выходных сигналов).
  Q = {q0, q1,...,qk} – множество состояния автомата.
  Если множество конечно автомат называется конечным.
  f (q, x) - функция переходов.
   (q, x) - функция выходов.
  q0  Q - начальное состояние.

                             Законы функционирования автоматов
q(t) = f(q(t-1), x(t))
y(t) = (q(t-1), x(t))   }   Автомат I-го рода (автомат Мили)

q(t) = f(q(t-1), x(t))
y(t) = (q(t), x(t))     }   Автомат II-го рода

q(t) = f(q(t-1), x(t))
y(t) = (q(t))           }   Правильный автомат II-го рода
                             (автомат Мура)
                                    3.2. Примеры автоматов
Замечание. Для удобства восприятия и сокращения описания будем говорить об автоматах
как об автоматических роботоподобных устройствах, хотя на самом деле это, как уже было

                                              — 41 —

Страницы