Представимость обобщенных регулярных языков стохастическими сетями Петри
|
ВВЕДЕНИЕ 4
1 ЦЕЛЬ И ПОСТАНОВКА ЗАДАЧ 7
2 ОБЗОР 8
2.1 Абстрактный стохастический автомат и вероятностный язык 8
2.2 Абстрактные R-нечеткие автоматы и языки 9
2.3 Стохастические сети Петри 11
2.4 Условия представимости R-языков в стохастических автоматах в терминах весовой функции 15
3 ПРЕДСТАВИМОСТЬ R-ЯЗЫКА СТОХАСТИЧЕСКИМИ СЕТЯМИ ПЕТРИ 17
3.1 Алгоритм построения 17
3.2 Пример 22
4 МЕТОД СЕТЕВОЙ ПОДСТАНОВКИ 25
4.1 Постановка задачи 25
4.2 Алгоритм построения 26
4.3 Пример 29
5 РЕАЛИЗАЦИЯ 33
5.1 Описание программы 33
5.2 Стохастический автомат 34
5.2.1 Ввод данных 34
5.2.2 Подсчет веса слова 35
5.3 Стохастическая сеть Петри 35
5.3.1 Преобразование из стохастического автомата 35
5.3.2 Подсчет веса слова 36
5.4 Полученные результаты 37
ЗАКЛЮЧЕНИЕ 40
СПИСОК ЛИТЕРАТУРЫ 41
ПРИЛОЖЕНИЕ
1 ЦЕЛЬ И ПОСТАНОВКА ЗАДАЧ 7
2 ОБЗОР 8
2.1 Абстрактный стохастический автомат и вероятностный язык 8
2.2 Абстрактные R-нечеткие автоматы и языки 9
2.3 Стохастические сети Петри 11
2.4 Условия представимости R-языков в стохастических автоматах в терминах весовой функции 15
3 ПРЕДСТАВИМОСТЬ R-ЯЗЫКА СТОХАСТИЧЕСКИМИ СЕТЯМИ ПЕТРИ 17
3.1 Алгоритм построения 17
3.2 Пример 22
4 МЕТОД СЕТЕВОЙ ПОДСТАНОВКИ 25
4.1 Постановка задачи 25
4.2 Алгоритм построения 26
4.3 Пример 29
5 РЕАЛИЗАЦИЯ 33
5.1 Описание программы 33
5.2 Стохастический автомат 34
5.2.1 Ввод данных 34
5.2.2 Подсчет веса слова 35
5.3 Стохастическая сеть Петри 35
5.3.1 Преобразование из стохастического автомата 35
5.3.2 Подсчет веса слова 36
5.4 Полученные результаты 37
ЗАКЛЮЧЕНИЕ 40
СПИСОК ЛИТЕРАТУРЫ 41
ПРИЛОЖЕНИЕ
Сети Петри (далее СП) являются инструментом моделирования и функционального анализа параллельных и распределенных вычислительных систем и процессов, с помощью которого можно наглядно представлять структуру и поведение таких систем [3, 4, 5, 8, 10]. Используя их можно естественно описывать синхронизацию, параллелизм, причинную зависимость и конфликт. Но СП без расширений не предоставляют возможности анализа количественных параметров системы, например, времени отклика или производительности.
Многие реальные процессы лучше описываются вероятностными моделями. Поэтому было разработано временное расширение СП, такое как стохастические сети Петри (ССП) [7, 12]. Данная модель количественного
анализа дискретных динамических систем была разработана в начале 1980-х годов, изначально она основана на концепции стохастических временных задержек. При этом переходам ССП сопоставляются условные вероятности их срабатывания или параметры распределения задержек срабатывания. Существует два вида ССП: с непрерывным временем [7, 12] и с дискретным временем [1, 2, 7, 11]. Обычно непрерывные модели в качестве временной области используют неотрицательные действительные числа, а дискретные — натуральные числа. В непрерывных моделях обычно используется экспоненциальное распределение вероятностей, в то время как в дискретных — геометрическое, что связано с замечательным свойством «забывчивости» таких распределений, заключающимся в том, что вероятность текущей смены состояний зависит только от вероятности предыдущей смены. Поэтому нет необходимости хранить информацию об истории функционирования, предшествующей последнему изменению состояний .
Стандартно анализ ССП проводится с использованием марковских процессов с дискретным множеством состояний, называемых цепями Маркова. Так, непрерывно-временной и дискретно-временной ССП возможно сопоставить соответственно цепь Маркова с непрерывным временем с дискретным временем. Эти цепи генерируются на основе ССП и анализируются с помощью хорошо разработанных алгоритмов и методик.
В непрерывно-временной ССП переходы срабатывают отдельно в моменты непрерывного времени. Данная модель имеет интерливинговую семантику, т. е. параллельные вычисления моделируются их чередованием. В дискретно¬временной ССП переходы срабатывают параллельно, в так называемых «шагах», в определенные моменты дискретного времени. Следовательно, эта модель имеет шаговую семантику. Параллельные вычисления интерпретируются этой семантикой как последовательность параллельных действий. Произвольные конечные распределения для дискретно-временной ССП позволяют вводить дискретное время, сохраняя при этом приемлемую анализируемость модели. Поэтому такая модель выглядит более перспективной как с точки зрения способа представления параллелизма, так и с точки зрения вычислительной сложности ее исследования.
Кроме этого в последние годы широко используется методология моделирования дискретных систем, основанная на использовании раскрашенных (цветных) сетей Петри - Coloured Petri Nets [6, 9]. Эта
методология является обобщением формализма обыкновенных сетей Петри на случай многих видов ресурсов и позволяет более эффективно моделировать сложные системы. В определение таких сетей добавляются несколько значимых компонент, описывающих более сложные по сравнению с обычными СП правила функционирования. В то же время структура сети - двудольный ориентированный мультиграф и основной принцип работы - изменение маркировок при срабатывании переходов, не являются принципиально отличающимися от обычных СП.
Исходя из вышеизложенного, можно обосновать актуальность ССП с точки зрения представления структурного взаимодействия компонент моделируемой системы и анализа последовательностей разрешенных переходов, срабатывания которых носят вероятностный характер. Поэтому исследование свойств представляемых ими языков имеет существенное значение. В то же время интересна и обратная задача - задача синтеза модели ССП, которая реализует заранее известные наборы последовательностей действий, носящих вероятностный характер.
В [12] показано сопоставление ССП и марковского процесса, а в [11] приведена теорема о том, что любой стохастический автомат задает марковский процесс. Кроме того, есть известный подкласс сетей Петри, называемый автоматными сетями, который порождает регулярные языки, как и класс конечных автоматов. С другой стороны в работах [13, 14] исследуется
представимость стохастическим автоматом регулярного обобщенного языка, задаваемого над полем вещественных чисел R. Там же приведены необходимые и достаточные условия, которым должен удовлетворять такой язык, чтобы он оказался обобщенным вероятностным языком и существовал представляющий его конечный стохастический автомат, а также алгоритм построения такого автомата.
Целью данной работы является исследование возможности представления обобщенного регулярного языка с помощью специально определенной «стандартной» формы стохастической раскрашенной сети Петри, полученной из стохастического автомата, порождающего этот язык.
Многие реальные процессы лучше описываются вероятностными моделями. Поэтому было разработано временное расширение СП, такое как стохастические сети Петри (ССП) [7, 12]. Данная модель количественного
анализа дискретных динамических систем была разработана в начале 1980-х годов, изначально она основана на концепции стохастических временных задержек. При этом переходам ССП сопоставляются условные вероятности их срабатывания или параметры распределения задержек срабатывания. Существует два вида ССП: с непрерывным временем [7, 12] и с дискретным временем [1, 2, 7, 11]. Обычно непрерывные модели в качестве временной области используют неотрицательные действительные числа, а дискретные — натуральные числа. В непрерывных моделях обычно используется экспоненциальное распределение вероятностей, в то время как в дискретных — геометрическое, что связано с замечательным свойством «забывчивости» таких распределений, заключающимся в том, что вероятность текущей смены состояний зависит только от вероятности предыдущей смены. Поэтому нет необходимости хранить информацию об истории функционирования, предшествующей последнему изменению состояний .
Стандартно анализ ССП проводится с использованием марковских процессов с дискретным множеством состояний, называемых цепями Маркова. Так, непрерывно-временной и дискретно-временной ССП возможно сопоставить соответственно цепь Маркова с непрерывным временем с дискретным временем. Эти цепи генерируются на основе ССП и анализируются с помощью хорошо разработанных алгоритмов и методик.
В непрерывно-временной ССП переходы срабатывают отдельно в моменты непрерывного времени. Данная модель имеет интерливинговую семантику, т. е. параллельные вычисления моделируются их чередованием. В дискретно¬временной ССП переходы срабатывают параллельно, в так называемых «шагах», в определенные моменты дискретного времени. Следовательно, эта модель имеет шаговую семантику. Параллельные вычисления интерпретируются этой семантикой как последовательность параллельных действий. Произвольные конечные распределения для дискретно-временной ССП позволяют вводить дискретное время, сохраняя при этом приемлемую анализируемость модели. Поэтому такая модель выглядит более перспективной как с точки зрения способа представления параллелизма, так и с точки зрения вычислительной сложности ее исследования.
Кроме этого в последние годы широко используется методология моделирования дискретных систем, основанная на использовании раскрашенных (цветных) сетей Петри - Coloured Petri Nets [6, 9]. Эта
методология является обобщением формализма обыкновенных сетей Петри на случай многих видов ресурсов и позволяет более эффективно моделировать сложные системы. В определение таких сетей добавляются несколько значимых компонент, описывающих более сложные по сравнению с обычными СП правила функционирования. В то же время структура сети - двудольный ориентированный мультиграф и основной принцип работы - изменение маркировок при срабатывании переходов, не являются принципиально отличающимися от обычных СП.
Исходя из вышеизложенного, можно обосновать актуальность ССП с точки зрения представления структурного взаимодействия компонент моделируемой системы и анализа последовательностей разрешенных переходов, срабатывания которых носят вероятностный характер. Поэтому исследование свойств представляемых ими языков имеет существенное значение. В то же время интересна и обратная задача - задача синтеза модели ССП, которая реализует заранее известные наборы последовательностей действий, носящих вероятностный характер.
В [12] показано сопоставление ССП и марковского процесса, а в [11] приведена теорема о том, что любой стохастический автомат задает марковский процесс. Кроме того, есть известный подкласс сетей Петри, называемый автоматными сетями, который порождает регулярные языки, как и класс конечных автоматов. С другой стороны в работах [13, 14] исследуется
представимость стохастическим автоматом регулярного обобщенного языка, задаваемого над полем вещественных чисел R. Там же приведены необходимые и достаточные условия, которым должен удовлетворять такой язык, чтобы он оказался обобщенным вероятностным языком и существовал представляющий его конечный стохастический автомат, а также алгоритм построения такого автомата.
Целью данной работы является исследование возможности представления обобщенного регулярного языка с помощью специально определенной «стандартной» формы стохастической раскрашенной сети Петри, полученной из стохастического автомата, порождающего этот язык.
В ходе производственной практики были выполнены следующие задачи:
1. Изучены результаты проведенных ранее исследований в области представления регулярного обобщенного ^-языка стохастическими автоматами.
2. Определены условия, которым должна удовлетворять ССП, чтобы она порождала заданный стохастическая ^-обобщенный язык.
3. Сформулирован алгоритм построения дискретно-временной раскрашенной ССП.
4. Доказана теорема о том, что префиксный язык ССП в условиях п.2,
построенной на основе графа стохастического автомата, совпадает с стохастическая ^-обобщенным языком, порождаемым этим
автоматом. Приведен пример.
5. Предложен метод «сетевой» подстановки для решения задачи
подстановки ^-обобщенного языка в другой ^-обобщенный язык вместо одного символа. Описан алгоритм построения обобщенной синхронной СП, порождающий результат подстановки ССП,
порождающих исходные языки. Приведен пример.
6. Реализован подсчет вероятности слова в языке, порождаемом стохастическим автоматом, и вероятности последовательности срабатываний в полученной ССП.
7. Проверена корректность работы программы на различных входных данных.
1. Изучены результаты проведенных ранее исследований в области представления регулярного обобщенного ^-языка стохастическими автоматами.
2. Определены условия, которым должна удовлетворять ССП, чтобы она порождала заданный стохастическая ^-обобщенный язык.
3. Сформулирован алгоритм построения дискретно-временной раскрашенной ССП.
4. Доказана теорема о том, что префиксный язык ССП в условиях п.2,
построенной на основе графа стохастического автомата, совпадает с стохастическая ^-обобщенным языком, порождаемым этим
автоматом. Приведен пример.
5. Предложен метод «сетевой» подстановки для решения задачи
подстановки ^-обобщенного языка в другой ^-обобщенный язык вместо одного символа. Описан алгоритм построения обобщенной синхронной СП, порождающий результат подстановки ССП,
порождающих исходные языки. Приведен пример.
6. Реализован подсчет вероятности слова в языке, порождаемом стохастическим автоматом, и вероятности последовательности срабатываний в полученной ССП.
7. Проверена корректность работы программы на различных входных данных.