Категория
Информатика
Тип
реферат
Страницы
2 стр.
Дата
21.01.2009
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
18265.zip — 71.47 kb
  • proverka-neprotivorechivosti-isxodnyx-opisanij-konechnyx-avtomatov_18265_1.rtf — 733.51 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы

Проверка непротиворечивости исходных описаний конечных автоматов
Ю.М. Вишняков
В 60-70-х годах на теорию конечных автоматов (КА), как универсал
ь ный инструментарий описания и синтеза цифровых
схем, возлаг а лись большие надежды. Однако возможности технологического базиса и и н формационные технологии того времени ограничили практическое испол ь
зование теории КА только рамками структурного синтеза. Абстрактный си н тез так и остался предметом теоретических изысканий. Сегодня в автом а тизированном проектировании происходит интенсивный переход к интегр и
рованным инструментальным средствам, осуществляющим сквозную ра з работку проектов на всех уровнях. В таких
системах наряду со стандар т ными средствами проектирования топологии и моделирования должны присутствовать и средства реализация проек т ных процедур логического синтеза. Таким образом сегодня сформиров а ны практические потребности и имеются все условия, чтобы абстрактная теория КА заняла достойное место в автоматизированном проектиров а
нии. Однако в этом плане она должна быть переработана в контексте сквозного автоматизированного проектиров а
ния.
В рамках этой цели предлагаемая работа развивает абстрактный си
н тез в части построения непротиворечивых описаний КА на языке регуля р ных выраж е
ний.
Пусть заданы входной X=X 1 ,X 2
,...,X n и выходной Y=Y 1
,Y 2 ,...,Y m а
л фавиты. КА перерабатывает входные слова (цепочки)
X* в выхо д ные Y* в соответствии с алфавитным (автоматным) оператором
=F( ) (А-оператор). Доказано, что обрабатываемые КА множества цепочек, относя т
ся к классу регулярных множеств (РМ), к о
торые задаются через правила их порождения, называемые регулярными



Ваше мнение



CAPTCHA