有限自動機系統

有限自動機系統(finite automaton system) 最基本的一種離散型系統.

它可由五元組定義為S _ (A,B,C, ",勸,其中A為輸入符號有限集合(輸入字母表);B為輸出符號有限集合(輸出字母表); C為有限狀態集合;": C X A->C為狀態遷移函式; }:C->B為輸出函式.用A‘或B‘分別表示A或B 中符號構成的符號串集合,則映射必可擴張為}' : C XA*->C,表示將a‘中輸入串逐步作用於C中某狀態而得到的最後狀態.有限自動機研究的基本問題是它如何接納輸入符號串Q* EA*,並把初態。。逐步轉換為串可EC’和輸出串b*任B*.由於通常把所有符號串集合的某一子集稱為(形式)語言,已經證明,有限自動機系統所能接納或識別的輸入符號串和生成的輸出符號串,只能是被稱為正規語言的較小的集合.上述必和幾的定義亦可改為由必和產定義.其中}:CXA->C的意義同前,而}:CXA->B 直接給出下一個輸出.前者亦稱為摩爾型自動機,後者則稱為米雷型自動機.

相關詞條

熱門詞條

聯絡我們