韋爾普，只是在沉思，但總的來說，生成與正則表達式匹配的隨機輸入對我來說是可行的，因為它對隨機性的定義足夠寬松，對正則表達式的定義足夠嚴格。我在考慮經典的形式定義，該定義只允許（）| *和字母字符。

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

可以構建圖形，然后從最終狀態開始，然后向后遍歷隨機邊，以跟蹤路徑。在標準構造中，圖中的每個節點都可以從初始狀態到達，因此您不必擔心會犯不可恢復的錯誤并需要回溯。如果達到初始狀態，請停止并讀取前進的路徑。那是您正則表達式的匹配項。

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

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

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

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