关闭常规语言

Question

a）让 $ l $ 是常规语言。根据定理，有一个接受语言的DFA。

很快描述了如何将DFA更改为NFA，接受 $ l ^ r $ ，其中R是反向的。

不需要编写如何建立正式或证明或正确性。

b）true或false：如果 $ l $ 不是常规的，则 $ l ^ r $ 不是常规

我的解决方案：

a）首先因为我们想要反转接受状态将成为开始并且拒绝状态将接受，也将边缘的方向改为对立面的一侧。 但是当谈到改变它到NFA时，我有点卡。

b）我认为它是真的，因为如果它的常规当然 $ l ^ r $ 将是常规的，它是真的。

这是a和b的方式？

Answer 1

a）

首先因为我们想要反转接受状态将成为开始，拒绝状态将接受，也将边缘的方向改为对立面。

你几乎在那里。如果您在原始DFA中有多个接受状态，会发生什么？这就是您需要NFA功能转换它们的地方。

这是一个扰流板，以防你想检查你的答案：设计一个dfa和它在计算机上的反向.se

b）

你的答案是真的，尽管你可能想要更仔细的话语来短语。我们想证明“如果 $ l $ 不是常规的， $ l ^ r $ 不是常规的” 。所以，让 $ l $ 不常规。如果 $ l ^ r $ 是常规的，所以 $（l ^ r）^ r= l $ ，这是一个矛盾。因此， $ l ^ r $ 不是常规的。