構造一個有限自動機來證明L是正常的

Question

Considering a language L, let L′ be the set of all first halves of strings in L so that 

L′ ={x| for some y,|x|=|y|and xy ∈ L} 

Please prove that if L is regular, then L′ is also regular by constructing a finite 
automaton for L′. 

我在解決這個問題時遇到了一些困難。我已經看到了一些解決方案，但希望有人用外行的話來解釋這個問題應該如何解決。我從以下鏈接查看了問題11的解決方案：http://tuvalu.santafe.edu/~moore/theory/hw1solns.pdf。

根據我的理解，必須構造L的DFA和LFA的NFA，並且在L'內我們追蹤L的最終狀態以及最終狀態的向後路徑。我讚賞澄清。

Answer 1

對於此證明，您不必爲L構建DFA。您的前提是L是常規的，所以您知道存在DFA爲L。選擇任意一種，現在您可以通過運行L DFA並將其與其運行的副本並行運行，從而爲L'構建 NFA。