中国计量学院学报
中國計量學院學報
중국계량학원학보
JOURNAL OF CHINA INSTITUTE OF METROLOGY
2007年
2期
127-130
,共4页
有穷自动机%数据结构%邻接链表%邻接矩阵
有窮自動機%數據結構%鄰接鏈錶%鄰接矩陣
유궁자동궤%수거결구%린접련표%린접구진
尽管邻接矩阵是有穷自动机的一种常用存储方法,但是,邻接矩阵并不适合存储所有类型的有穷自动机.原因是两个状态间可能有两条以上同方向的弧,而邻接矩阵只能记录两个状态间存在的一条弧.所以,有穷自动机的存储结构最好采用邻接链表来存储.将此数据结构应用于NFA转换为DFA的计算,将传统的子集法中状态转换矩阵,由三维数组降低为二维数组.
儘管鄰接矩陣是有窮自動機的一種常用存儲方法,但是,鄰接矩陣併不適閤存儲所有類型的有窮自動機.原因是兩箇狀態間可能有兩條以上同方嚮的弧,而鄰接矩陣隻能記錄兩箇狀態間存在的一條弧.所以,有窮自動機的存儲結構最好採用鄰接鏈錶來存儲.將此數據結構應用于NFA轉換為DFA的計算,將傳統的子集法中狀態轉換矩陣,由三維數組降低為二維數組.
진관린접구진시유궁자동궤적일충상용존저방법,단시,린접구진병불괄합존저소유류형적유궁자동궤.원인시량개상태간가능유량조이상동방향적호,이린접구진지능기록량개상태간존재적일조호.소이,유궁자동궤적존저결구최호채용린접련표래존저.장차수거결구응용우NFA전환위DFA적계산,장전통적자집법중상태전환구진,유삼유수조강저위이유수조.
