Проверка непротиворечивости исходных описаний конечных автоматов
    Ю.М. Вишняков
    В 60-70-х годах на теорию конечных автоматов (КА), как универсальный инструментарий описания и синтеза цифровых схем, возлагались большие надежды. Однако возможности технологического базиса и информационные технологии того времени ограничили практическое использование теории КА только рамками структурного синтеза. Абстрактный синтез так и остался предметом теоретических изысканий. Сегодня в автоматизированном проектировании происходит интенсивный переход к интегрированным инструментальным средствам, осуществляющим сквозную разработку проектов на всех уровнях. В таких системах наряду со стандартными средствами проектирования топологии и моделирования должны присутствовать и средства реализация проектных процедур логического синтеза. Таким образом сегодня сформированы практические потребности и имеются все условия, чтобы абстрактная теория КА заняла достойное место в автоматизированном проектировании. Однако в этом плане она должна быть переработана в контексте сквозного автоматизированного проектирования.
    В рамках этой цели предлагаемая работа развивает абстрактный синтез в части построения непротиворечивых описаний КА на языке регулярных выражений.
    Пусть заданы входной X={X1,X2,...,Xn} и выходной Y={Y1,Y2,...,Ym} алфавиты. КА перерабатывает входные слова (цепочки) ??X* в выходные ??Y* в соответствии с алфавитным (автоматным) оператором ?=F(?) (А-оператор). Доказано, что обрабатываемые КА множества цепочек, относятся к классу регулярных множеств (РМ), которые задаются через правила их порождения, называемые регулярными выражениями (РВ) [1].
    В алгебре РВ по определению ?, ? (пустая цепочка), X1, X2, ..., Xn являются элементарными РВ. Если e1, e2, e - РВ, то результаты операций e1*e2 - (конкатенации), e1|e2 (ИЛИ), {e} (Клини), (e) (круглые скобки) также являются РВ. Также отметим, что порождаемое множество цепочек или язык РВ e обозначают через |e|.
    Представим А-оператор через систему РВ (СРВ). Для этого выделим в X* подмножества регулярных цепочек E1, E2, ..., Em (в общем случае бесконечных) таким образом, чтобы цепочка ??E1 приводила к появлению на выходе КА буквы Y1, ??E2 - буквы Y2, ??Em -.Ym. Для случая ??X*\(E1E2...Em) определим дополнительную букву Ym+1. Также введем условие непротиворечивости EiEj= (i,j=1..m, i?j). Представим каждое множество Ei порождающим его регулярным выражением (РВ) ei (|ei|= Ei). Тогда представляющая КА система соотношений вида (1) и называется СРВ:
    (1)
    
    Поскольку взаимно однозначное соответствие между языком и порождающим его РВ отсутствует (например, РВ а{a} и {a}a порождают различными способами один и тот же язык), построение непротиворечивой CРВ требует далеко нетривиальных действий. И в этой связи можно предположить, что средства исследования непротиворечивости СРВ нужно искать вне алгебры РВ.
    Ближайшей моделью к РВ, которой может быть промоделирован разбор цепочек, является система переходов (СП), дуги которой взвешены буквами входного алфавита. КА с выходным алфавитом Y={0,1}, распознающий язык |e|, называют конечным распознавателем (КР). Представление КР в виде диаграммы состояний (рис.1), в которой начальная вершина S и конечная вершина Z связаны дугой e называется системой переходов (СП). ............