資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究TOC 中的歸納假設是什麼？
歸納法是數學中一個強大的工具。它是一種證明對所有自然數都成立的命題的方法。
假設 - 正式證明可以使用演繹證明和歸納證明。演繹證明由一系列語句組成，這些語句以邏輯推理的方式給出，以證明第一個或初始語句。初始語句稱為假設。
假設存在一個 k > 0，使得對於任何正則表示式 r，其中 0 < OP(r) < k，存在一個 NFA-s 使得 L(M) = L(r)。此外，假設 M 只有一個最終狀態。
歸納步驟
令 r 為一個具有 k + 1 個運算子（OP(r) = k + 1）的正則表示式，其中 k + 1 >= 1。
情況 1 - r = ri + r2
由於 OP(r) = k +1，因此 0<= OP(n)，OP(r2) <= k。根據歸納假設，存在非確定性有限自動機 (NFA-s) 機器 M1 和 M2，使得 L(Mt) = L(n) 和 L(M) = L(r2)。
此外，M1 和 M2 都只有一個最終狀態。我們可以構建如下所示的 M -
情況 2 - r = r1r2
由於 OP(r) = k+1，因此 0<= OP(r1)，OP(r2) <= k。根據歸納假設，存在 NFA-s 機器 M1 和 M2，使得 L(M1) = L(n) 和 L(M2) = L(r2)。
此外，M1 和 M2 都只有一個最終狀態。我們現在可以構建如下所示的 M -
情況 3 - r = ri*
由於 OP(r) = k+1，因此 0<= OP(ri) <= k。根據歸納假設，存在一個 NFA-s 機器 M1，使得 L(M1) = L(n)。
此外，M1 只有一個最終狀態。因此，我們可以如下構建 M -
更新於: 2021年6月12日
2K+ 次檢視
廣告