10. Абстрактный автомат. Соединение двух автоматов: параллельное

соединение. Пример.

Абстра́ктный автома́т (в теории алгоритмов) — математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. На вход этому устройству поступают символы одного алфавита, на выходе оно выдаёт символы (в общем случае) другого алфавита.

Абстрактный автомат

Формально абстрактный автомат определяется как пятерка

Где S — конечное множество состояний автомата, X, Y — конечные входной и выходной алфавиты соответственно, из которых формируются строки, считываемые и выдаваемые автоматом,  — функция переходов,  — функция выходов.

Параллельное соединение:

Параллельное соединение

Пусть заданы два автомата Мили:

 

Параллельное соединение возможно, если только . Считаем также, что задано устройство , объединяющее выходы и реализующее функцию  ,  представленную на рисунке 5.5. Для эквивалентного автомата Мили    (рисунок.5.6) имеем выходной алфавит

 

       

 

  

 

 

множество состояний ,

функцию переходов  

функцию выходов 

и начальное состояние .

 

Пример 5. Пусть автоматы    заданы таблицами 5.4 и 5.5 соответственно, функция  таблицей 5.6. Считаем, что .

Результирующий автомат характеризуется совмещенной  таблицей переходов/выходов (таблица 5.7).

 

11. Абстрактный автомат. Соединение двух автоматов последовательное.

Пример.(про АО см.10 вопр)

Соединение последовательно:

Последовательное соединение

 

Пусть задано последовательное соединение автоматов Мили    (рисунок 5.7). Предполагается, что выходной алфавит  совпадает с входным алфавитом 

Тогда для эквивалентного последовательного автомата Мили имеем:

множество состояний  ,

функцию переходов 

и функцию выходов 

 

Пример 6. Рассмотрим последовательное соединение автоматов    из примера 5. Считаем, что  . Тогда последовательное соединение    характеризуется совмещенной  таблицей переходов/выходов (таблица 5.8).

12. Абстрактный автомат. Соединение автоматов с обратной связью.

Пример. (про АО см.10 вопр)

13. Сети и коллективы автоматов.

19. Конечный автомат– математическая модель дискретных объектов, в которых переход из одного состояния в любое другое может быть совершен за конечное число шагов.

Конечный автомат является частным случаем машины Тьюринга <A₁,Q₁,S>, а именно:

• внешний алфавит конечного автомата А₁=АВ, АВ=, где А – входной алфавит, В – выходной алфавит;

• внутренний алфавит Q₁=Q(т.е.D={dл,dп,dн}=);

соответствие Sвход-выход конечного автоматаQAQB,DomSQA,JmSQB.

В этом плане конечный автомат U₃= <A,Q,B,S> в общем случае (как трансдъюсер)является частичным (т.е. не всюду определенным) и недетерминированным.

Автомат U₃=<A,Q,B,Г>, где Г – отображения, будем называтьвсюду определенным недетерминированным конечным автоматом.

Автомат U₃=<A,Q,B,Г_f>, где Г_f– функциональное отображение, называетсявсюду определенным детерминированным конечным автоматом.

Далее будем рассматривать инициальные автоматы, в которых Г_fесть характеристические функции переходаи выхода, т.е:U₃(q₀)=<A,Q,B,q₀,,>,q₀Q,:QAQ,:QAB

Напоминание:

1) Кортеж <A,Q,B,,> есть трансдьюсер, т.е. Г_f: А*В*

2) Кортеж <A,Q,> - акцептор (распознаватель), т.е.L(₃)А*, если(q₀,)=q­_iq₀..q_z,q_zQ,q_z– конечное состояние конечного автомата .

3)Конечный автомат называется комбинационным автоматом, если все его состоянияQэквивалентны между собой, т.е.b_e=(q_i, а)=(q_j, а) (выходной символb_eВ не зависит от состояния автомата, а определяется только входным символом аА). В свете этого определения минимальный (приведенный) комбинационный автомат, т.е. еслиQ=1, есть автомат без памяти <A,B,>, для которого функция переходоввырождена, а функция выходов имеет вид функции одного аргумента –(a_i)=b_j,a_iА,b_jВ

4) Конечный автомат, в котором А=В={0,1}называют логическим.