插入正規語言

Question

假設我在字母表Σ下有常規語言L.當我在中間插入符號時，如何顯示語言L'仍然是常規語言？例如，L包含一個字符串w，它由兩個子字符串u和v（w = uv）組成，我想表明常規語言L'包含字符串uxv，其中x是插入的符號。

請注意，u和v不必具有相同的長度，並且x也使用相同的字母表Σ。

謝謝！

Answer 1

由於L是規則的，所以存在接受它的有限自動機A.製作兩份A的副本（A1和A2）。在A2中，使起始狀態不是初始狀態。對於A1中的每個狀態p，將一個轉換p - x - > p添加到A2中的相應狀態。

使用您的示例符號，現在A1讀取u，新的轉換讀取x和A2讀取v。