Лабораторная работа по теории вычислительных процессов и структур

Федеральное агентство по образованию

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОННИКИ
(ТУСУР)

Томский межвузовский центр дистанционного образования
(ТМЦДО)

Кафедра автоматизированных систем (АСУ)

«Решение системы регулярных выражений»

Отчет по лабораторной работе №3 по дисциплине
«Теория вычислительных процессов и структур»

Выполнил: студентгруппы З-436-б
Козырев А.А.
«___» ___________ 2010 г.

Проверил:__________________
___________________________
«___» ___________ 2010 г.

Томск - 2010
СОДЕРЖАНИЕ

1. Лабораторное задание ……………………………………………………3
2. Краткая теория…………………………………………………………….4
3. Результат работы программы ……………………………………………7
4. Вывод ………………………………………………………………………9Список литературы ………………………………………………………….10
Приложение. Листинг программы …………………………………………11

1.ЗАДАНИЕ

Написать программу решения системы регулярных уравнений с регулярными выражениями. Максимальная размерность системы — 8. Максимальная длина регулярного выражения — 3. Алгоритм решения приведен в учебном пособии на стр. 50 –52. Упростить полученное решение с использованием аксиом (стр.49)

2. КРАТКАЯ ТЕОРИЯ

Рассмотрим краткую теорию решения уравнений с регулярными коэффициентами.
Определение. Регулярные выражения в алфавите [pic]и регулярные множества, которые они обозначают, определяются рекурсивно следующим образом:
1) 0 – регулярное выражение, обозначающее регулярное множество 0;
2) e – регулярное выражение, обозначающее регулярное множество {e};
3) если a[pic], то а – регулярное выражение, обозначающее регулярное множество {a};
4) если p и q – регулярные выражения, обозначающие регулярные множества P и Q, то
а) (p+q) – регулярное выражение, обозначающее [pic];
б) pq – регулярное выражение, обозначающее [pic];
в) [pic]- регулярное выражение, обозначающее [pic];
5) ничто другое не является регулярным выражением.Принято обозначать [pic] для сокращенного обозначения [pic]. Расстановка приоритетов:
- * (итерация) – наивысший приоритет;
- конкатенация;
- + (объединение).
Например, [pic]
Таким образом, для каждого регулярного множества можно найти регулярное выражение, его обозначающее и наоборот.
Введем леммы, обозначающие основные алгебраические свойства регулярных выражений. Путь a, b и y регулярныевыражения, тогда:
1) [pic]
2) [pic]
3) [pic]
4) [pic]
5) [pic]
6) [pic]
7) [pic]
8) [pic]
9) [pic]
10) [pic]
11) [pic]
12) [pic]

При работе с языками часто удобно пользоваться уравнениями, коэффициентами и неизвестными которых служат множества. Такие уравнения будем называть уравнениями с регулярными коэффициентами
[pic]
Где a и b – регулярные выражения. Можно проверить прямойподстановкой, что решение это уравнения будет [pic]
[pic]
т.е. получаем одно и тоже множество. Таким же образом можно установить и решение системы уравнений.
Определение. Систему уравнений с регулярными коэффициентами назовем стандартной системой с множеством неизвестных [pic], если она имеет вид:
[pic]
Где [pic] - регулярные выражения в алфавите, не пересекающемся с [pic]. Коэффициентами уравнения являютсявыражения [pic].
Если [pic], то в уравнении для [pic] нет числа, содержащего [pic]. Аналогично, если [pic], то в уравнении для [pic] член, содержащий [pic], - это просто [pic]. Иными словами, 0 играет роль коэффициента 0, а e – роль коэффициента 1 в обычных системах линейных уравнений.

Алгоритм решения.

Вход. Стандартная система Q уравнений с регулярными коэффициентами в алфавите ( имножеством неизвестных [pic].
Выход. Решение системы Q .
Метод: Аналог метода решения системы линейных уравнений методом исключения Гаусса.
Шаг 1. Положить i = 1.
Шаг 2. Если i = n, перейти к шагу 4. В противном случае с помощью тождеств леммы записать уравнения для [pic] в виде [pic], где ( - регулярное выражение в алфавите (, а ( - регулярное выражение...