AFA
2020年9月3日

AFA M是五元组\((Q, \Sigma, q_0, g, F)\)。其中\(g : Q \times \Sigma \times B^Q \rightarrow B\).

定义\(g^{\ast} : Q \times \Sigma^{\ast} \times B^Q \rightarrow B\)为：

\(\displaystyle g^{\ast} (q, \varepsilon, v) = v_q\)
\(\displaystyle g^{\ast} (q, a w, v) = g (q, a, g^{\ast} (w, v))\)

其中\(g^{\ast} (w, v) (q) = g^{\ast} (q, w, v), q \in Q\)

定义f为下列条件定义的布尔向量v：

\(\displaystyle v_q = q \quad \operatorname{iff} \quad q \in F\)

则AFA接受的语言为\(L (M) = \{ \omega |g^{\ast} (q_0, w, f) = 1 \}\)

定理 1. AFA和DFA等价

证明. 设AFA M为\((Q, \Sigma, q_0, g, F)\)。首先构造一个DFA D接受M语言的逆。

设D=\((Q', \Sigma, q_0', \delta, F')\)，其中\(Q' = B^Q, q_0' = f\). \(F'\)为满足\(v_{q_0'} = 1\)的布尔向量v的集合.

转移函数如下定义：

\(\displaystyle \delta (q, a) = p \quad \operatorname{iff} \quad g (a, q) = p\)

其中g(a,q)(t)=g(t,a,q), forall t in Q.

可以证明\(M^R\)和D等价。又，因为正规语言对补封闭，可以构造\(D^R\)与M等价。