資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用 C++ 構建用於語言 L = {an bm a(n+m) - n,m≥1} 的圖靈機
圖靈機 - 圖靈機是一種用於接受由 0 型文法生成的語言的單詞的裝置。圖靈機 (TM) 是一種數學模型，它由一條無限長的帶組成，帶被分成單元格，輸入在這些單元格上給出。它包括一個讀取輸入帶的磁頭。狀態暫存器儲存圖靈機的狀態。讀取輸入符號後，將其替換為另一個符號，其內部狀態發生變化，並且它從一個單元格向右或向左移動。如果 TM 達到最終狀態，則接受輸入字串，否則拒絕。
TM 可以正式描述為一個 7 元組 (Q, X, Σ, δ, q0, B, F)，其中 -
- Q 是有限的狀態集
- X 是帶字母表
- Σ 是輸入字母表
- δ 是轉移函式；δ : Q × X → Q × X × {左移，右移}。
- q0 是初始狀態
- B 是空白符號
- F 是最終狀態集
我們的目標是構建一個接受語言的圖靈機 TM
L= anbma(n+m) 其中 n,m>=1
讓我們舉一些 TM 可以接受的單詞的例子，
- abaa，n=1，m=1
- aabaaa，n=2，m=1
- abbaaa，n=1，m=2
- aaabaaaa，n=3，m=1
也就是說，n 個 a 後跟 m 個 b，然後再跟 n+m 個 a。n,m>=1
a 的最小數量始終為 3，b 為 1。當 n=m=1 時。
方法總結如下：
機器首先接受所有 n 個 a，然後接受所有 m 個 b。然後，隨著遇到更多 a，它開始刪除之前的輸入 b 和 a。最後，當沒有新的 a 並且磁頭到達第一個輸入字元時，這意味著所有字元都已正確處理。讓我們逐步按照輸入字串進行操作：
從狀態 q0 開始的轉換
δ (q0, a) → ( q1, x, R )。在狀態 q0，如果讀取的字元是 a，則轉換到狀態 q1，將其設為 x 並向右移動以指向字串中的下一個字元。
例如 - aabaaa → xabaaa（第一個字元變為 x，磁頭向右移動到下一個 a）
δ ( q0, b ) → ( q3, x, R )。在狀態 q0，如果讀取的字元是 a，則轉換到狀態 q3，將其設為 x 並向右移動以指向字串中的下一個字元。
例如 - babaaa…. → xabaaa….（第一個字元變為 x，磁頭向右移動到下一個 a）
這裡 x 用於表示第一個字元。
從狀態 q1 開始的轉換
δ ( q1, a ) → ( q1, a, R )。在狀態 q1，如果讀取的字元是 a，則保持在狀態 q1，並向右移動以指向字串中的下一個字元。
例如：xaabaaa… → xaabaaa…（對於其餘的 a，不做任何操作並向右移動）
δ ( q1, b ) → ( q2, b, R )。在狀態 q1，如果讀取的字元是 b，則保持在狀態 q1，並向右移動以指向字串中的下一個字元。
例如 - xaabaaa… → xaabaaa…（對於其餘的 b，不做任何操作並向右移動）
從狀態 q2 開始的轉換
δ ( q2, b ) → ( q2, b, R )。在狀態 q2，如果讀取的字元是 b，則保持在狀態 q2，並向右移動以指向字串中的下一個字元。
例如 - xaabbbaaa… → xaabbbaaa…（對於其餘的 b，不做任何操作並向右移動）
δ ( q2, z ) → ( q2, z, R )。在狀態 q2，如果讀取的字元是 z，則保持在狀態 q2，並向右移動以指向字串中的下一個字元。
例如 - xaabaazz… → xaabaazz…（對於其餘的 z，不做任何操作並向右移動）
δ ( q2, a ) → ( q3, z, L )。在狀態 q2，如果讀取的字元是 a，則將其設為 z，然後轉換到狀態 q3，並向左移動以指向字串中的上一個字元。
例如 - xaabaazz… → xaabazzz…（對於 a，用 z 替換並向左移動）
從狀態 q3 開始的轉換
δ ( q3, z ) → ( q3, z, L )。在狀態 q3，如果讀取的字元是 z，則保持在狀態 q3，並向左移動以指向字串中的上一個字元。
例如 - xaabzzzz… → xaabzzzzz…（對於 z，不做任何操作並向左移動）
δ ( q3, b ) → ( q2, z, R )。在狀態 q2，如果讀取的字元是 b，則將其設為 z 並轉換到狀態 q2，並向右移動以指向字串中的下一個字元。替換所有 b。
例如 - xaabzzzz… → xaazzzzz…（對於 b，用 z 替換並向右移動）
δ ( q3, a ) → ( q2, z, R )。在狀態 q2，如果讀取的字元是 a，則將其設為 z 並轉換到狀態 q3，並向右移動以指向字串中的下一個字元。替換所有 a。
例如 - xaazzzz… → xaazzzzz…（對於 a，用 z 替換並向右移動）
δ ( q3, x ) → ( q4, z, R )。在狀態 q2，如果讀取的字元是 x，則將其設為 z，然後轉換到狀態 q3，並向右移動以指向字串中的下一個字元。第一個符號已到達。
例如 - xzzzzzzz… → zzzzzzzz…（對於 x，用 z 替換並向右移動）
從狀態 q4 開始的轉換
δ ( q4, z ) → ( q4 z, R )。在狀態 q4，如果讀取的字元是 z，則保持在狀態 q4，並向右移動以指向字串中的下一個字元。現在所有字元都是 z。
例如 - zzzzzzzz… → zzzzzzzz…（對於所有 z，不做任何操作並向右移動）
δ ( q4, $ ) → ( qf, $ , R )。在狀態 q4，如果不再有字元，則到達末尾。轉換到最終狀態 qf。這意味著字串被接受。
例如 - zzzzzzzz$ → zzzzzzzz（對於字串的結尾，$ 不做任何操作並移動到最終狀態）
圖表顯示了圖靈機 -
輸入
aabaaa q0: aabaaa → q1: xabaaa → q1: xabaaa → q2: xabaaa → q3: xabzaa → q2: xazzaa q2: xazzaa → q3: xazzza → q3: xazzza → q3: xazzza → q2: xzzzzza → q2: xzzzzza q2: xzzzzza → q2: xzzzzza → q2: xzzzzza → q2: xzzzzzz → q3: xzzzzzz…….. q3: xzzzzzz → q3: xzzzzzz → q4: zzzzzzz → q4: zzzzzzz…….q4: xzzzzzz$ → qf: xzzzzzz$
到達 qf 意味著 aabaaa 被接受
2K+ 次瀏覽
