PARALLEL.RU

Помогите пожалуйста с алгоритмом (словесно или пример) эквивалентности СТРУКТУРНЫХ автоматов Мура. Заданы два структурных автомата Мура, нужно определить эквивалентны они или нет...

Посмотрите книгу:
Айзерман М.А., Гусев Л.А., Розоноэр Л.И., Смирнова И.М., Таль А.А. Логика. Автоматы. Алгоритмы М.: Физматгиз, 1963. – 556 с.
В ней целая глава - "Эквивалентность и минимизация последовательностных машин". Может, и найдете то, что Вам нужно. Только, думаю, нужно будет Ваши структурные автоматы привести к абстрактным.

_________________
Лучшее - враг хорошего?

Такое возможно привести структурные к абстрактным?
Вообще тема называется Определение эквивалентности структурных автоматов Мура. Считать их эквивалентными если они могут быть получены из одной ГСА.
Я получил два разных структурных автомата, теперь надо определеить эквивалентны они или нет...

Переименуйте структурные алфавиты (входной/выходной) обычными буквами и получите абстрактный.

Это Вы из одной ГСА получили два разных автомата? Если так, то они в этом случае эквивалентны (поскольку обратным преобразованием они приводятся к одной модели - ГСА, что и есть доказательство их эквивалентности).
Но здесь Вам, наверное, лучше почитать С.Баранова. Синтез микропрограммных автоматов. Там он как раз и выполняет взаимные преобразования ГСА в КА и обратно. Смотрели?

_________________
Лучшее - враг хорошего?

Сам преподаватель советовал эту книгу...Но ее нигде в городе нет. В инете электронных вариантов тоже нет. А курсовой уже в пятницу сдавать.

Сложно Вам чем-то помочь Но преподаватель должен был бы дать по идее нужный материал. Можно, конечно, отсканировать (у меня она есть). Но... нужно знать, что конкретно. Насколько я помню все это привязано к минимизации автоматов и достаточно разбросано по книге. А если еще нужно и описание преобразований ГСА в КА и обратно, то объем еще увеличится
В Инете на ALib.ru ее продают за 400 руб., но ... до пятницы Вам не успеть

_________________
Лучшее - враг хорошего?

Мне очень помогло преобразование КА в ГСА. Можно даже словестно.

Посмотрите статью:
Любченко В.С. Искусство программирования … RS-триггера?! Часть 1. Электронная схема и формальные модели. http://www.softcraft.ru/auto/ka/rsm/rsm01.shtml. Особенно на в ней на рис.4 - автоматные графы и на рис. - ГСА автоматов на рис.4. Думаю, догадаться можно. Подробно же расписывать - долго
Хорошо бы Вам поискать еще одну книгу - Э.Хамби. Программирование таблиц решений. Нужно только учитывать, что одна ТР - это одно состояние автомата. Как преобразовать одну ТР и блок-схему в ней есть.

_________________
Лучшее - враг хорошего?

Наверное я уже надоел:) Завтра все закончится. Появился еще один вопрос. Есть ГСА, преобразую ее в автомат. Из автомата получаю другую ГСА. Ее снова преобразую в автомат. Минимизурую таблицы переходов этих автоматов.
1. Они должны получиться одинаковыми?
2. Если они получатся одинаковыми, можно ли проверять эквивалентность таким способом (минимизацией таблиц переходов)?

Я бы предпочел, чтобы продолжилось В смысле, чтобы у Вас остался интерес к автоматам. Поверьте, у автоматов было, есть и будет большое будущее. Тогда это будет только начало. А я в этом случае буду считать, что время потрачено не даром

Не обязательно. Минимальный автомат у некоторого автомата может быть не один.

В результате таких преобразований автоматы могут получиться и разными, но поскольку последний автомат получен путем эквивалентных преобразований, то эти автоматы эквивалентны по определению Хотя, как я уже сказал, если мы из двух внешне разных автоматов получим одну ГСА, то смею утверждать, что такие автоматы эквивалентны. Хотя, если честно, о таком доказательстве я не слышал Просто рассуждаю логически. Если какие-то две модели сводятся к одной путем эквивалентных преобразований, то эти исходные модели эквивалентны.
Да. Минимизация не есть проверка на эквивалентность. Хотя, конечно, все минимальные автоматы некоторого автомата эквивалентны. Речь, наверное, должна идти о минимальных автоматах разных автоматов, проверяемых на эквивалентность. Хотя эвивалентность минимальных автоматов, думаю, легче доказывать. Просто меньше объем работы .

_________________
Лучшее - враг хорошего?

Огромное спасибо...За курсовой я получил отлично...

Пока я не увидел практического применения автоматов, поэтому они особый интерес не вызывают...У меня в следующем семестре будет предмет ТЯП, вроде он тесно связан с автоматами...может там он (интерес) и проснется...

а где практически автоматы применяются???

Да везде - от проектирования "железа", до программирования; от последовательного программирования, до параллельного...
Вам, наверное, их плохо дают, так сказать, на уровне ТЯП-ЛЯП , если у Вас такое представление о них
См. для примера сайты:
1) SWITCH-технология - http://is.ifmo.ru/
2) КА-технология - http://www.softcraft.ru/forum/viewforum ... efd927be3d

_________________
Лучшее - враг хорошего?

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

Не думаю, что этот вариант ... Так обычно дают, т.к. в програмировании автоматы достаточно специализированны. Стандартно - теория и проектирование компиляторов. Но ситуация меняется (правда, как я считаю, медлено). Тот же - UML. Там все фактически на автоматах. Это-то есть последний "писк". Какие автоматы и какой "писк" - другой вопрос. Но уж c UML-то по идее Вас должны бы знакомить, если Ваши преподаватели отслеживают современные тенденции в программировании?

_________________
Лучшее - враг хорошего?