close

Вход

Забыли?

вход по аккаунту

?

Табличная имитация алгоритмов искусственного интеллекта.

код для вставкиСкачать
управление, вычислительная техника и информатика
Зибров П.Ф., Аникина О.В.
ТАБЛИЧНАЯ ИМИТАЦИЯ АЛГОРИТМОВ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА
УДК 004.8
ТАБЛИЧНАЯ ИМИТАЦИЯ АЛГОРИТМОВ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА
© 2010
П.Ф. Зибров, доктор технических наук, профессор,
заведующий кафедрой «Высшая математика и математическое моделирование»
Тольяттинский государственный университет, Тольятти (Россия)
О.В. Аникина, аспирант
Поволжский государственный университет сервиса, Тольятти (Россия)
___________________________________________________________________________________________________________
Ключевые слова: имитационное моделирование; электронные таблицы; клеточный автомат; генетический
алгоритм; искусственная нейронная сеть.
Аннотация: приводятся результаты имитационного табличного моделирования алгоритмов работы клеточных
автоматов, генетических алгоритмов и искусственных нейронных сетей.
ВВЕДЕНИЕ
Целью исследования является применение оригинальной технологии создания итерационных табличных моделей
[1, 2] для имитации работы алгоритмов клеточных автоматов
[3, 4], генетических алгоритмов [5] и искусственных нейронных сетей (ИНС) [6]. Имитационные табличные модели строятся в среде табличного процессора в визуальном
режиме по принципу «программирование без программирования», отличаются большой гибкостью и наглядностью,
способствуют выработке у создателей моделей творческого,
креативного мышления. Разработанная технология имитационного табличного моделирования алгоритмов искусственного интеллекта и множества других вычислительных
алгоритмов представляет наибольший интерес для учебных целей, обеспечивая учащимся неограниченный доступ
к структурам данных и алгоритмам их обработки, а также
наглядно отображая в динамическом режиме промежуточные и выходные результаты моделирования.
МЕТОДИКА ПРОВЕДЕНИЯ ИССЛЕДОВАНИЙ
Электронную таблицу (ЭТ) можно представить себе как
некий распределенный вычислитель. В процессе пересчета ЭТ
каждая ее ячейка выполняет свою долю кооперативной работы
по хранению и переработке данных решаемой задачи, используя
для вычислений формулу, ассоциированную с этой ячейкой, и
саму себя - в качестве хранилища полученного результата. Затем
в дело вступают следующие ячейки таблицы, которые принимают полученные другими ячейками результаты вычислений,
выполняют свою работу по обработке данных и так далее до тех
пор, пока совместными усилиями общая задача не будет решена.
Должным образом организуя связи между ячейками ЭТ
и применяя в них требуемые формулы можно, в принципе,
«заставить» такой распределенный вычислитель решить
вычислительную задачу любой степени сложности, разумеется, в пределах потенциальных возможностей применяемых
табличного процессора и компьютерной системы.
Идея имитационного табличного моделирования вычислительных алгоритмов, реализованная в работах [1, 2], заключается в адекватном отображении любого последовательного
или параллельного алгоритма на исполнительные устройства
этого распределенного вычислителя – ячейки электронной
таблицы, решающей задачу алгоритма.
И действительно, не прибегая к программированию на
VBA, в работе [2] были созданы имитационные табличные
модели большинства классических вычислительных алгоритмов, составляющих основу численных методов:
Вектор науки ТГУ. № 4(14), 2010
вычисления по рекуррентным формулам, в том числе с
использованием метода простых итераций;
интерполяция функций;
решение систем алгебраических уравнений;
решение трансцендентных уравнений методами деления
отрезка пополам, хорд, касательных;
одномерная и многомерная оптимизация (методами золотого сечения, градиентного спуска и др.);
численное дифференцирование, интегрирование, решение обыкновенных дифференциальных уравнений (методами
Эйлера, Рунге-Кутты, Адамса), а также некоторых уравнений
в частных производных;
решение вероятностных вычислительных задач методом
Монте – Карло и др.
В работах [3-6] идея имитационного табличного моделирования вычислительных алгоритмов была обобщена на
ряд алгоритмов искусственного интеллекта. Характерной
особенностью последних является то, что все они опираются на метод простых итераций, где в клеточных автоматах
один цикл итераций означает смену одного поколения популяции клеток, в генетических алгоритмах – цикл скрещивания, мутации и отбора, в ИНС – обучение нейронной сети на
одном учебном образце. По этой причине все эти алгоритмы
потребовали использования электронных таблиц в режиме
множественного пересчета ЭТ, т.е. разработки нестандартных итерационных табличных моделей.
Практическая реализация имитационных табличных
моделей алгоритмов клеточных автоматов, генетических
алгоритмов и нейронных сетей подробно описана в работах
[3, 5, 6] и здесь не рассматривается ввиду их сложности и
громоздкости.
РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЙ
Главные достоинства имитационного табличного моделирования алгоритмов искусственного интеллекта заключаются в следующем:
обеспечение свободы творчества и экспериментирования
для квалифицированных программистов и пользователей ПК,
не обладающих хорошими программистскими навыками;
полная открытость для анализа и модификации структур
данных и алгоритма решения задачи;
погруженность создаваемой имитационной модели в
мощную вычислительную среду табличного процессора, обеспечивающую всесторонний анализ, эффективную отладку и
визуальное отображение данных в виде таблиц, диаграмм,
графиков;
27
Зибров П.Ф., Аникина О.В.
управление, вычислительная техника и информатика
ТАБЛИЧНАЯ ИМИТАЦИЯ АЛГОРИТМОВ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА
Рис.
1. Состояние
клеточногоклеточного
автомата семейства
Марголуса после
25 итераций [3].
Рис.1.
Состояние
автомата
«Автоволны»
после 25 итераций [4].
Рис.1. Состояние клеточного автомата «Автоволны» после 25 итераций [4].
использование инструментальных средств и функциональных возможностей электронных таблиц для тестирования новых гипотез и идей;
исключительная полезность и наглядность имитационных табличных моделей для учебных целей.
Нами были созданы имитационные табличные аналоги алгоритмов. В созданной нами имитационной табличной модели ГА
почти всех семейств клеточных автоматов (КА), представлен- алгоритмов.
В созданной нами имитационной табличной модели ГА
задействованы следующие генетические механизмы: селекция методом
ных в великолепной программе М. Войтовича Mcell для иссле- задействованы следующие генетические механизмы: селекция методом
ранжирования, одноточечное скрещивание, инверсия (мутация) одного гена в
дования КА [http://www.mirekw.com], и ряда других: «Муравей ранжирования, одноточечное скрещивание, инверсия (мутация) одного гена в
Лэнгтона», «Автоволны», «Одномерная диффузия», семейства случайно выбранной точке.
случайно
выбраннойглобальной
точке.
Результаты
максимизации и минимизации функции
КА «1D-binary», «Generations», «Life», «Margolus», «RulesРезультаты глобальной максимизации и минимизации функции
Table», «Vote-for-Life», «Weighted-Life» и др.
Растригина представлены на рис.3. Эксперименты с моделью показали, что при
представлены
на равном
рис.3. Эксперименты
с моделью
показали,
что при
На рис. 1, 2 для примера представлены состояния ими- Растригина
числе особей
в популяции,
n= 20, глобальный
оптимум
определяется
тационных табличных моделей клеточных автоматов «Авто- числе особей
Рис.2.
Состояние
клеточного
автомата
семейства
Марголуса
в
популяции,
равном
n=
20,
глобальный
оптимум
определяется
2. Состояние
обычно Рис.
за несколько
десятковклеточного
итераций. автомата семейства Марговолны» и семейства Марголуса после выполнения 25 итера- обычно
после
несколько
десятков
итераций.
лусазапосле
25 итераций
[3].25 итераций [3].
ций (смен поколений). Важной особенностью этих моделей
является простота визуализации временного поведения КА,
Возможность табличной имитации генетических алгоритмов (ГА)
достигаемая использованием условного форматирования
продемонстрирована на примере глобальной оптимизации функции Растригина,
ячеек электронной таблицы.
Возможность табличной имитации генетических алго- часто используемой в качестве тестовой для различных оптимизационных
ритмов (ГА) продемонстрирована на примере глобальной
оптимизации функции Растригина, часто используемой в
качестве тестовой для различных оптимизационных алгорита) Максимизация
мов. В созданной нами имитационной табличной модели ГА
а) Максимизация
задействованы следующие генетические механизмы: селекция методом ранжирования, одноточечное скрещивание,
Рис.2.
Состояние
инверсия (мутация)
одного
гена в случайноклеточного
выбранной точке. автомата семейства Марголуса
Результаты глобальной максимизации и минимизации
функции Растригина представлены на рис.3.
Эксперименпосле
25 итераций [3].
ты с моделью показали, что при числе особей в популяции,
равном n= 20, глобальный оптимум определяется обычно за
несколько десятков итераций.
б) Минимизация
а) Максимизация
Возможность
б) Минимизация
Рис.3. Глобальная
оптимизацияоптимизация
функции
Растригина
с помощью
имитационной
б)
Минимизация
Рис.3.
Глобальная
функции
Растригина
табличной имитации
генетических
алгоритмов
(ГА)с
Рис.3. Глобальная оптимизация функции Растригина с помощью имитационной
помощью имитационной
генетического
табличной модели табличной
генетическогомодели
алгоритма
[5].
модели генетического алгоритма [5].
алгоритма табличной
[5].
продемонстрирована на примере глобальной
оптимизации
Возможность
построения функции
имитационной Растригина,
табличной
модели
Возможность
построения
имитационной
табличной
модели
искусственной нейронной сети была продемонстрирована на примере решения
Вектор
науки ТГУ. на
№ примере
4(14), 2010
28
часто
используемой в качестве тестовой
длянейронной
различных
оптимизационных
искусственной
сети была
продемонстрирована
классической задачи
Фишера
о классификации
цветков ирисов.
Врешения
задаче
классической задачи Фишера о классификации цветков ирисов. В
Фишера рассматриваются три вида цветков ириса. Всего имеется
Фишера
рассматриваются
три вида
видаи цветков
ириса.
имеется
экземпляров
цветков каждого
для каждого
из Всего
них измерены
задаче
по 50
по
50
четыре
экземпляров цветков каждого вида и для каждого из них измерены четыре
управление, вычислительная техника и информатика
Зибров П.Ф., Аникина О.В.
ТАБЛИЧНАЯ
ИМИТАЦИЯ
АЛГОРИТМОВ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА
раметра: длина и ширина чашелистника, длина
и ширина
лепестка.
Возможность построения имитационной табличной
араметры ирисов
являются независимыми переменными, а тип ВЫВОДЫ
ириса –
модели искусственной нейронной сети была продемонстри-
Продемонстрированная нами возможность создания
классификации цветков ирисов. В задаче Фишера рассматри-
клеточных автоматов, генетических алгоритмов и искус-
рована на примере
классической
задачи Фишера
о имитационных
висимой переменной.
Цельрешения
состоит
в том, чтобы
по данным
четырех табличных моделей алгоритмов работы
мерений научиться
предсказывать
вид нового,
неизвестного
цветкаственных
ириса. нейронных сетей убедительно доказывает, что
ваются три
вида цветков ириса.
Всего имеется
по 50 экземэлектронные таблицы могут успешно использоваться в
пляров цветков
и для каждоготрехслойная
из них измереныИНС
В табличном
виде каждого
была вида
реализована
прямого
четыре параметра: длина и ширина чашелистника, длина и
качестве эффективной среды имитационного моделиро-
ми переменными, а тип ириса – зависимой переменной. Цель
алгоритмов.
вания и визуализации разнообразных вычислительных
ширина
ирисов скрытый
являются независимыспространения
видалепестка.
4 – 6 Параметры
– 3 (4 входа,
слой из 6 нелинейных
йронов, выходной
3 линейных
с алгоритмом
состоитслой
в том,из
чтобы
по даннымнейронов)
четырех измерений
научить- обучения сети
СПИСОК ЛИТЕРАТУРЫ
ся предсказывать
вид нового, ошибки.
неизвестного
цветканачалом
ириса.
етодом обратного
распространения
Перед
обучения
сети
В табличном виде была реализована трехслойная ИНС пря-
[1] Алгоритмическое табличное моделирование в
Excel / В.И.Аникин, О. В. Аникина. - «Информаользователь может
выбрать величину
инерции,
скорость
обучения,
мого распространения
вида 4 – 6момента
– 3 (4 входа,
скрытый слой
из Microsoft
6 нелинейных нейронов, выходной слой из 3 линейных нейро-
тика и образование», 2008. - №9. - с. 49-54
может выбрать величину момента инерции, скорость обучения,
Аникина. - «Информатика и образование», 2009. - № 9, с.
чальный случайный
вес синапсов,
число
эпохобратного
обучения,
а также[2]режим
Алгоритмическое табличное моделирование в
нов) с алгоритмом
обучения сети
методом
распроMicrosoft
Excel: итерационные модели / В.И. Аникин, О.В.
странения
ошибки.
Перед сети
началом
обучения сети пользователь
одачи учебных
образцов
на входы
(рис.4).
Эксперименты,
с созданной
имитационной
табличной
начальныйпроведенные
случайный вес синапсов,
число эпох обучения,
а так- 88-95
же режим подачи учебных образцов на входы сети (рис.4).
[3] Табличное моделирование клеточных автоматов в
сов, показали, что в оптимальных режимах подачи образ-
[4] Табличное моделирование спиральных автоволн с
классифицировать контрольные и неизвестные образцы уже
после 10 эпох обучения (рис.5).
кина. - Тезисы докладов VII Международной научно – технической конференции «Физика и технические приложения волновых процессов». – Самара, 2008. - с.12-13
[5] Табличное моделирование генетических алгоритмов в Microsoft Excel / О.В. Аникина, Е.М. Звездилина. Проведение научных исследований в области обработки,
хранения, передачи и защиты информации: сб. научных
трудов Всероссийской конференции с элементами научной
школы для молодежи, т. 4. – Ульяновск: УГТУ, 2009. - с.
278-286
[6] О возможности табличной реализации нейронных
сетей в Microsoft Excel / В.И. Аникин, О.В. Аникина. Потенциал развития непроизводственной сферы в крупных промышленных городах Поволжского региона: взгляд
молодых профессионалов: сб. ст. II международной научно
– практической конференции. Ч. II / Поволжский гос. ун-т
сервиса. – Тольятти: Изд-во ПВГУС, 2009. – с. 266-270.
оделью ИНС Эксперименты,
для классификации
цветков ирисов, показали, что в
проведенные с созданной имитационной Microsoft Excel / В.И.Аникин, О.В. Аникина. - «Информатехнологии», 2009. - № 6, с. 23-28
табличной моделью
для классификации
ири- ционные сеть
птимальных режимах
подачи ИНС
образцов
«Случайно»цветков
и «Перемешивая»
помощьюуже
клеточных автоматов / В.И. Аникин, О.В. Аничинает надежно
классифицировать
контрольные
и неизвестные
цов «Случайно»
и «Перемешивая»
сеть начинает
надежно образцы
осле 10 эпох обучения (рис.5).
Рис.4. Пользовательский
интерфейс интерфейс
имитационной
табличной
Рис. 4. Пользовательский
имитационной
таблич-модели ИНС
ной модели
для классификации
цветков
ириса[6].
[6].
дляИНС
классификации
цветков
ириса
Величина ошибки
1
0,9
0,8
0,7
0,6
0,5
0,4
0,3
0,2
0,1
0
0
20
Последовательно
40
Случайно
60
80
100
Количе ство эпох
Перемешивая
Рис.5. Среднеквадратичная ошибка обобщения имитационной табличной
Рис. 5. Среднеквадратичная ошибка обобщения имиИНС для
контрольных
образцов.
тационной модели
табличной
модели
ИНС для
контрольных
образцов.
Вектор науки ТГУ. № 4(14), 2010
ВЫВОДЫ
Продемонстрированная нами возможность создания имитационных
29
Мельников Б.Ф., Зубова М.А.
управление, вычислительная техника и информатика
ПОСТРОЕНИЕ АВТОМАТА COM НА ОСНОВЕ БАЗИСНОГО АВТОМАТА
Table Simulation of Artificial Intelligence Algorithms
© 2010
P.F. Zibrov, doctor of technical sciences,
professor, head of the chair "High mathematics and mathematical modeling"
Togliatti State University, Togliatti (Russia)
O.V. Anikina, postgraduate student
В [1] был
получен алгоритм построения автомата, анал
Volga Region State University of Services, Togliatti
(Russia)
В [1] был получен алгоритм построения автомата, аналогичного COM, на
___________________________________________________________________________________________________________
множестве т. н. псевдоблоков [2]. В данной статье мы
Keywords: simulation; cellular automata; genetic
algorithm;
neural network;
множестве
т. н.artificial
псевдоблоков
[2]. В spreadsheets.
данной статье мы будем строить
непосредственно автомат COM – на его подмножестве (на
Annotation: results of spreadsheets simulation of cellular automata, genetic algorithms, artificial neural networks are
непосредственно автомат COM – на его подмножестве (на основе одного из
discussed.
результатов работы [3] можно доказать, что это подмн
УДК
результатов работы [3] можно доказать, что это подмножество является
заалгоритм
исключением
нескольких
«вырожденных»
В собственным
[1] был
построения
аналогичного
COM,слн
Впостроения
[1] был
Вполучен
[1]
былавтомата,
алгоритм
получен
алгоритм
построения
построения
автомата
В алгоритм
[1]получен
был
получен
построения
автомата,
аналогичного
В[1][1]
былполучен
получен
алгоритм
автомата,
аналогичного
на C
собственным заВисключением
нескольких
«вырожденных»
случаев
), а именно
– на
[1]Вбыл
получен
был
алгоритм
построения
построения
В алгоритм
[1] был
автомата,
получен
автомата,
аналогичного
алгоритм
аналогичного
построения
COM,
COM,
наCOM,
автомата
на множестве
блоков.
Кроме
того,
мы
впервые
получим
множестве
т.
н.
псевдоблоков
[2].
В
данной
статье
мы
будем
строит
множестве
множестве
т. данной
н.[2].
псевдоблоков
т.Встатье
н.
псевдоблоков
[2].
В мы
данной
[2].
Вформ
стат
дан
множестве
т. н.[2].
псевдоблоков
данной
статье
будем
множестве
т.
н.псевдоблоков
псевдоблоков
мыбудем
будем
строить
множестве
множестве
т.Кроме
н.т.
псевдоблоков
н.того,
множестве
[2].
В [2].
данной
В Вт.
данной
н.статье
псевдоблоков
статье
мы
будем
мы
[2].
строить
В строить
данной
статс
на множестве
блоков.
мы впервые
получим
формулу
для
описания
входного
и
выходного
языков
произвольного
состояния
этого
(
на
основе
одного
непосредственно
автомат
COM
–
на
его
подмножестве
непосредственно
непосредственно
автомат
COM
автомат
– основе
наCOM
его(на
–подмножеств
на
его поди
основе
непосредственно
автомат
COM
– на
его
подмножестве
одного
непосредственно
автомат
–нана
егоподмножестве
подмножестве
519.178
(наавтомата
(на(на
основе
основе
одного
из
из из одн
непосредственно
автомат
автомат
COM COM
–COM
на
непосредственно
–его
подмножестве
его
автомат
COM
– одного
на
подмножеств
входного инепосредственно
выходного
языков
произвольного
состояния
этого
– вего
этом
результатов
работы
[3]
можно
доказать,
что
это
подмножество
иработы
состоит
основной
результат
данной
статьи.
Изявляется
этой
фор
результатов
результатов
работы
[3]
работы
можно
доказать,
можно
доказать,
чтоявляетс
это
чп
результатов
[3]доказать,
можно
доказать,
что[3]
это
подмножество
результатов
можно
чтоподмножество
это
подмножество
результатов
результатов
работы
работы
[3] можно
[3][3]работы
можно
доказать,
результатов
доказать,
чтоработы
что
это
это[3]
подмножество
можно
доказать,
является
является
что это яв
и состоит
основной
результат
данной
статьи.
Из
этой
формулы
очевидным
ПОСТРОЕНИЕ
АВТОМАТА
COM
НА
ОСНОВЕ
)
собственным
за
исключением
нескольких
«вырожденных»
случаев
,
а
именно
собственным
собственным
за
исключением
заавтомата,
исключением
нескольких
нескольких
«вырожденны
«вы
образом
следует,
среди
прочего,
эквивалентность
определяем
собственным
за исключением
нескольких
«вырожденных»
В [1] был получен алгоритм
В [1] былпостроения
получен алгоритм
построения
аналогичного
автомата,
COM,
на
аналогичного
COM,
на
а случаев
именно
собственным
за
исключением
нескольких
«вырожденных»
случаев
Вавтомата,
[1] был
получен
алгоритм
Вза
[1]
былпостроения
получен
алгоритм
автомата,
построения
аналогичного
COM,
наименно
COM,
н
собственным
собственным
за исключением
исключением
нескольких
собственным
нескольких
«вырожденных»
«вырожденных»
за
исключением
случаев
случаев
нескольких
«вырожденны
–
– ),–а им
), ааналогичного
), а),именно
образом следует,АВТОМАТА
среди
прочего,
эквивалентность
определяемого
нами
автомата
на множестве
блоков.
Кроме
того,
мы
впервые
получим
формулу
для
описани
БАЗИСНОГО
на
множестве
на
множестве
блоков.
Кроме
блоков.
того,
Кроме
мы
того,
впервые
мы
получим
впервые
на
множестве
блоков.
Кроме
того,
мы
впервые
получим
формулу
для
оп
на
множестве
блоков.
Кроме
того,
мы
впервые
получим
формулу
для
описания
множестве т. н. псевдоблоков
множестве т. [2].
н. псевдоблоков
Вмножестве
данной
статье
[2].
мы
В
данной
будем
статье
строить
мы
будем
строить
т.
н.
псевдоблоков
множестве
т.
[2].
н.
псевдоблоков
В
данной
статье
[2].
В
мы
данной
будем
статье
строить
мы
будем
строит
COM
и
исходного
конечного
автомата
(или
заданного
регуляр
на множестве
на множестве
блоков.
блоков.
Кроме
Кроме
того,того,
мы
на множестве
впервые
мы впервые
получим
блоков.
получим
формулу
Кроме
формулу
того,
для мы
описания
длявпервые
описания
получим
входного
и выходного
языков
произвольного
состояния
этого автомата
– в этом
входного
входного
и выходного
и выходного
языков
произвольного
языков
произвольного
и исходного
конечного
автомата
(или
заданного
регулярного
языка).
и из
выходного
языков
состояния
этого
входного
ивходного
выходного
произвольного
этого
автомата
– автомата
всостояния
этом и–с
(на
(языков
основе
одного
на
основе
одного
из
непосредственно автомат
непосредственно
COM – наCOM
автомат
егонепосредственно
подмножестве
COM – на
его
подмножестве
(его
(на основе
насостояния
основе
одного
из
одного
автомат
непосредственно
COM
– на
автомат
его
подмножестве
COM
– напроизвольного
подмножестве
© 2010
входного
входного
и выходного
и выходного
языков
языков
произвольного
входного
произвольного
исостояния
выходного
состояния
этого
языков
этого
автомата
произвольного
автомата
– в этом
– в этом
состояния
и состоит
основной
результат
данной
статьи.
Из этой
формулы
очевидным
ипрофессор
состоит
иавтомата,
основной
состоит
основной
результат
результат
данной
статьи.
данной
Из
статьи
это
и
состоит
основной
результат
данной
статьи.
Из
этой
формулы
и
состоит
основной
результат
данной
статьи.
Из
этой
формулы
очевидным
В [1]результатов
был
Вможно
получен
[1]
был
получен
алгоритм
алгоритм
построения
построения
автомата,
аналогичного
аналогичного
COM,
на
COM,
на
Мельников,
доктор
наук,
результатовБ.Ф.
работы
результатов
[3] можно работы
доказать,
[3]физико-математических
что
это
доказать,
подмножество
что
это
является
подмножество
является
результатов
[3]основной
можно
работы
доказать,
[3]
что
можно
это статьи.
доказать,
подмножество
что
это
является
подмножество
и состоит
иработы
состоит
основной
результат
результат
данной
и данной
состоит
статьи.
основной
Из этой
Из результат
этой
формулы
формулы
данной
очевидным
очевидным
статьи. являетс
Изочев
это
образом
следует,
среди среди
прочего,
эквивалентность
определяемого
нами автомат
образом
следует,
образом
среди
следует,
прочего,
среди определяемого
эквивалентность
прочего,
эквивалентно
опред
профессор
кафедры
«Прикладная
математика
и
прикладная
информатика»
образом
следует,
прочего,
эквивалентность
нами
ав
образом
следует,
среди
прочего,
эквивалентность
определяемого
нами
автомата
)
)
,
а
именно
–
,
а
именно
–
собственным
за исключением
собственным
нескольких
за
исключением
«вырожденных»
нескольких
случаев
«вырожденных»
случаев
)
)
собственным
за
исключением
собственным
нескольких
за
исключением
«вырожденных»
нескольких
случаев
«вырожденных»
случаев
,
а
именно
–
,
а
именно
образом
образом
следует,
следует,
среди
среди
прочего,
прочего,
эквивалентность
образом
эквивалентность
следует,
определяемого
среди
определяемого
прочего,
нами
эквивалентность
нами
автомата
автомата
опред
2.
ПРЕДВАРИТЕЛЬНЫЕ
СВЕДЕНИЯ
множестве
множестве
т. н. псевдоблоков
т. н. псевдоблоков
[2]. В данной
[2]. В данной
статье мы
статье
будем
мы строить
будем строить
COM
и
исходного
конечного
автомата
(или
заданного
регулярного
языка).
М.А.
Зубова,
студентка
COM
и исходного
COM
изаданного
исходного
конечного
конечного
автомата
автомата
(или
заданного
(или
зад
ре
2.впервые
ПРЕДВАРИТЕЛЬНЫЕ
СВЕДЕНИЯ
COM
иконечного
исходного
конечного
автомата
(или
заданного
регулярного
языка)
COM
и
исходного
конечного
автомата
(или
регулярного
языка).
на множестве блоков.
наКроме
множестве
того, блоков.
мы
получим
того,COM
мы
формулу
для
получим
описания
формулу
для
описания
наКроме
множестве
на
Кроме
множестве
того,
блоков.
мы
впервые
Кроме
получим
мы
формулу
впервые
для
получим
описания
формулу
для
COM
иблоков.
исходного
ивпервые
исходного
конечного
автомата
COM
(или
итого,
исходного
(или
заданного
заданного
конечного
регулярного
регулярного
автомата
языка).
языка).
(или
заданного
ре
(на
основе
(на
одного
основе
из
одного
изописани
непосредственно
непосредственно
автомат
автомат
COM
– на
COM
его
–автомата
подмножестве
на
его
подмножестве
Будем
использовать
следующие
обозначения.
Пусть
Тольяттинский
государственный
университет,
Тольятти
(Россия)
входного и выходного
входного
языков ипроизвольного
выходного
языков
состояния
произвольного
этого
автомата
состояния
–
в
этом
этого
автомата
–
в
этом
входного
и
выходного
входного
языков
и
произвольного
выходного
языков
состояния
произвольного
этого
автомата
состояния
–
в
этом
этого
автомата
–
в
этом
Будем использовать следующие обозначения. Пусть
___________________________________________________________________________________________________________
результатов
результатов
работы работы
[3] можно
[3] доказать,
можно доказать,
что это что
подмножество
это подмножество
является
K = {Q,является
Σ, δ, S, F}
состоитнедетерминированный
основнойи результат
состоит основной
данной
результат
Из
этой
данной
формулы
статьи.
очевидным
Изосновной
этой
формулы
очевидным
истатьи.
состоит
основной
и
результат
состоит
данной
статьи.
результат
Из данной
этой
формулы
статьи. очевидным
Из этой
формулы очевидным
Ключевыеислова:
конечный
автомат;
базисный
автомат;
всевозможных
дуг.
2.
ПРЕДВАРИТЕЛЬНЫЕ
СВЕДЕНИЯ
2.
ПРЕДВАРИТЕЛЬНЫЕ
2.
ПРЕДВАРИТЕЛЬНЫЕ
СВЕДЕНИЯ
= {Q, Σ, множество
δ, S, F}
(1)СВЕДЕНИ
2. –K
ПРЕДВАРИТЕЛЬНЫЕ
СВЕДЕНИЯ
2. исключением
ПРЕДВАРИТЕЛЬНЫЕ
СВЕДЕНИЯ
собственным
собственным
за исключением
нескольких
нескольких
«вырожденных»
«вырожденных»
случаев
),случаев
а определяемого
именно
), аСВЕДЕНИЯ
–именно
– автомат
2.
2.за
ПРЕДВАРИТЕЛЬНЫЕ
ПРЕДВАРИТЕЛЬНЫЕ
СВЕДЕНИЯ
2.
СВЕДЕНИЯ
ПРЕДВАРИТЕЛЬНЫЕ
недетерминированный
конечный
автомат
Рабина-Ск
образом
следует,
среди
образом
прочего,
следует,
эквивалентность
среди
прочего,
определяемого
эквивалентность
нами
определяемого
автомата
нами
автомата
образом
следует,
среди
образом
прочего,
следует,
эквивалентность
среди
прочего,
определяемого
эквивалентность
нами
автомата
нами
Аннотации: в статье рассматривается множество
дуг,
определенное
на
блоках
бинарного
отношения
#.
Дуги
Будем
использовать
следующие
обозначения.
Пусть
Будем
использовать
Будем
использовать
следующие
следующие
обозначения.
обознач
Пус
–
недетерминированный
конечный
автомат
Рабина-Скотта
или,
иначе,
Будем
использовать
следующие
обозначения.
Будем
использовать
следующие
обозначения.
Пусть
на множестве
наCOM
множестве
блоков.
Кроме
блоков.
того,
Кроме
мы
того,
впервые
мы
впервые
получим
получим
формулу
формулу
для
описания
дляПусть
описания
Будем
Будем
использовать
следующие
следующие
обозначения.
Будем
обозначения.
использовать
Пусть
Пусть
следующие
обозначения.
COM и исходного
конечного
COM и исходного
автомата
конечного
(или
заданного
автомата
регулярного
(или
заданного
языка).
регулярного
языка).
этого множества
соответствуют
всем
возможным
дугам
любого
недетерминированного
конечного
автомаи исходного
конечного
COM
ииспользовать
исходного
автомата
конечного
(или
заданного
автомата
регулярного
(или
заданного
языка).
регулярного
языка).
конечный
автомат,
определяющий
регулярный
язык LПус
=
K = {Q,
Σ,
δ, S,
K
= {Q,
Kδ,= S,
{Q,
F}Σ,(1)
δ, S,(1
F
K
=F}{Q,
Σ,F}
δ, S,L
та, определяющего заданный регулярный
язык.
Наавтомат,
этого
множества
дуг
определяется
автомат
COM,
= δ,
{Q,
δ,
F}Lэтого
конечный
определяющий
=
(K),
где–Σ,
K регулярный
=состояния
{Q,
KK
=Σ,
{Q,
S,
Σ, Σ,
F}
δ,язык
S, S,
= {Q,
Σ,вQ
δ,этом
(1)
S,– F}
(1)
входного
входного
и выходного
и основе
выходного
языков
произвольного
языков
произвольного
состояния
этого
автомата
автомата
–F}
вK
этом
множество
состояний,
S и
⊆ выходных
Q
и F ⊆Рабина-Скотта
Q
– множества
старто
–получены
недетерминированный
конечный
автомат
или,
иначе
являющийся инвариантом рассматриваемого языка. В статье
описания
входных
языков
–
недетерминированный
–
недетерминированный
конечный
конечный
автомат
автом
Раби
– недетерминированный
конечный
автомат
Рабина-Скотта
или,
недетерминированный
конечный
автомат
Рабина-Скотта
или,
иначе,
–основной
недетерминированный
– – недетерминированный
конечный
–статьи.
недетерминированный
автомат
Рабина-Скотта
Рабина-Скотта
конечный
или,
иначе,
автомат
иначе,
Раби
и состоит
и состоит
основной
результат
результат
данной
этойавтомат
Из
формулы
этой
формулы
очевидным
очевидным
множество
состояний,
S данной
⊆ Q и Fстатьи.
⊆ Qконечный
–Из
множества
стартовых
и или,
финальных
состояний2.автомата
COM. 2. ПРЕДВАРИТЕЛЬНЫЕ
состояний
Будем рассматривать
автомат
бе
ПРЕДВАРИТЕЛЬНЫЕ
СВЕДЕНИЯ
СВЕДЕНИЯ
конечный
автомат, соответственно.
определяющий регулярный
язык L = L(K),
где Q
2. ПРЕДВАРИТЕЛЬНЫЕ
2. конечный
ПРЕДВАРИТЕЛЬНЫЕ
СВЕДЕНИЯ
СВЕДЕНИЯ
конечный
конечный
автомат,
автомат,
определяющий
определяющий
регулярный
В [1]
был
получен
алгоритм
построения
ана
автомат,
определяющий
L автомата,
= Lрегулярн
гд
конечный
автомат,
определяющий
регулярный
=Lязык
Lавтомата
(K),
где
Q(K),–язык
конечный
конечный
автомат,
автомат,
определяющий
определяющий
конечный
регулярный
регулярный
автомат,
языкрегулярный
язык
определяющий
Lязык
=ε-переходов,
LLL(K),
=
регулярный
(K),
где
Q
где
образом
образом
следует,
следует,
среди
прочего,
среди
прочего,
эквивалентность
эквивалентность
определяемого
нами
автомата
нами
В [1] был получен
алгоритм
построения
аналогичного
COM,
наопределяемого
состояний
соответственно.
Будем
рассматривать
автомат
без
т.е.
Вавтомата,
[1]
был
получен
алгоритм
построения
автомата,
аналогичного
COM,
на– Q – язык
ВВЕДЕНИЕ Будем использовать
Будем
следующие
использовать
обозначения.
следующие
Пусть
обозначения.
Пусть
множество
состояний,
S
⊆
Q
и
F
⊆
Q
–
множества
стартовых
и
финальны
множестве
т.
н.
псевдоблоков
[2].
В
данной
статье
функция
переходов
δ
автомата
(1)
будет
иметь
вид
δ:
Q×∑
→
⊆
Q
и
F
⊆
⊆
Q
Q
и
–
F
множества
⊆
Q
–
мн
с
множество
множество
состояний,
состояний,
S
S
Будем использовать
Будем
следующие
обозначения.
следующие
Пусть
Пусть
языксостояний,
L =состояний,
L(K),Sиспользовать
где
–⊆Q
множество
Q
ии Fфинальных
Q
множество
состояний,
S– ⊆Q
⊆
и обозначения.
F ⊆стартовых
Q S–Sстартовых
множества
стартовых
и финм
множество
состояний,
S⊆и
Q⊆
F⊆
QQ
–множества
множества
стартовых
и
множество
множество
⊆ Q
SQ
F[2].
множество
и иF
Q
множества
–состояний,
состояний,
⊆
Q
F ⊆
истроить
финальных
Q финальных
– множества
с
В статье рассматривается
определенное
множестве множество
т. н. псевдоблоков
[2].и исходного
Вмножестве
данной
статье
мы автомата
будем
строить
т.автомата
н. псевдоблоков
Взаданного
данной
статье
мы
будем
COMдуг,
и функция
исходного
COM
конечного
конечного
(или
заданного
(или
регулярного
регулярного
языка).
языка).
переходов
δ
(1)
будет
иметь
вид
δ:
Q×∑
→
P
(Q),
а
не
δ:
Q×(∑
– множества
стартовых
финальных
состояний
соответственБудем
рассматривать
автомат
без
ε-переходов,
K = {Q, Σ, δ, S, F} K = {Q,
Σ,состояний
δ, S, F}
(1)
(1)
состояний
соответственно.
рассматривать
Будем
автом
на
(т.е
непосредственно
автомат
COM
–Будем
на
его
подмножестве
Kсоответственно.
= {Q,
Σ,
δ,и Будем
S,
F}
K (Q)
=состояний
{Q,
Σ,
δ,
S,соответственно.
F}
(1)
(1
состояний
соответственно.
Будем
рассматривать
автомат
безрассматрив
ε-переход
состояний
соответственно.
рассматривать
автомат
без
ε-переходов,
т.е.
∪
на блоках бинарного
отношения
#.
Дуги
этого
множества
{ε})
→
P
(Q),
где
P
–
множество
всех
подмножеств
множ
состояний
состояний
соответственно.
соответственно.
Будем
Будем
рассматривать
состояний
рассматривать
соответственно.
автомат
автомат
без
ε-переходов,
Будем
без
ε-переходов,
рассматривать
т.е.
т.е.
автом
нарассматривать
основе
одного
из
непосредственно автомат COM – на егонепосредственно
подмножестве
(на основе
одного из
COM
– на
его подмножестве
но. Будем(автомат
автомат
без ε-переходов,
т.е. функция
недетерминированный
недетерминированный
конечный
автомат
конечный
Рабина-Скотта
автомат
или,
Рабина-Скотта
иначе,
или,
иначе,
∪ {ε})
P (Q),
где
Pфункция
(Q)
–функция
множество
подмножеств
множества
Q.Pδ:будет
–→
недетерминированный
– недетерминированный
конечный
автомат
конечный
Рабина-Скотта
автомат
или,Рабина-Скотта
иначе,
или,
иначе
переходов
δвсех
автомата
(1)
будет
иметь
вид
δ:δвид
Q×∑
→
P (Q),
не
δ:иметь
Q×(∑
результатов
работы
[3]
доказать,
что
подм
функция
переходов
функция
переходов
δ можно
автомата
автомата
(1)
иметь
будет
вид
δ:
Q×
соответствует –всем
возможным– дугам
любого
недетермипереходов
δ
автомата
(1)
будет
иметь
Q×∑
→
Pа это
(Q),
δ
функция
переходов
δ
автомата
(1)
будет
иметь
вид
δ:
Q×∑
→
(Q),
а(1)
не
Q×(∑
in
out
δ
автомата
(1)
будет
иметь
вид
δ:
Q×∑
δ
автомата
→
P
(Q),
→
P
(1)
а
(Q),
не
будет
δ:
аане
Q×(∑
иметь
δ: δ:
Q×(∑
видаδ:неQ×
функция
функция
переходов
переходов
δ
автомата
функция
(1)
будет
переходов
иметь
вид
δ:
Q×∑
автомата
(1)
будет
иметь
вид
:
Q
P
(Q),
переходов
результатов работы [3] можно доказать,
что это работы
подмножество
является
результатов
[3] можно
доказать,
что
это
подмножество
является
L
(q)
и
L
(q)
обозначим
входной
и
выходно
Через
нированногоконечный
конечного
автомата,
определяющего
заданный
собственным
за
исключением
нескольких
«вырожденных»
с
автомат, конечный
определяющий
автомат,
регулярный
определяющий
язык
Lрегулярный
=определяющий
язык
Lрегулярный
Lout
L
(K),
где
Qгде
–P=(Q)
(K),
где
Q
–где
K
KL
in не
∪
∪
∪
конечный
автомат,
конечный
автомат,
определяющий
язык
регулярный
=
язык
L
=
L
L
(K),
где
Q
–
(K),
где
Q
{ε})
→
P
(Q),
–
множество
всех
подмножеств
множества
Q.
{ε})
→
P
(Q),
{ε})
→
P
P
(Q),
(Q)
где
–
множество
P
(Q)
–
множество
всех
подмножеств
всех
под
P
(Q),
где
P
(Q)
–
множество
всех
подмножеств
→
P{ε})
(Q)«вырожденных»
–всех
множество
множества
Q.
∪{ε})
{ε})
→
P ∪(Q),
где
– где
множество
подмножеств
множества
Q. –подмножеств
∪ «вырожденных»
∪ входной
собственным
за множества
исключением
нескольких
случаев
,P(Q)
а(Q),
именно
–всех
)Pмножество
{ε})
Pи
(Q),
→за
где
(Q),
P{ε})
где
(Q)
P–(Q)
–СВЕДЕНИЯ
множество
→
подмножеств
Pвсех
(Q),
где Pвсех
(Q)
множества
–подмножеств
множества
множество
Q.
всех
L K∪ →
(q)
LPисключением
(q)
обозначим
иподмножеств
выходной
языки
Через
), Q.
асостояния
именно
собственным
нескольких
случаев
регулярный язык. На
основе этого
дуг
2. ПРЕДВАРИТЕЛЬНЫЕ
2.определяетПРЕДВАРИТЕЛЬНЫЕ
СВЕДЕНИЯ
K Q.
множества
на
множестве
блоков.
Кроме
того,
мы
впервые получим
фор
in
out
in
in
out
out
множество
состояний,
множество
S ⊆ Q исостояний,
Fканоническому
⊆ Q
– множества
S ⊆ Q иисостояний,
Fстартовых
⊆
Qмножество
– in
множества
и
финальных
стартовых
и
финальных
множество
S
⊆
Q
и
состояний,
F
⊆
Q
–
множества
S
⊆
Q
и
F
стартовых
⊆
Q
–
множества
и
финальных
стартовых
и
финальных
q,
т.е.
языки,
определяемые
автоматами
(Q,
∑,
δ,
S,
{q})
и
in
out
in
out
был получен алгоритм
построения
автомата,
аналогичного
COM,
на
ся автомат
COM,
являющийся,
аналогично
in Кроме
out
out
in
out
(q)входной
иформулу
(q)
(q)
ивыходной
обозначим
(q) языки
обозначим
входной
ивход
вы
Lобозначим
LLиK
LK
Через
Через
(q)
и L(q)
(q)
обозначим
ивыходной
состояни
L для
Через
на множестве блоков. Кроме того, мы впервые
получим
формулу
описания
на множестве
блоков.
того,
мы
впервые
получим
для
описания
Kи
K
K
Kи
(q)
и
L
обозначим
входной
и
Через
L
L
(q)
L
(q)
входной
и
выходной
языки
сос
Через
L
(q)
и
L
обозначим
входной
выходной
языки
состояния
Через
L
L
L
L
L
L
(q)
и
(q)
и
(q)
обозначим
(q)
обозначим
входной
входной
(q)
выходной
и
и
выходной
(q)
языки
обозначим
языки
состояния
состояния
входной
и
вы
Через
Через
Через
K
K
Будем
использовать
Будем
использовать
следующие
следующие
обозначения.
иПусть
выходного
языков
произвольного
состояния
этог
K
K обозначения.
q, т.е.
языки,
определяемые
автоматами
(Q,Будем
∑,
δ,рассматривать
S,KПусть
{q})
и K(Q,
∑, т.е.
δ,без
{q},
F)
K
K
K
Kвходного
состояний
соответственно.
состояний
Будем
соответственно.
рассматривать
Будем
автомат
рассматривать
без
ε-переходов,
автомат
т.е.
без
ε-переходов,
т.е.
базисному
автоматам,
инвариантом
рассматриваемого
языка.
состояний
соответственно.
состояний
Будем
соответственно.
рассматривать
автомат
без
ε-переходов,
автомат
ε-переходов,
т.е
т. н. псевдоблоков [2]. В данной
статье
мы будемязыков
строить
входного
и выходного
произвольного
состояния
этогосоответственно.
автомата
– вязыки,
этом определяемые
языки
состояния
q, т.е.
автоматами
входного
и выходного
языков
произвольного
этого
автомата
–(Q,
этом
q, т.е. основной
языки,
q,состояния
т.е.
определяемые
языки,
определяемые
автоматами
автоматами
∑,
δ, (Q,
S,
q, т.е.q,языки,
определяемые
автоматами
(Q,
∑,
δ,
S,
{q})
ив{q})
(Q,(Q,
δ,этой
{q},
F{
иS,
состоит
результат
данной
статьи.
Из
В [1] былфункция
полученпереходов
алгоритмδфункция
построения
автомата,
аналот.е.
языки,
определяемые
автоматами
(Q,
∑,
δ,
S,
и∑,
(Q,
δ,фо
q,
т.е.
языки,
определяемые
(Q,
δ,S,вид
S,
{q})
и
(Q,
∑,
δ,
F)Q×(∑
q,переходов
т.е.
q,будет
языки,
т.е.
языки,
определяемые
определяемые
автоматами
автоматами
q,автоматами
т.е.
(Q,
языки,
∑,
(Q,
δ,
определяемые
∑,
S,∑,
δ,{q})
{q})
ине
(Q,
автоматами
и
∑,
(Q,(1)
δ,
∑,{q},
δ,
(Q,
{q},
F)
∑,
F)δ:∑,
δ,
S,
{
K
=
{Q,
Σ,
K
δ,
=
{Q,
F}
Σ,
δ,
S,
F}
(1)
соответственно.
→
P
(Q),
а
не
δ:
Q×(∑
→
P
(Q),
а
не
δ:
Q×(∑
автомата
переходов
(1)
будет
δ
иметь
автомата
вид
δ:
(1)
Q×∑
иметь
вид
δ:
Q×∑
,
,
S,
{q})
и
(Q,
,
,
{q},
F)
соответственно.
δ
автомата
(1)
будет
δ
иметь
автомата
вид
(1)
δ:
Q×∑
будет
→
иметь
P
(Q),
а
δ:
δ:
Q×∑
Q×(∑
→
P
(Q),
а{q},
не
функция
функция
переходов
и состоит (основной
даннойрассматриваемого
статьи.
Изосновной
этой формулы
очевидным
на основерезультат
одного изДля
венно автомат COM – на его подмножестве
и
состоит
результат
данной
статьи.
Из
этой
формулы
очевидным
языка
L
будем
обозначать
эквивалентный
ему
Зеркальный
автомат
для
заданного
автомата
(1)
будем
соответственно.
соответственно.
гичного COM, на множестве т. н. псевдоблоков [2]. В данной
соответственно.
образом
следует,
средиавтомата
прочего, эквивалентность
определяе
Зеркальный
автомат
для
заданного
(1)
будем
соответственно.
R
соответственно.
соответственно.
соответственно.
соответственно.
недетерминированный
недетерминированный
конечный
конечный
автомат
автомат
Рабина-Скотта
Рабина-Скотта
или,
иначе,
или,
иначе,
–Q.
Зеркальный
автомат
для
заданного
(1)
K
∪ {ε})строить
→
P это
(Q),непосредственно
где
P∪(Q)
{ε})
–среди
множество
→ P–прочего,
(Q),
гдевсех
Pэквивалентность
подмножеств
– множество
множества
всех
подмножеств
Q.
множества
Q.
∪–(Q)
{ε})
→
P∪ (Q)
{ε})
–среди
→
множество
P (Q),
всех
PRэквивалентность
(Q)
подмножеств
–автомата
множество
множества
всехбудем
подмножеств
Q.обозначать
множества
образом
следует,
определяемого
нами
автомата
образом
следует,
прочего,
определяемого
нами
автомата
~R где
~заданного
работы [3] статье
можно мы
доказать,
что
подмножество
является
R
будем
автомат
COM
– Pна(Q), где
R Зеркальный
Rавтомат
R
Зеркальный
автомат
для
заданного
для
автомата
авто
(1)
Зеркальный
автомат
для
заданного
автомата
(1)a)
будем
обозначать
K
–K
т.е.
K
=(Q,
å,
dF,
,для
F,
S),
где
dавтомата
(q,
если
обозначать
KRЗеркальный
=(Q,
∑,
δзаданного
,Зеркальный
S),
где
q'q'
∈
δRавтоматы
(q,
a)
если
иавтомата
только
т.е.
Lавтомат
L
.для
Будем
также
считать,
что
канонической
автомат
записью
Rи
R регуля
COM
иавтомат
исходного
конечного
автомата
(или
заданного
заданного
(1)
будем
Зеркальный
для
автомата
(1)
будем
обозначать
K–R – (1)е
–
Зеркальный
Зеркальный
автомат
автомат
заданного
для
заданного
автомата
автомата
(1)
автомат
будем
(1)
будем
для
обозначать
заданного
обозначать
K
Kобозначат
R
R
R
R
in
out
inавтомата
out
его нескольких
подмножестве
(на
основе
одного
из
результатов
работы
R (q, out
R
in
out
in
COM
и
исходного
конечного
(или
заданного
регулярного
языка).
COM
и
исходного
конечного
автомата
(или
заданного
регулярного
языка).
=(Q,
∑,
δ
,
F,
S),
где
q'
∈
δ
a)
если
и
только
если
q
∈
δ
(q',
a).
т.е.
K
)
м за исключением
«вырожденных»
случаев
,
а
именно
–
R
R
d
(q',
a).
Очевидно,
что
K
определяет
и
только
если
q
R L(K),
R
R
R R
R и L
конечный
автомат,
определяющий
определяющий
регулярный
регулярный
язык
=δ=(Q,
L∑,
где
(K),
Q∈ где
–δгде
Q
R(q)
(q)
обозначим
и автомат,
входной
(q) иобозначим
выходной
иобозначим
выходной
языки
состояния
L K (q)конечный
L K Через
Через L K (q) и L K Через
(q)Rт.е.
иR входной
(q)состояния
входной
обозначим
и
выходной
входной
языки
иL
выходной
L
Lязыки
Через
=(Q,
,язык
F,
S),L=
δRсостояния
где
F,
q'S),
(q,языки
q' a)
∈
если
δ–состояни
(q,
иa)тол
ес
т.е.
K
т.е.
KRязык
=(Q,
∑,
δ(q)
, ∑,F,
где
∈Lδ∑,
(q,
a)
только
если
qесли
∈
δq(q',
KRRт.е.
RL
R
R если
R
RK
R Rq'
.и,если
что
Rязыка
K
δS),
,K
S),
где
q'
и∈
только
δaR
рассматриваемого
L
обозн
для рассматриваемого
языка
L
∑,
δS),
,=(Q,
F,S),RS),
где
q'(q,
∈
δ(q,
(q,a)∑,
a)если
только
q(q,∈
δRесли
(q',
a).
т.е.
[3] можно доказать, что это
подмножество является
собственRK
=(Q,
=(Q,
∑,=(Q,
δ ∑,
, Очевидно,
F,
δKRследующие:
, RF,
где
q'где
∈
q'
δKRF,
∈Kопределяет
δa)=(Q,
если
и∈
δесли
только
,δF,
и(q,итолько
S),a)
если
где
если
q'
q если
∈будем
qδδRR(q',
∈
δRa)
a).
(q',
a).
и∈тол
т.е. Kт.е.
K KДля
т.е.
Rязык L .
ве блоков. Кроме того, мы впервые получим формулу для описания
R
R
R
R
RL .
R
определяет
язык
Очевидно,
что
K
язык
L R. язык
L.
Очевидно,
Очевидно,
что
K R определяет
что
K определяет
определяет
L{q})
.F)
Очевидно,
K
R
RS,
ным за исключением
нескольких
«вырожденных»
случаев),
Rавтоматами
R –
Rязык
множество
множество
состояний,
состояний,
S ⊆что
иRрассматриваемого
SОчевидно,
FK
⊆δ,
⊆что
Q
Qиопределяемые
–что
F
множества
⊆
Q
множества
стартовых
и∑,
и
финальных
рассматриваемого
языка
будем
эквивален
q, т.е.
языки,
определяемые
q, т.е.
языки,
автоматами
определяемые
δ,
автоматами
{q})
иДля
(Q,
∑,
{q},
{q})
F)
иKR(Q,
∑,L
δ,R стартовых
{q},
q,(Q,
т.е.∑,
языки,
определяемые
q,Q
т.е.
языки,
автоматами
S,
иLопределяет
(Q,
(Q,
∑,финальных
δ,
δ, S,
{q},
{q})
F)
∑, δ, {q}, F
определяет
язык
. обозначать
будем
обозначать
эквива~S,
определяет
язык
Очевидно,
K
определяет
определяет
язык
язык
LОчевидно,
.языка
Lи
. (Q,
Очевидно,
Очевидно,
Kчто
Для
рассматриваемого
языка
L Для
будем
обозначать
ему
,что
{s
иL L. .L что
=K (R,
∑,~δR, {sязык
L = (Q, ∑, δQэквивалентный
Q}, FQ) 2.
R}, FR).
выходного языков
произвольного
состоянияблоков.
этого автомата
–того,
в этом
ПРЕДВАРИТЕЛЬНЫЕ
СВЕДЕНИЯ
а именно
– соответственно.
на множестве
Кроме
мы
впервые
. .Будем
также
лентный
емурассматривать
канонической
автомат
записью
Lбез
Будем
автомат
записью
соответственно.
соответственно.
соответственно.
2. ПРЕДВАРИТЕЛЬНЫЕ
СВЕДЕНИЯ
состояний
состояний
соответственно.
соответственно.
Будем
Будем
рассматривать
автомат
автомат
без ε-переходов,
ε-переходов,
т.е. также
т.е. счи
2.канонической
ПРЕДВАРИТЕЛЬНЫЕ
~
~
~СВЕДЕНИЯ
получим
формулу
для
описания
входного
языков
рассматриваемого
языка
Lавтоматы
будем
обозначать
эквивалентный
ему
основной результат
данной
статьи.
Из
этой Для
формулы
очевидным
Lи .выходного
Lи
и.Будем
для рассматриваемого
языка
считать,
что
L
Будем
также
считать,
что
автоматы
канонической
автомат
записью
Будем
также
считать,
что
автомат
канонической
автомат
записью
R
R
использовать
следующие
обозначения.
Пусть
Для
рассматриваемого
языка
L
будем
обозначать
эквивалентный
ему
Рассмотрим
некоторые
определения
и
факты
из
[1–4],
используемые
в KR
R
–автомат
– автомата
Зеркальный
автомат
Зеркальный
для заданного
автомат
автомата
для заданного
(1) будем
автомата
обозначать
(1)Kбудем
обозначать
– δ:обозначать
Зеркальный
автомат
Зеркальный
для
заданного
автомата
дляQ×∑
заданного
(1)K→
будем
обозначать
(1)Q×(∑
Kбудем
Будем
использовать
следующие
обозначения.
Пусть
Будем
использовать
следующие
обозначения.
Пусть
произвольного
состояния
этого
автомата
–
в
этом
и
состоит
функция
функция
переходов
переходов
δ
автомата
δ
автомата
(1)
будет
(1)
иметь
будет
вид
иметь
δ:
вид
δ:
P
Q×∑
(Q),
→
а
не
P
(Q),
δ:
а
не
Q×(∑
L
следующие:
дует, среди прочего, эквивалентность
определяемого
нами
автомата
для
рассматриваемого
языка
L
следующие:
in
out
~
~
~ δR(q', a).
K и=δ(φ
S,)~
F}
R языка RL следующие:
R
R
R
R
R
Rдве
R{Q, Σ,
для рассматриваемого
∑,автомат
δстатьи.
, F,
где
=(Q,
q'автомат
∑,
∈формулы
δL
(q,
, .=
F,
a)
S),очевидесли
иS,
q'Будем
только
∈ δδRRсчитать,
(q,
если
a)=
qRгде
∈что
только
(q',
qсчитать,
т.е. KR =(Q,
т.е.S),KИз
иa).δ,
φесли
–qит.н.
данной
статье.
использовать
специальные
функции
основной
результат
данной
этой
=(Q,
∑,
, L
F,
S),
=(Q,
∑,
∈
δa).
,(q,F,
a)
S),(1)
если
где
q' только
∈ δ=R(q,
если
a)å, если
qавтоматы
∈
только
(q',FR).
∈ δR(q', a)
т.е.
K
т.е.
L∈
Будем
автоматы
канонической
записью
(R,
dR,
{sR},
(Q,
å,иδq'dQ,
{sQ},
FQ)
иииS,
L(1)
K
{Q,
Σ,где
δ,также
F}
. Kесли
Будем
что
канонической
записью
для
рассматриваемого
языка
Lтакже
следующие:
K
=если
{Q,
Σ,
δ,
F}
дного конечного
автомата
(или
заданного
регулярного
языка).
∪
∪
{ε})
→
P
{ε})
(Q),
→
где
P
P
(Q),
(Q)
где
–
множество
P
(Q)
–
множество
всех
подмножеств
всех
подмножеств
множества
множества
Q.
Q.
R
R
R
R
–
недетерминированный
конечный
автомат
Рабина-С
R
R
R
R
ным
образом
следует,
среди
прочего,
эквивалентность
опре~ что K определяет
Рассмотрим
некоторые
определения
и факты
из [1–4],
LK .конечный
определяет
язык
L=
Очевидно,
что
~
определяет
язык
L
определяет
язык
L . Рабина-Скотта
Очевидно,
K . (R,
Очевидно,
что
K
(Q, ∑, Очевидно,
δQ, языка
{sQ},язык
FLфункции
иразметки
∑, δR, {s
FR.конечный
). иначе,
L–=
недетерминированный
автомат
Рабина-Скотта
или,
состояний
автомата
(1),
помечающие
каждое
Q)следующие:
R},
– что
недетерминированный
автомат
или, состояние
иначе,
для
рассматриваемого
=
(Q,
∑,
δ
,
{s
},
F
)
и
=
L
~
Q
Q
Q
деляемого
нами
автомата
COM
и
исходного
конечного
автоin
in
out
out
используемые
данной
Будемииспользовать
две
спедля рассматриваемого
языка
следующие:
=
(Q,
∑,
δQ(q)
,в(K),
{s
},
Fстатье.
=
(R,
∑, δR, {s
конечный
автомат,
определяющий
регулярный
язык
Qвходной
Q)~входной
R}, LF
(q) иL
Lрассматриваемого
LL
(q)
(q)
иL
обозначим
обозначим
и выходной
и будем
выходной
языки
состояния
языки
состояния
Через L K
Через
in Qязыка
out
конечный
автомат,
определяющий
регулярный
язык
L
=
L
где
–
Для
L
обозначать
эквива
~
конечный
автомат,
определяющий
регулярный
язык
L
=
L
(K),
где
Q
–
K
K
K
мата (или заданного
регулярного
языка).
и
φ
)
–
т.н.
функции
разметки
состояциальные
функции
(φ
Рассмотрим
некоторые
определения
факты
из =
[1–4],
некоторыми
подмножествами
L = (Q, ∑, δQ
, {s~
}, FQ) L ибудем
и обозначать
(R, ∑,используемые
δсостояний
Для рассматриваемого
эквивалентный
Qязыка
R, {sR}, FR).L ви ему . А именно, для некоторого
множество
состояний,
S ⊆ Q некоторыми
и F ⊆ Q – множества
старт
ДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ
ний
автомата
(1),
каждое
состояние
Рассмотрим
некоторые
определения
и F)факты
=
(Q,
∑,
δ
,
{s
},
F
)
=∑,
(R,
δR∑,, и{s
},ииз
FF)
). {q},
L
множество состояний,
S
⊆
Q
и
F
⊆
Q
–
множества
стартовых
ипомечающие
финальных
in
out F∑,
множество
состояний,
S
⊆
Qи
и
Q(Q,
стартовых
финальных
Q
Q
Q
R{q},
Rδ,
Рассмотрим
некоторые
определения
и∑,(Q,
факты
исполб
~
q, т.е.
языки,
т.е.определяемые
языки, определяемые
автоматами
(Q,
δ,
{q})
δ, иS,
{q})
δ,(Q,
∑,
~q, специальные
~–S,множества
исостояний
φ
) –⊆ т.н.
данной
статье.
Будем
использовать
две
функции
(φзаписью
регулярного
Lавтомат
иавтоматами
некоторого
конечного
автомата
K={Q,
Σ,[1–4],
δ, S, что
F},
ПРЕДВАРИТЕЛЬНЫЕ
СВЕДЕНИЯ
и. Будем
. А именно,
длясчитать,
некотоподмножествами
L
Рассмотрим
некоторые
определения
и
факты
из
[1–4],
используемые
в
состояний
Будем
рассматривать
автомат
L . Будем языка
L соответственно.
также
авт
канонической
также
считать,
что
автоматы
и
канонической
автомат
записью
м использовать следующие обозначения.
Пусть соответственно. Будем рассматривать
состояний
без ε-переходов,
т.е.
состоянийавтомат
соответственно.
Будем рассматривать
автомат без ε-переходов, т.е.
Будем использовать
следующие
обозначения.
Пусть
соответственно.
соответственно.
in
рого
регулярного
языка
Loutи использовать
некоторого
конечногодве
автомата
данной
статье.
Будем
специальны
in
функции
разметки
состояний
автомата
(1),
помечающие
каждое
состояние
функция
δ[1–4],
автоматаиспользуемые
(1) будет
иметь вид δ:
задающего
этот язык,
определим
прямую
разметки
Рассмотрим
некоторые
определения
и
факты
из
в и→
данной
статье.
Будем
использовать
две
специальные
функции
(φQ×∑
φфункцию
)переходов
–этот
т.н.
данной
статье.
использовать
специальные
функции
для
рассматриваемого
языка
L
следующие:
K = {Q,
Σ, δ,
S, F}
(1)
→
(Q),
а(φ
не
δ:иL
Q×(∑
функцияБудем
переходов
δ автомата
(1) две
будет
иметь вид
δ: Q×∑
(1)
будет
иметь
вид
δ: Q×∑
→ P (Q),прямую
а не
функция
переходов
, δP,автомата
S,
F},
задающего
язык,
определим
K={Q,
для
рассматриваемого
языка
следующие:
R δ: Q×(∑R
–
–
Зеркальный
автомат автомат
для заданного
для
заданного
автомата
автомата
(1)
будем
(1)
обозначать
будем
обозначать
K
K
~Зеркальный
in
{ε})
→
P (Q) – множество
всех
подмножеств мно
~ конечный
– недетерминированный
out
L и (1), . помечающие
QQ
(Q)
следующим
образом.
Для
функцию
разметки
А
именно,
для
некоторого
некоторыми
подмножествами
состояний
→PPP(Q),
(Q)где
φφR∪},
рминированный конечный
автомат
Рабина-Скотта
иначе,
функции
состояний
состояние
K ::
∪ разметки
разметки
автомата
помеч
L=
(Q,статье.
∑, δPили,
,автомат
{s–Будем
},автомата
FРабина-Скотиподмножеств
=состояний
(R,
,множество
{s
F
).состояний
{ε})
→
P (Q),
где
всех
множества
Q.
∪Rфункции
функции
разметки
автомата
(1),
помечающие
и
) –каждое
т.н.
данной
использовать
две
специальные
функции
(φδq'Rin(q',
{ε})
→ PR~
(Q),
где
P∑,
(Q)δRR–каждое
всех подмножеств
множества
Q. φ R(1),
Q(Q)
Qмножество
Q)
RR
та или, иначе, конечный автомат, определяющий
регулярный
Q
и
q'
Q
множество
φ(q)
содержит
в
том
и
любого
q
∑,R δ=(Q,
, F,∑,S),
δLгде
, F,
q'
S),
∈
где
δ
(q,
q'
a)
∈
δ
если
(q,
a)
и
только
если
и
если
только
q
∈
если
q
∈
a).
δ
(q',∑,
a).δR, {sR
т.е. KR =(Q,
т.е.
K
in
out
=
(Q,
∑,
δ
,
{s
},
F
)
и
=
(R,
Q
Q
Q
in
~ автомата
автомат, определяющий
регулярный
язык
=
где состояний
Qконечного
–
L(K), out
in
LQKмножество
(q) и L K (q) φобозначим
входной иq'выходн
in K={Q,
outΣ,
регулярного
языка
L Lинекоторые
некоторого
S,иЧерез
F},∈входной
содержит
образом.
Для
любого
q(q)
∈δ,
Qнекоторого
q'
L
.Lвыходной
А
именно,
для
некоторыми
подмножествами
K (q) состояния
L Kследующим
(q) иОчевидно,
(q) обозначим
входной
состояния
Через L
Рассмотрим
определения
и иЧерез
факты
из
[1–4],
используемые
в ~и выходной
~
(q)
иLLRязыки
обозначим
языки
K разметки
функции
состояний
автомата
(1),
каждое
состояние
K
язык
.Kязык
LR. помечающие
Очевидно,
что
KR определяет
что
KRиопределяет
Вектор науки
ТГУ.
№ 4(14),
2010
30
некоторыми некоторыми
подмножествами
состояний L исостояний
. А именно,и для .н
подмножествами
L
состояний, S ⊆ Qзадающего
и F ⊆ Q – множества
стартовых
и финальных
язык,Будем
определим
прямую
функцию
разметки
q,
языки,
определяемые
(Q,
∑,
δ, S, {q})
in т.е.определения
out
Рассмотрим
некоторые
и иqавтоматами
факты
из
[1–4],
ис
в том
идве
только
том
входные
языки
состояний
и имеют
хотя
регулярного
и некоторого
конечного
автомата
K={Q,
Σ,
δ,
S,
F},
и
φ
)
–
т.н.
даннойэтот
статье.
использовать
специальные
функции
(φ
q, т.е.языка
языки, L
определяемые
автоматами
∑,
δ,случае,
S, определяемые
{q})
иесли
(Q,
∑,
δ,
{q},
F)
q, (Q,
т.е.
языки,
автоматами
(Q,
∑,
δ,
S,
{q})
(Q,
∑,
δ,
{q},
F) бы
~
соответственно. Будем рассматриватьнекоторыми
автомат без ε-переходов,
inт.е.
соответственно.
L
подмножествами
состояний
и
.
А
именно,
для
некоторого
регулярного
языка
L и некоторого
конечного автомата K={Q, Σ,
:общее
Q → Pслово,
(Q)
φ автомата
Kпрямую
соответственно.
одно
т.е. Будем
задающего
этот язык,состояний
определим
функцию
разметки
функции соответственно.
разметки
(1),
помечающие
каждое состояние
данной
статье.
использовать
две специальные функции
(φ
реходов δ автомата (1) будет иметь вид δ: Q×∑ → P (Q), а не δ: Q×(∑
Зеркальный автомат для заданного автомата
(1) буде
R
Зеркальный автомат для заданного
автомата
(1) будем
обозначать
K – автомата
in in
Зеркальный
автомат
для заданного
(1) будем обозначать KR –
in
in
регулярного языка L и некоторого конечного авт
Документ
Категория
Без категории
Просмотров
18
Размер файла
1 372 Кб
Теги
алгоритм, интеллекта, искусственного, табличная, имитация
1/--страниц
Пожаловаться на содержимое документа