資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究解釋有限自動機和正則表示式之間的關係。
為了理解有限自動機 (FA) 和正則表示式 (RE) 之間的關係，我們需要理解這些術語。讓我們從瞭解什麼是正則表示式開始。
正則表示式
正則表示式是一種用於描述語言並被有限自動機接受的語言。正則表示式是表示任何語言的最有效方法。令 Σ 為表示輸入集的字母表。
Σ 上的正則表示式可以定義如下：
- Φ 是一個正則表示式，表示空集。
- ε 是一個正則表示式，表示集合 {ε}，稱為空字串。
- 對於 Σ 中的每個 'a'，'a' 是一個正則表示式，表示集合 {a}。
- 如果 r 和 s 是表示語言的正則表示式。
- 分別為 L1 和 L2，則：
- r+s 等價於 L1 U L2 並集
- rs 等價於 L1L2 連線
- r* 等價於 L1* 閉包
r* 被稱為 Kleen 閉包或閉包，表示 r 的無限次出現。
現在，讓我們瞭解有限自動機。
有限自動機
有限自動機是一種抽象的計算裝置。它是具有離散輸入、輸出、狀態和一組狀態轉換的系統的數學模型，這些轉換在來自字母表 Σ 的輸入符號上發生。
有限自動機的形式化定義
有限自動機定義為一個 5 元組
M=(Q, Σ, δ,q0,F)
其中：
- Q：稱為狀態的有限集。
- Σ：稱為字母表的有限集。
- δ：Q × Σ → Q 是轉換函式。
- q0 ∈ Q 是起始或初始狀態。
- F：最終或接受狀態。
現在我們已經瞭解了這些術語，讓我們瞭解它們之間的關係。
關係
FA 和 RE 之間的關係如下：
上圖說明了將
- RE 轉換為帶有 epsilon 移動的非確定性有限自動機 (NFA) 很容易。
- 帶有 epsilon 移動的 NFA 轉換為不帶 epsilon 移動的 NFA。
- 不帶 epsilon 移動的 NFA 轉換為確定性有限自動機 (DFA)。
- DFA 可以很容易地轉換為 RE。
更新於：2021 年 6 月 12 日
11K+ 次瀏覽
廣告