Студопедия

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

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

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






  • Как продвинуть сайт на первые места?
    Вы создали или только планируете создать свой сайт, но не знаете, как продвигать? Продвижение сайта – это не просто процесс, а целый комплекс мероприятий, направленных на увеличение его посещаемости и повышение его позиций в поисковых системах.
    Ускорение продвижения
    Если вам трудно попасть на первые места в поиске самостоятельно, попробуйте технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Если ни один запрос у вас не продвинется в Топ10 за месяц, то в SeoHammer за бустер вернут деньги.
    Начать продвижение сайта
  • Схемы из элементарных автоматов






    Пусть A = { 0, 1 }. Следующие автоматы называются элементарными (см. рис. 7.16):

     

     

    & - Z

     

    Рис. 7.16

    Здесь первые три автомата представляют собой уже известные функциональные элементы, которые для любых входных наборов вычисляют значения соответствующих булевских функций.

    Эти автоматы имеют по одному внутреннему состоянию.

     

    Автомат Z является задержкой для алфавита A = { 0, 1 }.

    Рассмотрим как с помощью схем, составленных из элементарных автоматов, можно представлять произвольные автоматы.

    Пусть Â = (A, B, Q, j, y) - произвольный автомат, для которого:

    A = { a 1,..., a m }, B = { b 1,..., b n }, Q = { q 0,..., q r }, и q 0 - это начальное состояние автомата Â.

    Будем представлять символы алфавитов A и B, а также элементы множества состояний Q с помощью двоичных наборов длины p = ] log 2(m)[, d = ] log 2(n)[ и s = ] log 2(r + 1)[ соответственно.

     

    Заметим, что значения p, d и s выбраны из соображений минимальности длины наборов, которых должно быть не меньше, чем элементов соответствующих множеств.

     

    Для определенности положим, что начальное состояние Â, равное q 0, представляется набором, состоящим из s нулей.

    Рассмотрим автомат Á, имеющий p входов и d выходов, который моделирует работу автомата Â.

    Состояния Á представляются двоичными наборами, имеющими длину s, которые соответствуют состояниям Â.

    Начальным состоянием автомата Á является состояние, представляющее состояние q 0 автомата Â.

    Если в некоторый момент времени на вход Á поступает набор, представляющий символ входного алфавита a i и автомат находится в состоянии, соответствующем состоянию q j, то на выходе Á появляется двоичный набор, представляющий
    y(a i, q j). При этом сам автомат Á переходит в состояние, представляющее состояние j(a i, q j).

     

    Канонические уравнения для автомата Á можно записать в виде:

    q1(t0) = 0;
      ...  
    q s (t0) = 0;
    q1(t+1) = j1(x 1(t),..., x p(t), q1(t),..., qs(t));
      ...  
    q s (t+1) = js(x 1(t),..., x p(t), q1(t),..., qs(t));
    y1(t) = y1(x 1(t),..., x p(t), q1(t),..., qs(t));
      ...  
    yd(t) = yd(x 1(t),..., x p(t), q1(t),..., qs(t)).

     

    Здесь (x 1(t),..., x p (t)) обозначает набор символов, поступающих на входы Á в момент t, а (q 1(t),..., q s(t)) - набор, задающий состояние автомата Á в тот же момент времени.

    Функция j i, i = 1,..., s, определяет значение i -й компоненты состояния автомата Á, в которое он переходит из состояния (q 1(t),..., q s(t)) под действием входного символа (x 1(t),..., x s(t)).

     

    Функция y j, j = 1,..., d, определяет значения символа на j -м выходе Á в момент t, для входного символа (x 1(t),..., x s(t)) и текущего состояния (q 1(t),..., q s(t)).

     

    Поскольку функции j i, i = 1,..., s, и y j, j = 1,..., d являются булевскими функциями, то они могут быть реализованы схемами из функциональных элементов, которые изображены на рис. 7.17.

     

    ........

     

    y1 ... y d j1 ... js

     

     

    Рис. 7.17

    Рассмотрим автоматную схему, представляющую автомат Á, которая изображена на рис. 7.18:


    x 1... x p q 1 ... q s

     

    ............

    y1 ... y d j1 ... j s ...

     

     

    Z.. Z

     

    y 1 y d Рис. 7.18

    Данная схема задает автомат, имеющий p входов и d выходов. В ней каждый из p входов, помеченных символами переменных, и s выходов элементов задержек является одним из входов схем из функциональных элементов, вычисляющих функции y1,..., yd, j1,..., js .

    В начальный момент времени Á находится в состоянии, которое представляется набором из s нулей.

    По определению функций j i и y j (i = 1,..., d, j = 1,..., s) построенная автоматная схема функционирует так же, как и автомат Â, c точностью до кодирования входных и выходных символов. То есть если на входе автомата Â появляется слово a, которое перерабатывается в выходное слово b, то автомат Á из своего начального состояния перерабатывает слово, получаемое из a заменой входящих в него символов их двоичными представлениями, в слово, получаемое из b аналогичной заменой сомволов алфавита B их двоичными представлениями.






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