Abstract
正如大家所知的,通訊越來越受到重視,人與人的溝通只需透過網路,在電 腦領域中,通訊協定越來越受到重視,也越來越重要,但目前對於通訊協定 測試,卻較容易被人忽視.大家對於好不容易寫出來的通訊軟體,都用較少 的心力去注意,使得整個程式有錯誤卻不知道,直到引起問題才想辦法解 決.有限狀態機是一種可以模擬通訊協定及程式的模型,有許多現有的理論 可以用在上面,這些理論可以用來產生測試序列,並可提出完整的證明,這 些因素使得在有限狀態機模型下作理論研究的幫助相當大,有限狀態機可 分為一群狀態,傳輸邊,輸出入訊號,而唯一測試序列是指對一個狀態輸入 一連續的輸入訊號序列,所能引起的唯一輸出序列,我們稱此序列為唯一測 試序列.此序列可用來測試有限狀態機上的狀態,如此一來我們便可以來測 試構架於有限狀態機上的通訊協定.若有限狀態機有多餘的狀態,普通的測 試序列並無法偵測到,有人便提出用測試序列的階層架構來解決,但是卻無 一個好的演算法來產生,後來有人用數學的定理證明出此方法的正確性.但 是原來的測試序列龐大且重複處太多.於是需要一個演算法來產生測試序 列.本篇論文所提出的演算法有下列幾種特性,第一,必須產生從起始狀態 到目前狀態的最短路徑.第二,必須將多餘的測試序列覆蓋(overlapped), 即不會產生重複的測試序列.第三,必能產生測試序列的階層架構,並有一 個不錯的資料結構可以用以分析此測試序列.但此演算法所產生的測試序 列尚未到最佳化的程度.