資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學設計一個圖靈機 (TM)，要求接受a和b數量相等的字串，並且必須以a開頭。
圖靈機 (TM) 比有限自動機 (FA) 和下推自動機 (PDA) 都強大。它們與我們製造的任何計算機一樣強大。
圖靈機的形式化定義
圖靈機可以形式化地描述為七元組
(Q,X, Σ,δ,q0,B,F)
其中：
Q 是有限的狀態集
X 是帶字母表
Σ 是輸入字母表
δ 是轉移函式：𝛿:QxX→QxXx{左移，右移}
q0 是初始狀態
B 是空白符號
F 是最終狀態。
圖靈機 (TM) 是一種數學模型，它由一條無限長的磁帶組成，磁帶被分成單元格，輸入就寫在這些單元格上。它有一個磁頭用於讀取輸入磁帶。狀態暫存器儲存圖靈機的狀態。
讀取輸入符號後，它被替換為另一個符號，其內部狀態發生改變，並且它從一個單元格移動到右邊或左邊。如果圖靈機到達最終狀態，則接受輸入字串，否則拒絕。
圖靈機具有讀/寫頭。因此我們可以在磁帶上寫入。
現在，讓我們構造一個圖靈機，它接受a和b數量相等的字串，
它生成的語言是L ={ anbn| n>=1}，該語言接受的字串是：
L= {ab, aabb, aaabbb, aaaabbbb,………}
示例
考慮n=3，所以a3b3，磁帶看起來像：
B= 空白
我們需要將每個 'a' 轉換為 X，每個 'b' 轉換為 Y。如果圖靈機包含數量相等的 X 和 Y，則它到達最終狀態。
步驟 1 − 將初始狀態設為 q0。此狀態將 'a' 替換為 X 並向右移動，現在狀態從 q0 更改為 q1，因此轉移函式為：
δ(q0, a) = (q1,X,R)
步驟 2 − 向右移動直到看到空白符號。
δ(q1, a) = (q1,a,R)
δ(q1, b) = (q1,b,R)
到達空白符號 B 後，向左移動並將狀態更改為 q2，因為我們需要將最後一個 'b' 更改為 Y。
δ(q1, B) = (q2,B,L) //1st iteration δ(q1, Y) = (q2,Y,L) // remaining iterations
步驟 3 − 當我們看到符號 'b' 時，將其替換為 Y 並將狀態更改為 q3 並向左移動。
δ(q2, B) = (q3,Y,L)
步驟 4 − 向左移動直到到達符號 X。
δ(q3, a) = (q3,a,L) δ(q3, b) = (q3,b,L)
當我們到達 X 時，向右移動並將狀態更改為 q0，然後開始下一次迭代。
將每個 'a' 和 'b' 替換為 X 和 Y 後，狀態從 q0 更改為 q4。
δ(q0, Y) = (q4,Y,N)
N 表示不動。
| X | X | X | Y | Y | Y | B | B | ........................... |
q4 是圖靈機的最終狀態，q0 是初始狀態，中間狀態是 q1、q2、q3。
狀態轉換圖
狀態轉換圖如下：
3K+ 次檢視
