Конечный автомат - Большая Энциклопедия Нефти и Газа, статья, страница 1
Скромность украшает человека, нескромность - женщину. Законы Мерфи (еще...)

Конечный автомат

Cтраница 1


Конечные автоматы используются в задачах распознавания, управления и многих других приложениях. Знаменитая машина Тьюринга является разновидностью конечного автомата.  [1]

Конечные автоматы моделируют огромное количество окружающих нас устройств, систем и явлений. Простейшим из них является устройство для продажи газированной воды. Конечным автоматом являются также электронные часы. Состояниями служат наборы указателей месяца, числа, часа, минуты и секунды. Такой автомат имеет около 31 млн. состояний. Интересным примером автомата с выходами в физике является модель атома Бора.  [2]

Конечный автомат как математическая модель реального объекта требует обычно двоякого рассмотрения. С одной стороны, он выступает как алфавитный преобразователь информации, реализующий соответствующее алфавитное отображение, а с другой - как динамическая система, изменяющая свои состояния во времени под действием внешних сигналов и внутренних факторов.  [3]

Конечный автомат определяет правоинвариантное конечное отношение эквивалентности на множестве входных последовательностей. Входные последовательности, для которых соответствующие состояния одинаковы, будем считать эквивалентными. И наоборот, для заданного правоинвариантного конечного отношения эквивалентности на множестве входных последовательностей мы можем построить автомат с минимальным множеством состояний, который определяет отношение эквивалентности на множестве входных последовательностей, совпадающее с первоначальным. Каждому классу эквивалентности соответствует вполне определенное состояние автомата. Следует как-то выделить начальное состояние, для этого дополним множество входных последовательностей пустой последовательностью. Класс эквивалентности, содержащий элемент Л, соответствует начальному состоянию. Может так случиться, что этот класс содержит только пустую последовательность. Функция переходов определяется с помощью соотношения 8 ( Ы, аг) [ xat ], где Ы обозначает состояние, соответствующее классу эквивалентности, содержащему входную последовательность к. Приведем примеры отождествления различных входных последовательностей, когда состояния, не принадлежащие минимальному множеству, не учитываются.  [4]

Конечный автомат определяет конечное отношение конгруэнтности на множестве входных последовательностей. Для каждой входной последовательности автомат начинает поочередно работать из каждого начального состояния, переходя в соответствующее конечное состояние. Последовательности будут эквивалентными, если они вызывают для каждого начального состояния одинаковые переходы. Таким образом, получено отношение конгруэнтности. Множество классов эквивалентности с введенным законом композиции образует конечную полугруппу. Более удобно множество классов конгруэнтности ввести при помощи внешнего поведения автомата. Мы воспользуемся функциями типа вход-выход для того, чтобы ввести понятие эквивалентности последовательностей, а именно назовем последовательности х и у эквивалентными, если ft ( uxv) ft ( uyv) для всех fi из данного множества функций.  [5]

Конечный автомат читает входной символ при каждом такте ( время дискретно) и сразу же пишет выходной символ. Входная последовательность считывается постоянно слева направо, с той же скоростью порождается выходная последовательность.  [6]

7 Начало построения автомата для поиска подстроки hello. [7]

Конечные автоматы используются для решения задачи о том, принадлежит ли данное слово данному языку. Конечный автомат представляет собой простое устройство, описываемое текущим состоянием и функцией перехода. Функция перехода формирует новое состояние автомата по текущему состоянию и значению очередного входного символа. Некоторые состояния считаются принимающими, и если после окончания ввода автомат оказывается в принимающем состоянии, то входное слово считается принятым.  [8]

9 Начало построения автомата для поиска подстроки hello. [9]

Конечный автомат, настроенный на данный образец, можно использовать для сравнения с образцом; если автомат переходит в принимающее состояние, то это означает, что образец найден в тексте. Использование конечных автоматов очень эффективно, поскольку такой автомат обрабатывает каждый символ однократно. Поэтому поиск образца с помощью конечного автомата требует не более Т сравнений. Теперь встает задача создания конечного детерминированного автомата, отвечающего данной подстроке. Это непросто; существующие алгоритмы работают долго.  [10]

Конечный автомат можно рассматривать как машину, которая в каждый момент времени находится в некотором состоянии q e Q и читает поэлементно последовательность w символов из Е, записанную на конечной слева ленте.  [11]

Конечный автомат может находиться в одном из состояний а из конечного множества А возможных внутренних состояний.  [12]

13 Нумерация клеток клеточного автомата.| Соседние ( по определению клетки. [13]

Конечный автомат с неограниченно продолжаемой лентой называется автоматом, или машиной, Тьюринга. Тьюринг показал также, что существует универсальная машина Тьюринга, способная выполнять любые вычисления.  [14]

Конечные автоматы удобны для описания любых детерминированных систем ( не учитывающих случайные факторы), функционирующих в дискретном времени.  [15]



Страницы:      1    2    3    4