資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究區分有限自動機和圖靈機
在瞭解有限自動機 (FA) 和圖靈機 (TM) 之間的區別之前，讓我們先了解一下這些概念。
有限自動機
有限自動機是一種抽象的計算裝置
它是一個系統的數學模型，具有離散的輸入、輸出、狀態和狀態之間的轉換集，這些轉換是在來自字母表 Σ 的輸入符號上發生的。
有限自動機表示
在計算理論 (TOC) 中，FA 可以表示為以下形式：
圖形 (狀態轉換圖)
表格 (狀態轉換表)
數學 (狀態轉換函式)
有限自動機的形式化定義
有限自動機是一個五元組
M=(Q, Σ, δ,q0,F)
其中，
Q - 有限集稱為狀態
Σ - 有限集稱為字母表
δ - Q × Σ → Q 是狀態轉換函式
q0 ε Q 是起始狀態或初始狀態
F - 結束狀態或接受狀態
圖靈機
圖靈機比有限自動機和下推自動機都強大。它們與我們構建的任何計算機一樣強大。
圖靈機的形式化定義
圖靈機可以正式描述為七元組 (Q,X, Σ,δ,q0,B,F)
其中，
Q 是一個有限的狀態集
X 是帶字母表
Σ 是輸入字母表
δ 是一個狀態轉換函式：δ:QxX→QxXx{左移，右移}
q0 是初始狀態
B 是空白符號
F 是結束狀態。
差異
有限自動機和圖靈機之間的主要區別如下：
| 序號 | 有限狀態機 | 圖靈機 |
|---|---|---|
| 1 | 有限狀態機描述正則語言類別。 | 圖靈機描述更大類別的語言，即遞迴可列舉語言類別。 |
| 2 | 有限狀態機描述一類較小的語言，其中不需要記憶體。 | 圖靈機是計算機的數學描述，並且接受比 FSM 更多的語言類別。 |
| 3 | 有限狀態機的計算能力低於圖靈機。 | 圖靈機的計算能力高於 FSM |
| 4 | 有限狀態機只是一組狀態和轉換。它唯一的儲存是它所處的狀態。因此，記憶體狀態的數量是……有限的。 | 圖靈機是一個有限狀態機加上一個磁帶儲存器。每次轉換都可能伴隨著對磁帶的操作（移動、讀取、寫入）。無論程式的大小如何，它所有可能的配置都是任意大的；它擴充套件到無限大。 |
更新於：2021年6月15日
5K+ 瀏覽量
廣告