2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Автомат Мили и Мура. Определение.
Сообщение07.04.2011, 17:44 
Препод говорит, что автомат Мура выдаёт выходной сигнал ещё до момента, как поступил первый входной. Мне кажется, что это противоречит с определением автомата Мура, который этот же препод нам давал. Скажите, что сделать: определение подправить или не верить преподу по поводу лишнего выходного сигнала?

Вот определения из моих лекций.
Конечным дискретным автоматом называется кортеж $ S = (Z, W, A, \delta, \lambda, a_1)$,
где
$Z$ - входной алфавит,
$W$ - выходной,
$A$ - состояния,
$\delta \colon D_\delta \to A, D_\delta \subseteq A \times  Z$
$ \lambda \colon D_\lambda \to W, D_\lambda \subseteq A \times Z $
$a_1$ - начальное состояние.
Абстрактный автомат в момент времени $t$ находится в состоянии $a(1)=a_1$. Находясь в момент времени $t \ne 1$ в состоянии $a(t)$ автомат:
(1) воспринимает входной сигнал $z(t) \in Z$,
(2) выдаёт выходной сигнал $w(t) \in W$,
(3) переходит в состояние $a(t+1)$.

Автомат Мили.
$\left\{
   \begin{aligned}
      a(t+1)=\delta(a(t),z(t)) \\
      w(t+1)=\lambda(a(t),z(t)). \\
   \end{aligned}
\right$

Автомат Мура.
$\left\{
   \begin{aligned}
      a(t+1)=\delta(a(t),z(t)) \\
      w(t+1)=\lambda(a(t)). \\
   \end{aligned}
\right$
Конец цитаты.

Но Когда дело доходит до построения автомата Мура, эквивалентного данному автомату Мили, или наоборот, то возникают проблемы с тем, что у Мура в начале работы есть лишний выходной сигнал, и вообще на равные входные последовательности эти автоматы выдают выходные последовательности разной длины (у Мура длиньше на единицу). Это что за эквивалентность такая, так сказать, с оговорками :-(.
Во вторых, при минимизации автомата Мура с помощью алгоритма Ауфенкампа-Хона (метод последовательных разбиений), препод заставляет делать первое разбиение с учетом как раз того лишнего выходного сигнала, о факте существования которого он утверждает.
Вот, почему мне не нравится позиция препода. Лишний сигнал - источник лишних проблем. В то время, как без него всё хорошо.

А противоречие в следующем. По данному определению $w(1)$ вообще неопределено для обоих автоматов. Если, скажем, $t=1,2,\dots$, то $w(t)$ определено только начиная с $w(2)$, так как определяется через $w(t+1)$.

Что ещё хотел попросить... Препод, если дело касается определений, ссылается на "а в книжке написано...". Поэтому, мне хотелось бы знать не только ответ, но и ему можно найти подтверждение.

Простите за отсутствие лаконичности :-).

 
 
 
 Re: Автомат Мили и Мура. Определение.
Сообщение08.04.2011, 20:39 
Может, все-таки
\begin{align*}
  \begin{cases}
   a(t+1) = \delta(a(t),z(t)),\\
   w(t) = \lambda(a(t),z(t))
  \end{cases}
и
\end{align*}
\begin{align*}
  \begin{cases}
   a(t+1) = \delta(a(t),z(t)),\\
   w(t) = \mu(a(t))
  \end{cases}
\end{align*}
?

 
 
 
 Re: Автомат Мили и Мура. Определение.
Сообщение09.04.2011, 19:59 
_hum_ в сообщении #432587 писал(а):
Может, все-таки
\begin{align*}
  \begin{cases}
   a(t+1) = \delta(a(t),z(t)),\\
   w(t) = \lambda(a(t),z(t))
  \end{cases}
и
\end{align*}
\begin{align*}
  \begin{cases}
   a(t+1) = \delta(a(t),z(t)),\\
   w(t) = \mu(a(t))
  \end{cases}
\end{align*}
?

Вы думаете? Нет, на лекции было дано то определение, которое я привёл. Если ваш вариант взят из надёжного источника, то не могли бы вы привести его название :-) .

 
 
 
 Re: Автомат Мили и Мура. Определение.
Сообщение09.04.2011, 23:59 
Советов Б.Я. Моделирование систем, 2001 (гл. 2.2. Дискретно-детерминированные модели).

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group