构造有限自动机证明 L 是正则的
Constructing a finite automaton to prove L is regular
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′.
我在解决这个问题时遇到了一些困难。我已经看到了一些解决方案，但希望有人通俗易懂地解释一下应该如何解决这个问题。我从以下 link 中查看了问题 11 的解决方案：http://tuvalu.santafe.edu/~moore/theory/hw1solns.pdf。
根据我的理解，必须构建 L 的 DFA 和 L' 的 NFA，并且在 L' 中我们跟踪 L 的最终状态以及从最终状态的向后路径。感谢您的澄清。
对于此证明，您不必为 L 构建 DFA。您的前提是 L 是正则的，因此您知道 存在 L 的 DFA。选择任何一个，现在您可以 构造 L' 的 NFA，通过 运行 您的 L DFA 平行于它的副本，向后运行。
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′.
我在解决这个问题时遇到了一些困难。我已经看到了一些解决方案，但希望有人通俗易懂地解释一下应该如何解决这个问题。我从以下 link 中查看了问题 11 的解决方案：http://tuvalu.santafe.edu/~moore/theory/hw1solns.pdf。
根据我的理解，必须构建 L 的 DFA 和 L' 的 NFA，并且在 L' 中我们跟踪 L 的最终状态以及从最终状态的向后路径。感谢您的澄清。
对于此证明，您不必为 L 构建 DFA。您的前提是 L 是正则的，因此您知道 存在 L 的 DFA。选择任何一个，现在您可以 构造 L' 的 NFA，通过 运行 您的 L DFA 平行于它的副本，向后运行。