automata - 自动机和形式语言

Question

表明正则语言 L 的单词的反义词也是正则的

我对如何处理这个问题感到困惑，我已经被困了几个小时：对于一个单词 x，我们使用 x^r 来表示它的反面。对于语言 L，我们使用 L^r 来表示 {x^r 其中 x 在 L 的集合中}。证明如果 L 是正则的，那么 L^r 也是正则的

Answer 1

如果L是正则的，则存在一些生成它的正则语法。它总是可以表示为左正则文法或右正则文法。让我们假设它是左正则文法G_l（右正则文法的证明是类似的）。

这种语法有两种产生式；终止类型：

A -> a, where A is non-terminal and a is either a terminal or empty string (epsilon)

或链接类型：

B -> Ca, where B, C are non-terminals and a is a terminal

当我们将反向应用于常规语言时，我们基本上也将其应用于产生式的尾部（因为头部只是单个非终结符）。以后会证明的。所以我们得到了一个新的语法G_r，带有产生式：

A -> a, where A is non-terminal and a is either a terminal or empty string (epsilon)
B -> aC, where B, C are non-terminals and a is a terminal

但是，嘿，这是一个正则语法！所以它接受的语言也是正规的。

有一件事情要做 - 表明反转尾巴实际上做了它应该做的事情。我们将非常简单地证明它：

1. 如果L包含 \epsilon，则在 中存在产生式 'S -> \epsilon' G_l。由于我们不接触这样的作品，它也存在于G_r.

2. 如果Lcontains a，一个由单个终端组成的单词，那么它类似于上面

3. 如果Lcontains aZ，其中 a 是终结符，并且Z是语言中的一个单词，该语言是通过从 in 中的单词中切掉第一个终结符而构造的L，然后L^rcontains （因为链接产生式的更改）(Z^r)a。Z 也是一种正则语言，因为它可以通过从 中删除左产生式的第一个“级别”来构造G_l，这给我们留下了正则语法。

我希望它有所帮助。通过反转相关有限自动机的边缘并稍微改变接受和进入状态，还有一种可以说是更简单的方法。