Лекция
Привет, Вы узнаете о том , что такое конечные автоматы, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое конечные автоматы, понятие автомата , настоятельно рекомендую прочитать все из категории Теория конечных автоматов.
Окружающие нас преобразователи информации не всегда выполняют чисто функциональное отображение информации. Результат преобразования вход выход зачастую зависит не только от того, какая информация в данный момент появилась на входе, но и от того, что происходило раньше, от предыстории преобразования. Множество примеров тому дают биологические системы. Например, один и тот же вход – извинение соседа после того, как он наступил вам на ногу в переполненном трамвае – вызовет у вас одну реакцию в первый раз и совсем другую в пятый раз. По-видимому, ваша реакция будет зависеть от предыдущих событий, произошедших в трамвае, иными словами, от входной истории.
Таким образом, существуют более сложные, не функциональные преобразователи информации; их реакция зависит не только от входа в данный момент, но и от того, что было на входе раньше, от входной истории. Такие преобразователи называютсяавтоматными.
Если число различных элементов входной информации у данного преобразователя есть конечное число (как и в конечном функциональном преобразователе), то и число возможных входных историй конечно (счетно). Если автомат по-разному будет себя вести для каждой возможной предыстории, то такой автомат должен иметь память, чтобы все эти предыстории запоминать. Соответствующая формальная модель и называется конечным автоматным преобразователем информации, или просто конечным автоматом.
Введем на множестве предыстории отношение эквивалентности. Две предыстории будем считать эквивалентными, если они одинаковым образом влияют на дальнейшее поведение автомата. Очевидно, что для своего функционирования автомат не обязательно должен запоминать входные истории, достаточно, чтобы он запоминал только класс эквивалентности (например, его номер), к которому принадлежит данная история. Класс эквивалентности его входных историй назовем внутренним состоянием автомата.
В своих внутренних состояниях автомат запоминает свое «концентрированное прошлое». Неформально состояние системы – это характеристика, однозначно определяющая ее дальнейшее поведение, все последующие реакции системы на внешние события. На один и тот же входной сигнал конечный автомат может реагировать по-разному в зависимости от того, в каком состоянии он находится в данный момент. Поскольку состояние представляет собой класс эквивалентных предысторий входов, состояние может измениться только при приходе очередного входного сигнала. При получении входного сигнала конечный автомат не только выдает информацию на выход как функцию этого входного сигнала и текущего состояния, но и меняет свое состояние, поскольку входной сигнал изменяет предысторию. Исходя из понятия формальных грамматик, будем считать, что входные и выходные переменные, а также внутренние состояния конечного автомата принимают значения из некоторых конечных алфавитов. Об этом говорит сайт https://intellect.icu . Пусть X – алфавит входной переменной xi, Y – алфавит выходной переменной yi, а Q – алфавит, определяющий внутренние состояния автомата qi.
Рис. 5.1
Функционирование автомата удобно представлять графически в виде блок-схемы. При этом структура конечного автомата в общем случае имеет вид некоторого многополюсника – «черного ящика» (рис. 5.1а) – с множеством МX входных векторов и множеством МY выходных векторов. Множество внутренних состояний МQ характеризуется памятью, запоминающей входную последовательность (предыстории) автомата. Укрупненная внутренняя структура конечного автомата изображена на рис. 5.1б. Здесь МZ- – множество векторов, характеризующих входные каналы обратной связи (памяти); МZ+ – множество векторов, характеризующих выходные каналы обратной связи (памяти). При этом каждое внутреннее состояние автомата qiхарактеризуется определенной совокупностью входов xi и z+i. Число внутренних состояний автомата называется объемом памяти автомата.
Рассматриваемые в курсе модели конечных автоматов являются абстрактными описаниями систем управления техническими автоматизированными устройствами или вычислительных процессов. В основе этих моделей лежит предположение о том, что эти автоматы работают дискретным образом, т.е. входные и выходные переменные, а также внутренние состояния не являются непрерывными функциями во времени, а изменяются в фиксированные моменты τv (v = 1,2,…). Предполагается, что конечный автомат может иметь только одно из конечного множества внутренних состояний qi. Это состояние остается неизменным в интервале времени между τv и τv+1, который далее будем называть тактом автоматного цикла. Продолжительность такта не обязательно является постоянной величиной, а переход автомата из одного внутреннего состояния в другое зависит только от порядкового номера такта vi. При этом состояние конечного автомата в любой тактовый момент τv характеризуется совокупностью входных переменных на данный тактовый момент и внутренним состоянием автомата в предшествующий тактовый момент τv-1.
Рассмотрев основные понятия и термины, можно дать точное определение конечного автомата. Конечным автоматом называетсяупорядоченная пятерка объектов А = {X, Y, Q, δ, λ}, где:
X – конечное непустое множество входных сигналов (входной алфавит);
Y – конечное непустое множество выходных сигналов (выходной алфавит);
Q – конечное непустое множество внутренних состояний;
δ – функция переходов (отображение Q × X →Q);
λ – функция выходов (отображение Q × X →Y).
Таким образом, в определении автомата участвуют три конечных множества X, Y, Q и две функции δ и λ, задающие некоторые отношения между элементами этих множеств.
Мощности множествX, Y, Q равны соответственно:
|X| = 
pi ; |Y| = 
ri ; |Q| = 
si ,
где pi , ri и si – количество символов в алфавитах входной переменной xi , выходной переменной yi и переменной состояния qi. При двоичной структуре всех алфавитов – |X| = 2n , |Y| = 2m , |Q| = 2k.
Для автомата А его функции δА и λА могут быть определены не только на множестве X всех символов входного алфавита (букв), но и на множестве X* всех входных наборов букв – слов. Для любого входного слова (χ = x1 x2 x3… xk) X* и любой буквы xj
δ(qi , χ xj) = δ(δ(qi , χ), xj ).
С помощью расширенной функции Ψ индуктивно определяется расширенная функция выходов λ:
λ(qi , χ xj) = λ(δ(qi , χ), xj ).
Поставим в соответствие каждому входному слову χ = x1 x2 x3… xk слово γ в выходном алфавите:
γ = λ(q1 , x1) λ(q1 , x1 x2) λ(q1 , x1 x2 x3)… λ(qi , x1… xk).
Это соответствие, отображающее входные слова в выходные слова, называется автоматным отображением, а также автоматным оператором, реализуемым автоматом (А, q1). Если результатом применения оператора к слову χ является выходное слово γ, то это обозначается А(χ) = γ. Число букв в слове χ называется длиной и обозначается |χ|.
Анализ данных, представленных в статье про конечные автоматы, подтверждает эффективность применения современных технологий для обеспечения инновационного развития и улучшения качества жизни в различных сферах. Надеюсь, что теперь ты понял что такое конечные автоматы, понятие автомата и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Теория конечных автоматов
Из статьи мы узнали кратко, но содержательно про конечные автоматы
Комментарии
Оставить комментарий
Теория конечных автоматов
Термины: Теория конечных автоматов