Фрагментные преобразования структуры многоленточных автоматов

• Автор: Великая, Яна Геннадьевна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Белгород
• Количество страниц: 169 с. : ил.

Содержание
Введение.

Глава 1. Основные понятия и постановка задач.

1.1 Многоленточные автоматы

1.2 Фундаментальные проблемы многоленточных автоматов.

1.3 Область применения автоматов

1.3.1 Формальное проектирование программного обеспечения

1.3.2 Разработка цифровых устройств.

1.3.3 Лексический анализ

1.3.4 Компьютерная лингвистика

1.3.5 iтехнология.

1.3.6 Специализированные языки программирования
1.4 Единый подход решения фундаментальных проблем.
Глава 2. Фрагмеитныс преобразования.
2.1 Основные понятия
2.2 Система преобразований Т
2.3 Полнота системы Т.
Глава 3. Проблема эквивалентности многоленточных автоматов
3.1 Трансформационный метод.
3.2 Модификация трансформационного метода.
3.3 Решение проблемы эквивалентности многоленточных автоматов, модифицированным трансформационным методом
3.3.1 Конечные автоматы.
3.3.2 Однородные автоматы.
Глава 4. Проблема минимизации и с решение для некоторых
множеств многоленточных автоматов.
4.1 Общее описание процедуры минимизации
4.2 Минимизация по сложным элементам
4.3 Минимизация по простым элементам
4.4 Окончательная минимизация
4.5 Алгоритмы минимизации
4.6 Сравнение алгоритмов минимизации.
4.7 Применение многоленточных автоматов в многопроцессорных
системах.
Заключение.
Список литературы


Последнее означает, что это модель многозадачного процесса вычислений, поскольку работа на одной ленте может восприниматься как работа, выполненная одной задачей обладающей возможностью коммутировать с остальными. При этом в каждой цепочке задач, начинающихся во входе и заканчивающихся в выходе число выполнений каждой задачи данной разновидности, должно сохраняться. Исследуемая модель не является универсальной моделью вычислений. Это утверждение справедливо и для случая двухленточного автомата. Для недетерминированных многоленточных автоматов (даже для двухленточных автоматов, которые обычно называются конечными преобразователями) проблема эквивалентности является стандартным примером неразрешимой проблемы. Этот результат неразрешимости был впервые доказан Т. Гриффитсом в г. Рис. Для многоленточных автоматов, также как и для конечных детерминированных автоматов, существует ряд проблем, называемых фундаментальными: проблема эквивалентных преобразований, проблема эквивалентности и проблема минимизации. Опишем актуальное состояние этих проблем. Введем ряд определений. Преобразование многоленточного автомата называется эквивалентным [-], если оно переводит многоленточный автомат в эквивалентный многоленточный автомат. Некоторое конечное множество эквивалентных преобразований называется системой эквивалентных преобразований [; ]. В работах [-] получены решения проблемы эквивалентных преобразований для отдельных подклассов многоленточных автоматов. В г. Рассмотрим следующую проблему: проблему эквивалентности. Проблема эквивалентности заключается в нахождении алгоритма, который по паре многоленточных автоматов определяет, эквивалентны они или нет. Решение этой проблемы для конечных автоматов было предложено в работах [-] и др. Для многоленточных автоматов долгое время не удавалось решить проблему эквивалентности. Это было связано с доказательством неразрешимости проблемы включения для многоленточных автоматов []. Поэтому решить проблему эквивалентности для многоленточных автоматов, используя стандартные подходы пригодные для конечных автоматов, не представляется возможным. Для двухленточных автоматов решение проблемы было предложено Бердом Р. В г. Т. Харыо и Дж. Кархумаки доказали разрешимость проблемы эквивалентности многоленточных автоматов, но алгоритм разрешения эквивалентности не был предложен []. Подловченко Р. И. и Хачатряном В. Е. был предложен трансформационный метод, использующий фрагментные эквивалентные преобразования [-]. Была доказана применимость трансформационного метода с целью разрешения эквивалентности в некоторых подклассах многоленточных автоматов[;]. В г. Лстичевский А. А, Шукурян A. C. и Шукурян С. Проблема минимизации многоленточного автомата заключается в построении по многоленточному автомату другого многоленточного автомата, эквивалентного исходному, но с минимальным числом состояний. Проблема минимизации конечных автоматов решена, её решение приведено в работах [-]. Что касается проблемы минимизации многоленточных автоматов, то она является почти не изученной. Предложены её решения лишь для некоторых частных случаев. Так, в работе [;] проблема решена для одного подкласса двухленточных автоматов, а в [] приведено построение по заданному автомату автомата близкого к минимальному автомату. Подводя итог, можно утверждать, что многие из фундаментальных проблем многоленточных автоматов до сих пор остаются открытыми. Конечные автоматы широко используются в различных областях информатики. Они используются в качестве языка программирования микроконтроллеров, при программировании мобильных устройств, компьютерных игр, в синтаксических и лексических анализаторах. Например, конечные автоматы используются для ЬЛ-анализа [I], метода синтаксического разбора для компиляторов языков программирования. ЬЛ-анализ осуществляется на основе ЬЛ-грамматик. ЬЛ-грамматики - это грамматики, для которых возможен детерминированный восходящий синтаксический анализ с чтением цепочки слева направо. Метод построения ЬЛ-анализатора даёт очень большие по объему анализаторы для грамматик.