正则表达式 – 查找DFA的补码？

I know that to convert a DFA,M to the complement,M`,I just need to swap the initial accepting states and final accepting states.

它不是补充,但你正在做一些与语言相反的事情和regular languages are closure under reversal.

DFA的冲销

什么是反转语言？

语言L的反转(表示为LR)是由…组成的语言
所有字符串的颠倒

鉴于L是一些FA A的L(A),我们可以为LR构建一个自动机：

• reverse all edges (arcs) in the transition diagram

• the accepting state for the L^R automaton is the start state for A

• create a new start state for the new automaton with epsilon transitions to each of the accept states for A

注意：通过反转所有箭头和交换DFA的初始和接受状态的角色,您可以获得NFA.
这就是为什么我写FA(不是DFA)

补充DFA

Finding the complement of a DFA?

定义：语言的补语根据与Σ*(西格玛星)的集合差异来定义.即L’=Σ* – L.

而L的补码语言(L’)除了^中的字符串之外,所有字符串均来自Σ*(西格玛星).Σ*是字母表中的所有字符串.
Σ=语言符号集

To construct the DFA D that accepts the complement of L,simply convert
each accepting state in A into a non-accepting state in D and convert
each non-accepting state in A into an accept state in D.
(Warning! This is not true for NFA’s)

A是L的DFA,D是补码

注意：为了构建补充DFA,旧的DFA必须是一个完整的手段,所有这些都应该从每个状态(或换句话说δ should be a complete function)都可能出现.

Complement: reference with example

Complement DFA for Regular Expression (00+1)*

以下是DFA名为A：

但DFA并不是DFA完整版.过渡函数δ是部分定义的,但不适用于全域Q×Σ(从l1向上偏离q1的边缘).

其完整的DFA可以如下(A)：

在上述DFA中,定义了所有可能的事务(*对于每对Q,Σ*),δ在这种情况下是一个完整的函数.

Reff: to learn what is Partial Function.

可以通过将所有最终状态q0更改为不是最终状态来构建新的补充DFA D,反之亦然.

所以在补数q0变成非最终和q1,q2是最终状态.

现在,您可以使用ARDEN’S THEOREM and DFA给出补全语言的正则表达式.

在这里我正在直接写正则表达式：

(00 1)* 0(^ 1(1 0)*)

其中^是空符号.

一些有用的链接：
从here,通过我的个人资料,您可以在FA找到一些更有用的答案.另外,两种常规语言属性的良好链接：one,second