如何表明如果語言L是規則的，那麼L'是正則的？

Question

設L是任何正則語言和∈Σ。如何顯示語言L'= {uav | uv∈L}也是正常的嗎？

維基百科說，一種方法來證明它是把它引回到正規語言，但我不明白在這種情況下如何做到這一點。希望有人能幫助。

Answer 1

有很多方法可以顯示出來。我認爲構建DFA的論點特別容易可視化。

想象一下您的語言L的DFA。我們稱之爲M。想象一下，它在圖表上以圖表形式展開。現在，想象一下M的副本，並將其在M旁邊展開。叫它M'。

現在 - 從M，從國家的Mq添加一個新的過渡到相應狀態的M'q'。過渡是符號a。

現在，考慮啓動狀態爲M的開始狀態和接受狀態爲M'的接受狀態的集合機器。本機開始接受L中的字符串，然後接受中間某個地方的a，然後繼續從L中斷處繼續接受字符串。這是我們要去的語言，我們爲它定義了一個完全合理的NFA。由於NFA接受的任何語言都是正常的，我們的語言是正常的。