Упражнение. 1. Показать, что автоматы Á1 и Á2 эквивалентны тогда и только тогда, когда множества функций

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

 

2. Показать, что всякий автомат эквивалентен самому себе.

 

ОПРЕДЕЛЕНИЕ

Автомат, все состояния которого являются отличимыми, называется минимальным автоматом.

 

Пусть Á = (A, B, Q, j, y) - некоторый автомат.

Обозначим как j* функцию j*: A* Q Q, которая для любого входного слова и состояния qi принимает значение, равное состоянию Á после переработки из начального состояния qi.

Эта функция может быть определена следующими соотношениями:

1) " a ÎA (j*(a, qi) = j(a, qi));

2) " ÎA*, a ÎA (j* ( a, qi) = j(a, j*( , qi))).

 

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

Функция может быть задана соотношениями:

1) "a ÎA ( (a) = y(a, qi));

2) " ÎA*, a ÎA( ( a)= ( ) y(a, j*( ,qi)).






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


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

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

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

Если вам понравился данный ресурс вы можете рассказать о нем друзьям. Сделать это можно через соц. кнопки выше.
helpiks.org - Хелпикс.Орг - 2014-2017 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.004 сек.