Содержание к диссертации
Введение
1 Анализ логических конструкций формальных языков 9
1.1 Исследование алгоритмов формирования многомодульных программ..9
1.2 Языки и регулярные языки 11
1.2.1 Алфавиты и языки 12
1.2.2 Регулярные выражения 15
1.3 Автомате конечным числом состояний 18
1.3.1 Проектирование автомата с конечным числом состояний 18
1.3.2 Гипотеза отождествления 24
1.3.3 Префиксное замыкание 31
1.4 Просто звёздные языки 33
1.4.1 Ограничения размера языка 33
1.4.2 Однобуквенный автомат 35
1.4.3 Условия полиномиального роста 37
1.5. Исчисление предикатов и регулярные языки 39
1.5.1 Регулярные предикаты 39
1.5.2 Языки со многими переменными 41
1.5.3 Исчисление и замкнутость предикатов 43
Цель и задачи исследования 45
2 Применение алгебраической теории групп к разработке синтаксиса и семантики формальных языков 46
2.1 Группы, как языки 46
2.1.1 Структура автоматов для групп 46
2.1.2 Построение алгоритма для решения проблемы слов 51
2.2 Графы Кэли и изометрические неравенства 54
2.2.1 Превращение графа Кэли в метрическое пространство 58
2.2.2 Ограничение длин 63
2.3. Группы автоматов 66
2.3.1 Свойство Липшица для групп автоматов 66
2.3.2 Стандартные автоматы 69
2.3.3 Ограничение длин 72
2.4. Инвариантность при замене образующих 76
2.4.1 Изменение образующих 77
2.4.2 Улучшение автоматической структуры 80
2.4.3 Биавтоматичность 83
2.4.4 Префиксное замыкание групп автоматов 85
3 Применение комбинаторной топологии к исследованию лексической структуры формального языка 88
3.1 Квазигеодезические, псевдоизометрия, поочередная комбинация 88
3.2 Метрические пространства, метрики путей и геодезические 89
3.3 Кратчайшие строки 92
3.3.1 Множества конического типа 92
3.3.2 Нахождение уровня элемента группы 98
3.3.3 Применение теории Люстерника - Шнирельмана к множествам конического типа 100
3.4 Псевдоизометрии 107
3.4.1 Псевдоотображения 108
3.4.2 Равносильность группы и действующего пространства 112
3.4.3 Оценки числа стационарных точек 114
Выводы 121
4 Определение оценки сложности символьного текста в терминах тополо гических инвариантов 122
4.1 Приложение результатов теоретического исследования к решению задач лексического анализа 122
4.2 Взаимодействие основных фаз транслятора 123
4.3 Применение метода категорного анализа к процедуре идентификации символов входного потока 125
Выводы 127
Заключение 129
Список литературы 131
- Проектирование автомата с конечным числом состояний
- Графы Кэли и изометрические неравенства
- Метрические пространства, метрики путей и геодезические
- Применение метода категорного анализа к процедуре идентификации символов входного потока
Введение к работе
Актуальность темы. В современных условиях информатизации общества - интенсивного развития современных информационных технологий и средств телекоммуникаций создание новых, совершенствование существующих языков программирования, а также соответствующих инструментальных средств является одной из особенно важных и актуальных.
Современный информационный рынок характеризуется быстрым появлением новых микропроцессоров и микроконтроллеров. Ожидать предоставления аппаратного прототипа перед началом разработки программного обеспечения в настоящее время означает рисковать своим проектом. Ликвидировать постоянное отставание процессов создания программного обеспечения от появления технических средств позволяет одновременная разработка программного и аппаратного обеспечения, что в результате приводит к повышению эффективности проектных работ и ускорению выхода нового изделия на рынок.
Потребность в мощных, гибких и надежных языковых инструментах, адекватных предельному уровню сложности и ответственности задач, решаемых программным обеспечением, определяет высокую активность исследований и разработок в данной области. Языки системного программирования, на которых создаются операционные системы, трансляторы и другие программы, развиваются в направлении повышения их уровня и независимости от ЭВМ. Машинная независимость достигается использованием стандарта языка, поддерживаемого всеми разработчиками трансляторов, эффективности и адекватности которых уделяется особенное внимание. С другой стороны, недоступность оригинальных средств разработки программного обеспечения для новых микропроцессоров и микроконтроллеров требует глубоких научных исследований различных теорий и создания новых методов и технологий компиляции. В связи с этим, проблема понимания между программистом и ЭВМ была и остаётся особенно акту альной. Использование языков высокого и сверх высокого уровней при создании больших программных комплексов не гарантирует от ошибок даже в тех случаях, когда отдельные модули программ, взятые порознь, тщательно оттестированы и не содержат ошибок
Сложность рассматриваемой проблемы приводит к необходимости развития исследований в области математической теории программирования в направлении разработки и внедрения новых методов синтаксиса и семантики языков программирования и их оптимизации. Корректная постановка соответствующих задач требует глубокого изучения содержания понятия «формальный язык». Специфика проектируемых объектов определяет особенности разработки алгоритмов, в основе которых лежит синтез современных результатов теории автоматов и семантического решения различного рода алгоритмических задач. Этим определяется актуальность рассматриваемой тематики.
Цель и задачи исследования. Целью диссертационной работы является повышение эффективности процедур лексического анализа в процессе трансляции программ за счёт применения теории конических типов при формализации конечных автоматов и направленную на разработку компиляторов новых языков программирования.
Для достижения поставленной цели необходимо решить следующие задачи:
1. Провести анализ логических конструкций формальных языков программирования и применить полученное обоснование для анализа синтаксиса и семантики этих конструкций.
2. Исследовать возможность применения алгебраической теории групп к разработке синтаксиса и семантики формальных языков программирования.
3. Применить комбинаторную топологию к исследованию лексической структуры формального языка.
4. Получить оценку сложности символьного текста программ на языках высокого и сверхвысокого уровней в терминах топологических инвариантов.
Методы исследования. В ходе исследования использовались теория формальных языков программирования, теория синтаксического анализа перевода и компиляции, теория алгоритмов, теория автоматов, теория графов, элементы алгебраической и комбинаторной топологии, вычислительной геометрии и гиперболических многообразий.
Научная новизна. В диссертационной работе получены следующие результаты, характеризующиеся научной новизной:
- метод категорного анализа, позволяющий повысить эффективность процедур лексического анализа в сканерах входного потока, основанный на применении теории конических типов для вычисления уровня элемента группы;
- процедура, позволяющая устанавливать формальное соответствие между автоматическими группами и квазигеодезическими, основанная на использовании топологических свойств квазигеодезических и позволяющая применить методы комбинаторной топологии к лексическому анализу;
- метод определения автоматичности формальной системы, отличающийся использованием свойств близости геодезических в метрике Ха-усдорфа, и позволяющий устанавливать применимость категорных методов к анализу формальных языков программирования;
- алгоритм вычисления количества стационарных точек для функций, заданных на конечных автоматах, отличающийся использованием структурных характеристик автоматов и позволяющий оценивать семантическую сложность символьного текста при работе компилирующих программ.
Практическая значимость и результаты внедрения: основные теоретические и практические результаты работы внедрены и используются в производственном процессе ФГУП ВНИИС при разработки высокоэффек тивных инструментальных средств программирования специального назначения, в учебный процесс Воронежского государственного технического университета для студентов специальности 230201 «Информационные системы».
Апробация работы. Результаты диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: Международном семинаре «Компьютерное моделирование электромагнитных процессов в физических, химических и технических системах» (Воронеж, 2004), Международном семинаре «Физико-математическое моделирование систем» (Воронеж, 2004), Всероссийской конференции «Интеллектуализация управления в социальных и экономических системах» (Воронеж, 2004).
Публикации. Основное содержание диссертационной работы изложено в 10 печатных работах. В работах, опубликованных в соавторстве, лично соискателю принадлежат: разработка математической модели поиска гомоморфизмов и изоморфизмов между группами при разработки синтаксиса и семантики формальных языков, оценка семантической сложности входного потока в процессе функционирования транслятора, возможность применения теорий категорий к множеству конического типа для повышения эффективности процедур лексического анализа.
Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения, изложенных на 140 страницах машинописного текста, списка литературы из 84 наименований, содержит 40 рисунков.
Проектирование автомата с конечным числом состояний
Этот пункт посвящен лингвистической формализации процессов проектирования. Естественно классифицировать языки в соответствии с типом машин, способных узнавать их. Автомат с конечным числом состояний является особенно простым типом машин и оказывается, что язык является регулярным в том и только в том случае, если он узнаваем некоторым автоматом с конечным числом состояний.
Проектирование автомата с конечным числом состояний Автомат с конечным числом состояний —это пятерка (S,A,]u,Y,So), где S — конечное множество, называемое множеством состояний, А — конечное множество, называемое алфавитом, ц. — отображение S A—»S — это функция, называемая функцией перехода (перемещения), Y — это (возможно пустое) подмножество от S, называемое подмножеством допустимых состояний, s0eS — называется начальным или стартовым состоянием. В дальнейшем, говоря об автомате с конечным числом состояний над А мы будем опускать ц. и писать Sx вместо JLI(SX).
Часто в литературе, допустимое состояние также называют успешным состоянием или конечным состоянием. Название Y для множества допустимых состояний означает «Да». Идея заключается в том, что машина начинает с начального состояния So и читает ленту, на которой напечатана строка от А. Лента читается по буквам. После считывания буквы, состояние машины изменяется в соответствии с существующим состоянием прочитанной буквы и с функцией перехода ц. Затем лента передвигается на одну букву влево, то есть головка сдвигается на одну букву вправо по ленте. Если после употребления всех вводимых данных, состояние машины находится в Y, тогда машина отвечает «Да». В противном случае она отвечает «Нет». Более формально, эту идею можно сформулировать в следующем определении: Пусть M=(S,A,JI,Y,S0),— автомат с конечным числом состояний.
Пусть Map (S,S) — это полугруппа, состоящая из отображений из S в S. Отображение A—»Map(S,S), задаваемое с помощью ц может быть расширено единственным образом до полугруппового гомоморфизма А — Мар (S,S). Принято считать, что строка со узнаваема или допустима с помощью М, если соответствующий элемент из Map(S,S) переводит So— Y. Язык строк, узнаваемых с помощью М, будем называть языком, узнаваемым с помощью М, и будем обозначать через L (М).
Довольно часто, автомат с конечным числом состояний представляют как ориентированный граф с узлом для каждого состояния и со стрелкой для каждого перехода, (то есть в виде каждой пары состояний и букв).
Рисунок 1.2 показывает дополнительные соглашения, используемые при рисовании автомата с конечным числом состояний
Следующие рисунки показывают два примера использования конечного автомата. Рисунок 1.3. Плюс 1 по модулю 3 На рисунке 1.3 приводится детерминированный автомат (определение которого будет приведено ниже) с конечным числом состояний над алфавитом, состоящий из двух символов (1) и (+). Пустая строка представляет ноль и является допустимой. Кроме того, строка вида 1 + 1+.. . + 1 является допустимой, если только строка представляет ноль по модулю три. Все остальные строки являются недопустимыми.
Пусть х и у являются образующими двух групп Gx и Gy порядка два. На рисунке 1.3 изображен конечный автомат, который допускает именно те строки над {х,у}, которые редуцированы в свободном произведении Gx Gy (то есть, которые не имеют двух «х» или двух «у» в ряду).
Конечные автоматы имеют важное применение в текстовых процессорах и компиляторах. Их скорость в качестве компьютерного устройства в первую очередь зависит от того факта, что передаточная функция может быть реализована, как массив или таблица поиска. Если дан конечный автомат, то иногда можно его упростить, не меняя языка, который он узнает. Можно убрать все недостижимые (недопустимые) состояния автомата, те которые не могут быть достижимы из начального состояния.
Обычно, при конструировании конечного автомата, как правило, убирают недостижимое состояние и соединяют недостижимые состояния в одно "состояние неудач". Автомат, к которому применяется такое соглашение, называют нормализованным.
В литературе встречаются разные варианты определения конечного автомата. Приведем наиболее часто встречающиеся. Довольно часто тип описанной выше машины называют детерминированным конечным автоматом, для того, чтобы отличить его от других конечных автоматов. В дальнейшем, понятия "конечный автомат" и "детерминированный автомат будем считать равнозначными".
В любом случае. Дано конечное множество S, называемое . множеством состояний. Стрелкой называется тройка (sbx,S2), где Sj и S2 являются элементами множества S, а х является элементом некоторого другого множества и называется ярлыком. Sj называется источником стрелки, a S2 называется целью стрелки. Стрелка с ярлыком х иногда называется х - переходом.
Графы Кэли и изометрические неравенства
Если дана группа G, такая что А является множеством групповых образующих для G, то мы распространим отображение р до АиА"\ полагая p(i(x))=(p(x))" , и таким образом мы получим групповой гомоморфизм 7i:F(A)—»G. Если ядро этого гомоморфизма является наименьшей нормальной подгруппой из F(A), содержащей R, то мы скажем, что R является множеством отношений для G. И что А и R вместе образуют групповое представление для G; это обозначается так G= A/R .
Проблема слов в G состоит в нахождении алгоритма, который имеет на входе слово со над А и отвечает «Да» или «Нет», в зависимости от того представляет ли со тождественный элемент в G или нет.
Пусть G является конечно-представленной группой с полугрупповыми образующими А. Предположим, что G является регулярно - образованной, что означает существование регулярного языка L над А, такого, что отображение 7c:L— G является съюрективным, и такого, что обратный образ Lo в L тождественного элемента под действием п тоже является регулярным языком. Тогда проблема слов в G разрешима.
Рассмотренные утверждения остаются справедливыми при более слабом предположении, что G имеет представление с рекурсивно перечислимым множеством отношений, что L является рекурсивно перечислимым языком, и что L0 является рекурсивным языком. Интуитивно рекурсивное множество -это такое множество, для которого принадлежность элемента может быть проверена алгоритмически. Рекурсивно перечисленное множествб - это такое множество, элементы которого могут быть перечислены алгоритмически;
Это более слабое условие так как, в общем, нет способа узнать принад I лежит ли объект, который еще не возник в перечислении этому множеству или нет. Причина того, что мы устанавливаем результаты для регулируемых языков, заключается в том, чтобы определить промежуточное звено между общими группами и группами автоматов.
Пусть дано слово со над А. Мы хотим проверить, совпадает ли cc/eG с тождественным элементом или нет. Пусть F(A) - это свободная группа над А и пусть К является ядром отображения F(A)-»G, то есть множеством редуцированных слов, представляющих тождественный элемент из G. Так как, группа является конечно - представленной, то К является рекурсивно — перечисленным. Сокращая элементы из Ксо путем вычеркивания обратных, мы получим полный обратный образ X элемента а/ из F(A). Это значит, что мы можем перечислить множество всех слов Y над А представляющих со7 путем введения в слова, являющихся элементами X, зачеркнутых пар из образующих и их обращений. Так как пересечение двух рекурсивно перечисленных множеств является рекурсивно - перечисленным, мы можем рекурсивно перечислить множество YflL которое состоит из всех элементов L переходящих при отображении в со7. По предположению это множество не является пустым, поэтому наш расчет даст такой элемент в L. Затем мы! проверим, принадлежит ли этот элемент L0 или нет.
Пусть G является конечно-представленной группой с полугрупповыми образующими А. Пусть L является регулярным языком над А и пусть ото-бражение 7t:L-»G является съюрективным и конечно однозначным. Тогда проблема слов G разрешима. Эти два результата показывают обычную двусмысленность в утверждениях неситуационной математики. Сказать, что некоторый объект существует, еще не означает, что мы знаем, как сконструировать этот объект. Например, имеется алгоритм, говорящий «Да» либо алгоритм говорящий «Нет». (Если бы гипотеза Римана была бы независима от теорий множеств, это бы не произошло, но имеет смысл поверить что гипотеза Римана или ее отрицания могут быть выведены из аксиом теорий множеств). Уже известно, как построить алгоритм в случае, когда L и Lo даны конструктивно (например, путем такого задания конечного автомата). Мы знаем, как использовать знания, что L0 является конечным если Lo задано конструктивно.
Алгоритм для проблемы слов, полученный здесь является ужасно длинным и поэтому он не практичен. Далее мы покажем, как получить быстрый алгоритм для решения проблемы слов, который действует, когда группа является группой автоматов.
Группа может быть группой автоматов, по отношению к одному языку и в тоже время только регулярно образованной по отношению к другому языку (см. рис 3.2). Проблема слов может быть быстро разрешима, если использовать первую структуру, и только медленно разрешима, если использовать вторую структуру. Такая группа может быть регулярно образованной по отношению к некоторому языку, но не являться группой автоматов, по отношению к любому языку.
На рисунке 2.2 изображён автомат, который допускает язык XX vx((Xx)vx), где х является образующей группой Z целых чисел и X является его обращением. С этим языком Z регулярно-образована, но не является группой автоматов.
Выбор множества групповых или полугрупповых образующих А для группы G даёт понятие расстояния в G, где два различных элемента находятся на расстоянии единица, если они могут быть получены один из другого правым умножением на образующую. Объединяя такие соседние элементы, мы получаем так называемый «граф Кэли» для G.
Метрические пространства, метрики путей и геодезические
В частности, зная некоторое слово е, представляющее тождественный элемент, мы можем решить проблему слов за квадратичное время путем нахождения представления в L для нужного слова и подавая его, а также и е на «распознаватель равенства слов».
Предположим, что множительные автоматы Мх для хєА нормализованы. Предположим, что нам задана допустимая и и образующая х, и мы хотим найти допустимое представление v для их. Идея состоит в том, что Мх допускает некоторую пару (u, v), где и =и возможно продолжено некоторым числом из $, a v; - это допустимое слово, представляющее их, которое тоже, возможно, продолжено с помощью $. Если мы проигнорируем второй элемент его меток, то Мх становится не детерминированным автоматом с одной переменной, допускающим u. Найдем путь из стрелок, соответствующий і/ и прочтем v, обращая внимание на второй элемент меток на этом пути стрелок.
Более точно, пусть So - это множество, единственный элемент которого это начальное состояние S0 для Мх. Для i 0 мы индуктивно определим Т,, как множество стрелок с началом в SH и меткой в виде (Xj, уО , где у;єАи{$} произвольный, a Xj равно либо і - му символу в и (если і со) либо $ (если i u). Также определим Sj, как множество концов стрелок в Tj. Пусть п будет наименьшим числом таким, что n u и Sn включает допустимые состояния из Мх. Идя в обратном направлении прочтем метки уп, .... у і на пути из стрелок, которые соединяют начальное состояние с допустимым состоянием и образуем строку v=yi, ..., Уп представляющую их. Наконец чтобы получить v сбросим запаздывающие $. Так как имеется только конечное число стрелок и состояний, то время затрачиваемое на каждый шаг в этой индукции ограничено постоянной. Поэтому общее время пропорционально числу п, определенному выше, п может только превосходить и на ограниченное число N, потому что оно не будет минимальным.
Это показывает что если дана допустимая строка и, то можно найти представление для ііх за время порядка (и), и длина представления меньше или равна u+N. Заменяя (Xj, уі) на ( у;, Xj), мы видим, что аналогичные сценарний применимы, когда мы умножаем и на х" . Повторяя этот процесс, мы ВИДИМ, что можно найти представление для со длины не более чем Nco+n0 где По - это длина представления тождественного элемента. Требуемое время имеет порядок 0(2Ii (iN + wo)) = 0(И )
Наконец, чтобы убедиться в том, что весь процесс конструктивен, заметим, что мы можем найти точно допустимое представление тождественного элемента из автоматической структуры: а именно, мы начнем с допустимой строки Xj, ..., хп и воспользуемся приведенной выше процедурой для умножения последовательно на хп" ... xf .
Рассмотрим вопрос, является ли проблема изоморфизма разрешимой для синхронных автоматических групп? То есть, существуют ли, алгоритмы, имеющие на входе две автоматические группы и определяющие на выходе, изоморфны они или нет? Мы предположим, что такого алгоритма нет.
Каждая автоматическая группа G конечно представима и удовлетворяет квадратичному изопериметрическому неравенству то есть, если (A/R) является представлением G, то каждое слово со, представляющее тождествен-ный элемент, может быть записано в виде п=0(со ).
Пусть L будет языком допустимых слов автоматической структуры над А. Вышеприведённое утверждение задает постоянные N и п0 такие, что для любого слова со префиксы co(t) имеют представление ut =L длины не более N(co)+no. Для каждого t элементы и, и ut+l разделены на одну образующую, скажем xt. По нашему утверждению, равномерное расстояние между путями ut и и,+1 ограничено липшицевой постоянной к для L. Поэтому петля utxtut+i" 1 может быть разложена на число петель не больше чем Nco+n0, длина которых не более чем (2к+2) (см рис 3.16). И тогда со само (если оно является петлей) может быть разложено на петли, числом не более Nco +п0со длина которых также ограничена. Мы получаем конечное множество реляторов для G, беря все петли до этой длины. В терминах этого представления G очевидно удовлетворяет квадратичному изопериметрическому неравенству. Как мы заметили в конце пункта 2.2, это дает квадратичное периметрическое неравенство для любого представления.
Эпштейн предварительно использовал идею разрезания круга (без какого - либо обсуждения) для того чтобы показать, что автоматические группы конечно — представимы. Это само по себе было развитием рассуждения Кэннона в его обсуждении почти выпуклых групп.
Рисунок 2.16. Каждая петля ограничивает круг. Для того чтобы найти круг для слова со, представляющего тождественный элемент, мы сначала возьмем представление ut для префиксов co(t). Эти ut могут быть выбраны с длиной, ограниченным числом кратным со (наверху слева). Для двух последовательных значений t это дает нам клин (наверху в центре) которой может быть поделен на четырехсторонние и трёхсторонние области (трёхсторонние области встречаются если ut и ut+i имеют различные длины). Эти области имеют периметр не более, чем 2к+2, где к является липшицевой постоянной для структуры (нижняя часть рисунка).
Применение метода категорного анализа к процедуре идентификации символов входного потока
Выделение границ лексем - одна из основных задач, которую решает сканер входного потока. При разработки компилирующих программ для новых микропроцессоров и микроконтроллеров эта задача является достаточно сложной. Функции, выполняемые лексическим анализатором, и состав лексем, которые он выделяет в тексте исходной программы, могут меняться в зависимости от версии компилятора.
Границы лексем распознаются по заданным терминальным символам. Эти символы - пробелы, знаки операций, символы комментариев, а также разделители (запятые, точки с запятой и др.). Набор таких терминальных символов может варьироваться в зависимости от входного языка. Важно отметить, что знаки операций сами также являются лексемами, и необходимо не пропустить их при распознавании текста. Задача лексического анализа обычно решается с использованием отдельного специализированного программного подпроцессора.
Подпроцессор может строиться с использованием различных методов идентификации слов. Выбор метода идентификации, в конечном счете, определяет качественные характеристики всего лексического блока компилятора.
Наибольшее распространение получили следующие методы: метод автомата; метод линейного списка; метод упорядоченного списка (бинарный поиск); метод хеширования.
В диссертации разработан алгоритм (см. рис. 4.2) работы сканера, который можно описать так: просматривается входной поток символов программы на исходном языке до обнаружения очередного символа, ограничивающего лексему; для выбранной части входного потока выполняется функция распознавания лексемы; при успешном распознавании информация о выделенной лексеме заносится в таблицу лексем, и алгоритм возвращается к первому этапу; при неуспешном распознавании выдается сообщение об ошибке, а дальнейшие действия зависят от реализации сканера - либо его выполнение прекращается, либо делается попытка распознать следующую лексему (идет возврат к первому этапу алгоритма).
Работа программы-сканера продолжается до тех пор, пока не будут просмотрены все символы программы на исходном языке из входного потока. Разработанный алгоритм вычисления количества стационарных точек для функций, заданных на конечных автоматах и использующий структурные характеристики автоматов, позволяет оценивать семантическую сложность символьного текста при работе лексического анализатора новых языков программирования. Уровень конического типа, в данном случае - это количество лексем, которые участвуют в тексте программы. Способ вычисления конического типа показывает границы лексем, и тем самым позволяет выделять эти лексемы в тексте программы, что и позволяет эффективно решать одну из основных проблем компиляции.
В данной главе было приведено приложение результатов теоретического исследования к решению задач лексического анализа в процессе компиляции. Был разработан алгоритм работы сканера входного потока, отличающийся способом распознавания лексем. Этот способ основан на применении теории конического типа и он позволяет выделять эти лексемы в тексте программы, что и приводит к более эффективному решению одной из основных проблем компиляции.
Задачи о способе представления информации в памяти компьютера остаются особенно важными и актуальными в развитии информационных технологий в целом. Современный информационный рынок характеризуется быстрым появлением новых микропроцессоров и микроконтроллеров. Ожидать предоставления аппаратного прототипа перед началом разработки программного обеспечения в настоящее время означает рисковать своим проектом. Ликвидировать постоянное отставание процессов создания программного обеспечения от появления технических средств позволяет одновременная разработка программного и аппаратного обеспечения, что в результате приводит к повышению эффективности проектных работ и ускорению выхода нового изделия на рынок. Сложность рассматриваемой проблемы приводит к необходимости развития исследований в области математической теории программирования в направлении разработки и внедрения новых методов синтаксиса и семантики языков программирования и их оптимизации, отражающих современные комбинаторно-геометрические методы анализа. Корректная постановка соответствующих задач требует глубокого изучения содержания понятия «формальный язык». Специфика проектируемых объектов определяет особенности разработки алгоритмов, в основе которых лежит синтез современных результатов теории автоматов - конечные автоматы и семантического решения различного рода алгоритмических задач. В рамках исследования этих проблем были получены следующие результаты
