韋爾普，只是在沉思，但總的來說，生成與正則表達(dá)式匹配的隨機輸入對我來說是可行的，因為它對隨機性的定義足夠?qū)捤?，對正則表達(dá)式的定義足夠嚴(yán)格。我在考慮經(jīng)典的形式定義，該定義只允許（）| *和字母字符。

正則表達(dá)式可以映射到稱為有限自動機的形式機。這樣的機器是有向圖，具有一個稱為最終狀態(tài)的特定節(jié)點，一個稱為初始狀態(tài)的節(jié)點以及每個邊緣上的字母組成的字母。如果可以從初始狀態(tài)開始并遍歷圖形中遍歷每個字符標(biāo)記的一條邊并在最終狀態(tài)結(jié)束，則正則表達(dá)式會接受一個單詞。

可以構(gòu)建圖形，然后從最終狀態(tài)開始，然后向后遍歷隨機邊，以跟蹤路徑。在標(biāo)準(zhǔn)構(gòu)造中，圖中的每個節(jié)點都可以從初始狀態(tài)到達(dá)，因此您不必?fù)?dān)心會犯不可恢復(fù)的錯誤并需要回溯。如果達(dá)到初始狀態(tài)，請停止并讀取前進(jìn)的路徑。那是您正則表達(dá)式的匹配項。

但是，對于何時或是否達(dá)到初始狀態(tài)并沒有特別的保證。人們將必須弄清楚所生成的字符串在何種意義上是“隨機的”，以及您首先希望從該語言中獲取隨機元素的含義。

不過，也許這是思考該問題的起點！

既然我已經(jīng)寫了出來，在我看來，重復(fù)解析選擇以簡化正則表達(dá)式模式可能會更簡單，直到剩下一個簡單的字符串為止。查找模式中的第一個非字母字符。如果是*，請復(fù)制前幾項并刪除*。如果是|，則選擇保留或刪除其余項目。對于左括號，請執(zhí)行相同的操作，但要查看匹配的右括號后面的字符。如果先將正則表達(dá)式解析為樹表示形式，這樣會使paren分組結(jié)構(gòu)更易于使用，這可能會更容易。

對于擔(dān)心確定正則表達(dá)式是否實際匹配任何東西的人來說，這等同于停止問題：不，常規(guī)語言的行為非常好。您可以判斷是否有兩個正則表達(dá)式描述了同一組接受的字符串。您基本上是在上面制造機器，然后遵循一種算法來產(chǎn)生規(guī)范的最小等效機器。對兩個正則表達(dá)式執(zhí)行此操作，然后檢查生成的最小機器數(shù)量是否相等，這很簡單。