5.4. Эквивалентность конечных автоматов: теорема Мура кратко

Привет, Вы узнаете о том , что такое эквивалентность конечных автоматов, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое эквивалентность конечных автоматов, теорема мура , настоятельно рекомендую прочитать все из категории Теория конечных автоматов.

Две булевы функции F1 и F2 эквивалентны, если на всех возможных наборах входных переменных они принимают одинаковые значения. Поскольку число наборов у булевых функций конечно, то, перебрав их все, можно проверить, эквивалентны ли F1 и F2. Можно также привести F1 и F2 к совершенной нормальной форме и сравнить их представления.

Иная ситуация с конечными автоматами. Два конечных автомата эквивалентны, если реализуемые ими отображения вход-выход эквивалентны. Конечный автомат реализует отображение бесконечного множества входных последовательностей сигналов в бесконечное множество выходных последовательностей сигналов. Поэтому автоматные отображения нельзя сравнить простым перечислением их значений на всех возможных аргументах.

Конечные автоматы А = {XА, YА, QА, δА, λА} и В = {XВ, YВ, QВ, δВ, λВ} называются эквивалентными, если выполняются два условия:

а) их входные алфавиты совпадают: XА = XВ = X;

б) реализуемые ими автоматные отображения совпадают:

(χХ*) λА*(qА, χ) = λВ*(qВ, χ).

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

Прямым произведением конечных автоматов А = {X, YА, QА, δА, λА} и В = {X, YВ, QВ, δВ, λВ} с одинаковым входным алфавитом Х называется автомат А×В ={X, YА×YВ, QА×QВ, δА×В, λА×В}, где:

а) (qА QА) (qВ QВ) (xХ) δА×В ((qА, qВ) x ) = (δА(qА, x), δВ(qВ, x));

б) (qА QА) (qВ QВ) (xХ) λА×В ((qА, qВ) x ) = (λА(qА, x), λВ(qВ, x)).

Иначе говоря, конечный автомат, являющийся прямым произведением двух конечных автоматов, в качестве своих состояний имеет пары состояний исходных автоматов, выходной алфавит – множество пар выходных символов автоматов множителей, а функции выходов и переходов определены покомпонентно. Таким образом, это просто два стоящих рядом невзаимодействующих конечных автомата, синхронно работающих на одном общем входе (рис. 5.7). Прямое произведение автоматов называется также синхронной композицией.Рис. 5.7

Теорема 5.1. ( теорема мура ) Два конечных автомата А = {X, YА, QА, δА, λА} и В = {X, YВ, QВ, δВ, λВ} с одинаковым входным алфавитом Х являются эквивалентными тогда и только тогда, когда для любого достижимого состояния (qА, qВ) в их прямом произведении А×В справедливо (xХ) λА(qА, x)= = λВ(qВ, x).

Определение: Состояние qQ называется достижимым тогда и только тогда, когда (χХ*) δ* (q0, χ ) = q (то есть по воздействием какого-либо входного слова χ автомат попадает в это состояние.

Доказательство. Об этом говорит сайт https://intellect.icu . Пусть А и В эквивалентны, то есть по определению эквивалентности (χХ*) λА*(qА, χ) = λВ*(qВ, χ).

Докажем при этом предположении:

((qА, qВ) QА×QВ) достижимо (qА, qВ)  (xХ) λА(qА, x)= λВ(qВ, x).

В соответствии с определением, свойство достижимости состояния (qА, qВ) эквивалентно условию (χХ*) δ* ((q0А, q0В), χ ) =(qА, qВ). Таким образом, надо доказать, что если

(χХ*) λ* (q0А, χ ) = λ* (q0В, χ) , то

((qА, qВ) QА×QВ)[ (ξХ*) δ* ((q0А, q0В), ξ ) = (qА, qВ) 

 (xХ) λА(qА, x)= λВ(qВ, x)].

Предположим противное, то есть что

¬((qА, qВ) QА×QВ)[ (ξХ*) δ* ((q0А, q0В), ξ ) = (qА, qВ) 

 (xХ) λА(qА, x)= λВ(qВ, x)], (здесь знак ¬ перед выражением определяет инверсию) и покажем, что тогда ¬(χХ*) λА*(q0А,x) = λВ*(q0В, x).

Отрицание следствия можно преобразовать в

((qА, qВ) QА×QВ)[ (ξХ*) δ* ((q0А, q0В), ξ ) =

= (qА, qВ) & (xХ) λА(qА, x) ≠ λВ(qВ, x)].

Положим χ = ξ x. Очевидно, что

λА*(q0А, χ) = λА*(q0А, ξx = λА*(q0А ,x)^ λА(δ*(q0А, ξ) x ) = λА*(q0А, ξ)^ λА(qА, x) ≠ ≠ λВ*(q0В, ξ)^ λВ(qВ, x ) = λВ*(q0В, ξ)^ λВ(δ*(q0В, ξ)x) = λВ*(q0В, ξx) = λВ*(q0В, χ).

Отсюда:

(χХ*) λА*(q0А, χ) ≠ λВ*(q0В,χ) или ¬(χХ*) λА*(q0А, χ) = λВ*(q0В, χ),

что и требовалось доказать.

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

Пример конечного автомата Мура представлен на рис. 5.8а. Здесь выход автомата определяется однозначно тем состоянием, в которое автомат переходит после приема входного сигнала. Например, в состояние 1 можно прийти по трем переходам: из состояния 0 под воздействием входного сигнала b, из состояния 2 под воздействием b, из состояния 1 также под воздействием входа b. Во всех трех случаях выходная реакция автомата одна и та же: на выходе образуется сигнал у2. Совершенно очевидно, что по любому автомату Мура легко построить эквивалентный ему автомат Мили; так для автомата Мура (рис. 5.8а) эквивалентный ему автомат Мили изображен на рис. 5.8б.

Рис. 5.8

Справедливо и обратное: для любого автомата Мили существует эквивалентный ему автомат Мура. Справедливость этого утверждения легко доказывается конструктивно. Рассмотрим автомат Мили, представленный на рис. 5.9а. Каждое состояние автомата Мили расщепляется на несколько эквивалентных состояний, с каждым из которых связывается один выходной символ. Для нашего примера это состояния р0, p1, q0, ql, r0, rl. Построение переходов эквивалентного автомата Мура ясно из рисунка 5.9б.

Рис. 5.9

Отметим однако, что такая эквивалентность автоматов Мили и Мура не отражает их существенной разницы: выходные сигналы в автомате Мили связаны с (мгновенными) событиями переходов автомата, в то время как выходные сигналы в автомате Мура определяются при входе в его новое состояние. В примерах реальных систем, функционирование которых описывается моделью конечного автомата, обычно ясно видна разница между двумя видами выходных сигналов – импульсными сигналами, возникающими только в моменты переходов системы из одного состояния в другое, и потенциальными выходными сигналами, возникающими в момент входа в состояние и остающимися неизменными все время, пока автомат находится в текущем состоянии. В реальных системах управления часто необходимы сигналы обоих типов. Во многих применениях конечных автоматов для спецификации дискретных систем с памятью используются как выполнения функций на переходах между состояниями, так и функции входа и функции выхода, активизирующиеся соответственно в моменты входа в новое состояние и выхода из текущего состояния.

Вау!! 😲 Ты еще не читал? Это зря!

• представление конечных автоматов ,
• простейший автомат , детерминированный автомат ,
• конечные автоматы , понятие автомата ,
• понятие клеточного автомата , клеточный автомат ,
• Конечные автоматы как структуры данных - Индексируйте ключей с помощью автоматов
  
• конечные автоматы , виды конечных автоматов ,
• Автомат Мили
• Автомат Мура
• JFLAP — кроссплатформенная программа симулятор (автоматов, машины Тьюринга , грамматик)
• Автоматное программирование
• Sequential Function Chart
• Компилятор
• Транслятор
• Сети Петри
• Секвенциальная логика (Последовательностная логика )
• Таблица принятия решений
• Суффиксный автомат

Анализ данных, представленных в статье про эквивалентность конечных автоматов, подтверждает эффективность применения современных технологий для обеспечения инновационного развития и улучшения качества жизни в различных сферах. Надеюсь, что теперь ты понял что такое эквивалентность конечных автоматов, теорема мура и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Теория конечных автоматов