为什么{a ^ n a ^ n |n>=0}是规则的?

是,语言{a ⁿ 一 ⁿ |n>=0} 是常规语言 。为了证明某种语言是正则的,可以绘制其dfa/正则表达式。您可以按如下方式驱动该语言:

因为“ a n a n 对于 n >= 0 “与”相同 a 2n 对于n>=0”,这是“偶数个符号的所有字符串竞赛的集合” a " 那是常规的 -此的正则表达式为 (aa)* .

注意,正则表达式仅适用于正则语言,因此证明{a ⁿ 一 ⁿ |n>=0}是一种常规语言。而DFA将是:

我建议你读一下 why languages like {a ⁿ b ⁿ | n >= 0} are not regular .

首先将定义更改为等效 L = {a^2n | n >= 0} 。现在观察任何属于 L 只是2的倍数 a s、 然后将该定义更改为 (aa)* ,这是一个 正则表达式 因为它只使用原语来表达常规语言-单个字符( 一 ),串联( aa )和Kleene星( * ). 现在你完成了。