確定型有窮自動機

有窮自動機的每一步操作都是確定的,因此可稱為確定型有窮自動機。確定有窮自動機就是說當一個狀態面對一個輸入符號的時候,它所轉換到的是一個唯一確定的狀態。

基本介紹

  • 中文名:確定型有窮自動機
  • 外文名:deterministic finite automata
  • 適用範圍:數理科學
  • 類別:有窮級數模型
簡介,引入,定義,辨析,

簡介

引入

有窮自動機是一種有窮級數模型。它由一個讀頭和一條有窮長的紙帶所組成,紙帶被分割成有限個同樣大小的單元,每個單元中可以是空的,或寫有取自有窮字母表
上的一個字母,讀頭在每一時刻都對準一個單元,並具有一個確定的內部狀態,這些內部狀態構成一個有窮集
。其中指定一個(比如 q1)為初始狀態,另外,指定一個
作為終止狀態(或接受狀態)集。
讀頭每次只能向右移動一單元(而不能寫或抹),並且每次都必須向右移動。讀頭所取的內部狀態將由一個轉換函式 δ 所確定。具體地說,在一個有窮自動機 𝒜 工作時,當讀頭所指單元內符號為 ai,內部狀態為 qi 時,讀頭將向右移一單元並取新的內部狀態
於是,有窮自動機𝒜 可以形式地看成由字母表 A,內部狀態集 Q、開始狀態 q1、終止狀態集 F 及轉換函式 δ 所組成的一個五元組 𝒜=<A,Q,q1,F,δ> 。在紙帶上給定 A 上的一個字 δ,如約定讀頭指向 σ 最左邊的符號且以 q1 為開始狀態,𝒜 便可開始運行,當 𝒜 讀完 σ 的讀頭所取的內部狀態為接受狀態,則稱 𝒜 接受 σ ,否則便拒絕 σ 。所有被 𝒜 所接受的字組成的 𝒜 接受的語言 L(𝒜)={σ∈A*|𝒜 接受σ}。
美國邏輯學家、數學家克林(Kleene,S.C.)證明了一個語言可被某有窮自動機接受,若且唯若它為正規的,這個結論成為克林刻畫。
圖1.有窮自動機圖1.有窮自動機

定義

有窮自動機的每一步操作都是確定的,因此可稱為確定型有窮自動機。如果允許在每一步上讀頭的內部狀態可在幾個狀態中任取,即 δ 之值為內部狀態之集合(而不是一個內部狀態),這樣便得到非確定型有窮自動機。但是這兩類自動機接受的語言類是一致的。

辨析

確定有窮自動機就是說當一個狀態面對一個輸入符號的時候,它所轉換到的是一個唯一確定的狀態;
不確定有窮自動機是說當一個狀態面對一個輸入符號的時候,它所轉換到的可能不只一個狀態,可以是一個狀態集合。這就是兩者的主要區別。還有就是 DFA 的開始狀態是唯一的,而 NFA 的開始狀態是一個開始狀態集。

相關詞條

熱門詞條

聯絡我們