資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學構建用於所有長度迴文串的下推自動機
L = {ww’ | wcw’, w ∈ {0, 1}*}，其中 w’ 是 w 的逆序。
這是在字母表 {0,1} 上所有奇數和偶數長度迴文串的語言。
為了構建所有長度的迴文串，讓我們使用非確定性下推自動機 (NPDA)。
為了構建 wcw’，我們需要檢查字串是否為奇數長度，如果到達中間元素 'c'，則處理它並移動到下一個狀態，而無需對堆疊進行任何更改。
示例
給定的字串是 1 1 0 0 1 1 1 1 0 0 1 1
結果 - 接受
給定的字串是：1 0 1 0 1 0 1 0 1
結果 - 接受
狀態轉換圖如下：
步驟 1 - 接收到 0 或 1 時，將元素壓入堆疊頂部，並檢查輸入字串是否為偶數長度，如果是，則檢查它是否到達輸入字串的後半部分。
假設，如果輸入字串是奇數長度，則檢查它是否到達中間元素。
步驟 2 - 如果輸入字串是偶數長度並且到達前半部分的最後一個元素，則將該元素壓入堆疊頂部並進行 epsilon 移動到下一個狀態；或者，如果輸入字串是奇數長度，則在接收到元素 'c' 時，移動到下一個狀態，而無需對堆疊進行任何更改。
步驟 3 - 接收到一個元素時，檢查掃描的符號：如果掃描的符號是 '0' 並且堆疊頂部也包含 '0'，或者掃描的符號是 '1' 並且堆疊頂部也包含 '1'，則從堆疊頂部彈出該元素；否則，移動到死狀態。
重複步驟 3，直到字串為空。
步驟 4 - 檢查掃描的符號是否為 '$' 並且堆疊不包含任何元素，則移動到最終狀態；否則，移動到死狀態。
更新於：2021年6月15日
10K+ 次瀏覽
廣告