Эквивалентность автоматов-распознавателей




Первый шаг в изложении теории минимизации – понятие эквивалентности состояний.

Два автомата-распознавателя следует считать эквивалентными, если они распознают один и тот же язык.

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

Справедливость этой теоремы легко доказывается с помощью построения их синхронной композиции и ее анализа. Продемонстрируем это на следующем примере. Пусть два конечных автомата-распознавателя имеют один входной алфавит X, т.е.:

и

Тогда прямым (декартовым) произведением этих автоматов называется следующий автомат:

Рис. - Общая структура синхронной композиции двух конечных автоматов

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

Ни одна цепочка над алфавитом Х, распознаваемая автоматом , не распознается автоматом и наоборот, что означает, что языки и в этом примере не пересекаются: .

Финальное состояние – те состояния, в которых обе компоненты являются одновременно финальными.

Пример. Дано:

Алфавит

Автоматы и работают синхронно под воздействием одних и тех же входных сигналов Х.

Рис. - Граф переходов автомата-распознавателя

 

Рис. - Граф переходов автомата-распознавателя

 

 

Рис. – Синхронная композиция, граф переходов автомата-распознавателя

 

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

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

 

 

Пример. Дано:

Алфавит

Формальный язык

Формальный язык

 

Графы состояний для каждого автомата-распознавателя следующие:

 







Дата добавления: 2020-12-11; просмотров: 82; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2021 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.009 сек.