finite-automata - 这种语言是正规的吗？

Question

对于每个 n 接受 n(n-1)(n-2)/6+n(n-1)/2+1 多个 {0,1}^n 的语言是常规语言吗？

我有一个问题要绘制那些语言的 dfa，但我什至不确定它是否是常规语言。

Answer 1

这听起来像家庭作业，我猜问题是：绘制一个完全接受 n(n-1)(n-2)/6+n(n-1)/2+1 个长度为 n 的单词的 DFA（超过字母表 {0,1}）。让我们将自动机构造为两个 DFA 的交集。

第一个自动机接受长度为 n 的单词。这很容易——有 n+1 个状态链。第一个状态是初始状态，只有最后一个状态是接受，每个状态都有一个标记为 0,1 的转换到链中的下一个状态。接受状态没有传出转换。

第二个自动机接受有一个、两个或三个 1 的单词。此外，非常简单——我们需要 4 个状态：q_0、q_1、q_2、q_sink。状态 q_0 是初始状态，状态 q_0,q_1,q_2 正在接受，它们有一个带 0 的自循环。有转换 q_0 --1--> q_1 --1--> q_2 --1-- > q_sink。最后，q_sink 被拒绝，它有一个 0,1 的自循环。

为了构造自动机的交集，我们需要两个自动机的乘积。这是一个通用的结构，也不是很难。