Petri網(wǎng)表征語(yǔ)言和可達(dá)性分析.pdf

1、Petri網(wǎng)的可達(dá)性是Petri網(wǎng)的重要性質(zhì)，其判定問(wèn)題在Petri網(wǎng)理論中是一個(gè)重要課題。本文對(duì)Petri網(wǎng)的可達(dá)標(biāo)識(shí)集做了一些分析，主要內(nèi)容包括以下幾個(gè)方面：
　　1)提出了Petri網(wǎng)的表征語(yǔ)言的概念，證明了任意Petri網(wǎng)都具有一個(gè)上下文有關(guān)語(yǔ)言為其表征語(yǔ)言，并找出了幾種具有正規(guī)的表征語(yǔ)言的Petri網(wǎng)。
　　定義了標(biāo)識(shí)向字符串的映射函數(shù)，從而將Petri網(wǎng)的標(biāo)識(shí)映射為由庫(kù)所組成的串，將Petri網(wǎng)的可達(dá)標(biāo)識(shí)集映射為

2、這些串的集合，稱(chēng)這個(gè)集合為網(wǎng)系統(tǒng)的表征語(yǔ)言，顯然一個(gè)網(wǎng)系統(tǒng)的表征語(yǔ)言不是唯一的。表征語(yǔ)言描述了網(wǎng)系統(tǒng)的可達(dá)標(biāo)識(shí)集，即網(wǎng)系統(tǒng)的狀態(tài)空間。
　　有界網(wǎng)系統(tǒng)和公平網(wǎng)系統(tǒng)都存在正規(guī)的表征語(yǔ)言；如果一個(gè)網(wǎng)系統(tǒng)只有一個(gè)本原可重復(fù)向量，那么它也具有正規(guī)的表征語(yǔ)言。
　　2)給出了表征語(yǔ)言為正規(guī)語(yǔ)言的網(wǎng)系統(tǒng)的可達(dá)性判定方法。
　　本文提出了等價(jià)的表征語(yǔ)言的概念。對(duì)正規(guī)表達(dá)式的運(yùn)算規(guī)則做了擴(kuò)充，使得任意的正規(guī)表達(dá)式都可以轉(zhuǎn)化為另一個(gè)新的

3、表達(dá)式，新的表達(dá)式中不含括號(hào)運(yùn)算且它的各個(gè)加項(xiàng)都不含嵌套的閉包運(yùn)算，新的表達(dá)式生成的語(yǔ)言和原來(lái)的表達(dá)式生成的語(yǔ)言能夠表征同一個(gè)網(wǎng)系統(tǒng)。最后給出了對(duì)具有正規(guī)的表征語(yǔ)言的Petri網(wǎng)進(jìn)行可達(dá)性判定的方法。
　　3)給出了Petri網(wǎng)死標(biāo)識(shí)可達(dá)性判定的方法。
　　如果一個(gè)Petri網(wǎng)Σ1具有死標(biāo)識(shí)，則存在一組Petri網(wǎng)，這些Petri網(wǎng)和Σ1具有相同的庫(kù)所集且初始標(biāo)識(shí)為空標(biāo)識(shí)，這些網(wǎng)的可達(dá)標(biāo)識(shí)集的并集DM等于Σ1的基網(wǎng)的所有死標(biāo)