Реферат: Синтез комбинацонных схем и конечных автоматов, сети Петри

Сети Петри – наиболее удачный из существующих математический аппарат для моделирования, анализа, синтеза и проектирования самых разных дискретных систем с параллельно протекающими процессами.

Определение. Сетью Петри называется четвёрка элементов

C = (P, T, I ,O), (3.2.1)

где

P = { p1, p2,…,pn }, n > 0 (3.2.2)

множество позиций (конечное),

T = { t1, t2,…,tm }, m > 0 (3.2.3)

множество переходов (конечное),

I: T → P (3.2.4)

функция входов (отображение множества переходов во входные позиции),

O: T → P (3.2.5)

функция выходов (отображение множества переходов в выходные позиции).

Если pi I (tj) , то pi – входная позиция j - го перехода, если pi I (tj) , то pi – выходная позиция j - го перехода.

Для наглядного представления сетей Петри используются графы.

Граф сети Петри есть двудольный ориентированный мультиграф

G = (V,), (3.2.6)

где V = P U T , причём P ∩ T = Ш.

Исходя из графического представления сети Петри, её можно определить и так:

C = (P, T, A), (3.2.7)

где А – матрица инцидентности графа сети.

Определим понятие маркированной сети Петри – оно является ключевым для любой сети.

Маркировка μ сети Петри C = (P, T, I, O) есть функция:

N = μ(P), N N , (3.2.8)

отображающая множество позиций на множество натуральных чисел. Маркировку можно также определить как вектор:

μ = {μ1, μ2,…, μn} , (3.2.9)

где n = │P │, а μi N . Между этими определениями есть связь:

μi = μ (pi) (3.2.10)

На графе маркировка отображается ссответствующим числом точек в каждой позиции. Точки называются маркерами или фишками. Если фишек много (больше трёх), то их количество отображается числом.

Таким образом, маркированная сеть Петри представляет собой пятёрку элементов: