Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Композиция автоматов






Пусть заданы автоматы Â 1 и Â 2, имеющие соответственно m 1 и m 2 входов, а также n 1 и n 2 выходов (рис. 7.11).

 
 


x 1 y 1 x 1 y 1

... Â 1 ... Â 2

 

xm 1 yn 1 xm 2 yn 2

Рис. 7.11

Пусть k - такое целое число, что k n 1 и k m 2.

Тогда композицией Â 1 и Â 2 называется автомат, который получается из Â 1 и Â 2 подсоединением k различных выходов Â 1 к k различным входам Â 2.

Например, так как это выполнено для случая, изображенного на рис. 7.12.

 
 


... Â 2

...

 1 ...

...

 

...

 

Рис. 7.12

 

Понятно, что функционирование полученного устройства является корректным, если символы, появляющиеся на выходах Â 1 и поступающие на входы Â 2 принадлежат одному и тому же алфавиту.

Для простоты будем считать, что множества символов, появляющихся на любых входах и выходах автоматов всегда являются символами одного и того же алфавита.

 

Упражнение. Определить число выходов композиции автоматов Â 1 и Â 2в указанных ранее условиях.

 

Если автоматы Â 1 и Â 2 имеют по одному входу и одному выходу, то композиция таких автоматов, изображенная на рис. 7.13, называется суперпозицией Â и Â 2.

 
 


 1  2

Â

 

Рис. 7.13

 

Пусть заданы два автомата Â 1 = (A, A, Q 1, j1, y1) и Â 2 = (A, A, Q 2, j2, y 2).

Суперпозиция этих автоматов представляет собой автомат

 = (A, A, Q 1 Q 2, j, y), т.е. множество состояний автомата  - это множество пар (q i, q j), где q i Î Q 1 и q j Î Q 2.

Пусть начальные состояния автоматов Â 1 и Â 2 - это соответственно q 0 и q l.

Выпишем канонические уравнения для автомата Â:

q 1(t 0) = q 0;

q 2(t 0) = q l;

q 1(t +1) = j1(x (t), q 1(t));

q 2(t +1) = j2(y1(x (t), q 1(t)), q 2(t));

y (t) = y2(y1(x (t), q 1(t)), q 2(t)).

То есть y = y2(y1(x (t), q 1(t)), q 2(t)), где x (t) - это символ на входе Â 1, а q 1(t) и q 2(t) - состояния Â 1 и Â 2 в момент t. Функция перехода j представляет собой пару функций, определяющих первую и вторую компоненты состояния Â в следующий момент времени.

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.