資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究構建正則表示式 C( A + B)+ 的 DFA 程式
在本文中，我們將討論如何為正則表示式 C(A + B)+ 構建確定性有限自動機 (DFA)。我們將首先了解問題和背後的理論，然後深入探討實現，最後透過一個相關的示例來演示其用法。
理解問題陳述
確定性有限自動機 (DFA) 是自動機理論（理論計算機科學的一個分支）中使用的一種計算理論模型。它是最簡單的自動機型別之一，也是編譯器和解析器研究中的一個基本概念。
這裡的任務是為正則表示式 C(A + B)+ 程式設計一個 DFA。此表示式可以解釋為“C”後跟一個或多個“A”或“B”。我們的目標是建立程式來檢查給定的輸入字串是否與該正則表示式匹配。
理論背景
DFA 由一組狀態和在輸入符號上這些狀態之間的轉換組成。它從初始狀態開始並讀取輸入符號。對於每個輸入符號，它都會轉換到一個新狀態，直到所有輸入符號都已讀取。當且僅當 DFA 結束於最終（或接受）狀態時，它才接受輸入。
在這種情況下，正則表示式 C(A + B)+ 的 DFA 可以視覺化如下：
起始狀態：q0
接受狀態：q2
轉換：
q0 在輸入“C”時轉到 q1
q1 在輸入“A”或“B”時轉到 q2
q2 在輸入“A”或“B”時保持在 q2
示例
現在讓我們用不同的程式語言實現這個 DFA。請注意，此程式僅適用於大寫“A”、“B”和“C”。
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
typedef enum { q0, q1, q2, q3 } State;
State getNextState(State currentState, char input) {
switch (currentState) {
case q0: return (input == 'C') ? q1 : q3;
case q1: return (input == 'A' || input == 'B') ? q2 : q3;
case q2: return (input == 'A' || input == 'B') ? q2 : q3;
default: return q3;
}
}
bool matchesRE(const char* s) {
State currentState = q0;
int len = strlen(s);
for (int i = 0; i < len; i++) {
currentState = getNextState(currentState, s[i]);
}
return currentState == q2;
}
int main() {
const char* test = "CABAB";
printf("%s\n", matchesRE(test) ? "Matches Regular Expression" : "Does not match Regular Expression");
return 0;
}
輸出
Matches Regular Expression
#include <iostream>
#include <string>
using namespace std;
enum State { q0, q1, q2, q3 };
State getNextState(State currentState, char input) {
switch (currentState) {
case q0: return (input == 'C') ? q1 : q3;
case q1: return (input == 'A' || input == 'B') ? q2 : q3;
case q2: return (input == 'A' || input == 'B') ? q2 : q3;
default: return q3;
}
}
bool matchesRE(string s) {
State currentState = q0;
for (char c : s) {
currentState = getNextState(currentState, c);
}
return currentState == q2;
}
int main() {
string test = "CABAB";
cout << (matchesRE(test) ? "Matches Regular Expression" : "Does not match Regular Expression") << endl;
return 0;
}
輸出
Matches Regular Expression
public class Main {
enum State { q0, q1, q2, q3 }
static State getNextState(State currentState, char input) {
switch (currentState) {
case q0:
return (input == 'C') ? State.q1 : State.q3;
case q1:
return (input == 'A' || input == 'B') ? State.q2 : State.q3;
case q2:
return (input == 'A' || input == 'B') ? State.q2 : State.q3;
default:
return State.q3;
}
}
static boolean matchesRE(String s) {
State currentState = State.q0;
for (char c : s.toCharArray()) {
currentState = getNextState(currentState, c);
}
return currentState == State.q2;
}
public static void main(String[] args) {
String test = "CABAB";
System.out.println(matchesRE(test) ? "Matches Regular Expression" : "Does not match Regular Expression");
}
}
輸出
Matches Regular Expression
class State:
q0, q1, q2, q3 = range(4)
def get_next_state(current_state, input):
if current_state == State.q0:
return State.q1 if input == 'C' else State.q3
elif current_state == State.q1:
return State.q2 if input == 'A' or input == 'B' else State.q3
elif current_state == State.q2:
return State.q2 if input == 'A' or input == 'B' else State.q3
else:
return State.q3
def matches_re(s):
current_state = State.q0
for c in s:
current_state = get_next_state(current_state, c)
return current_state == State.q2
test = 'CABAB'
print('Matches Regular Expression' if matches_re(test) else 'Does not match Regular Expression')
輸出
Matches Regular Expression
測試用例
讓我們使用字串“CABAB”作為示例。此字串以“C”開頭，後跟一系列“A”和“B”。因此，它與正則表示式 C(A + B)+ 匹配，程式的輸出將為：“與正則表示式匹配”。
結論
在本文中，我們仔細研究了計算的理論模型 DFA 及其在驗證正則表示式中的應用。我們專注於正則表示式 C(A + B)+ 並建立了一個 C++ 程式來檢查輸入字串是否與該正則表示式匹配。我們希望本次討論能提供資訊，並幫助您更好地理解 DFA 及其在 C++ 中的實現。
752 次檢視
