regular-language - 你如何证明有序语言是正规的？

Question

我想知道如何证明具有顺序约束的语言是规则的。例如，如果您有 Σ = {1,2,3,4,5} 其中 L（Σ* 的子集）= (a1,a2,...an) 使得 an+1 大于 an你证明这是一种常规语言？

例如 α = (1,3,5) 会被接受，但 α = (1,4,5,2) 不会。

Answer 1

任何可以被 DFA（确定性有限自动机）识别的语言都是正则的。要证明您描述的语言是常规语言，您只需证明存在识别该特定语言的 DFA。

请记住，Σ 是有限的。如果我正确理解了语言的约束，一个有效的结构将有一个起始状态（接受或不接受，取决于你是否想在你的语言中包含 ε），对于 Σ 中的每个符号都有一个接受状态和一个拒绝状态. 如果当前状态是起始状态或对应于“较小”符号，则转换函数应导致与当前输入符号对应的状态，否则为拒绝状态。

也可以使用快捷方式-每种有限语言都是常规的，如果我正确理解了您描述的语言的约束，它显然是有限的（因为 Σ 是有限的）。这简单地意味着语言也是规则的。