为什么是{a^n a^n | n >= 0} 常规？

Question

我明白

{a^n b^n | n >= 0}

不规则的原因和证明。 为什么是{a^nb^n | n >= 0} 不规则？

我的一个习题的解法是：

{a^n a^n | n >= 0}

正则。我怎样才能证明这个论点？

Answer 1

是的，语言 {aⁿ aⁿ | n >= 0} 是常规语言。为了证明某种语言是正则的，可以画出它的dfa/regular expression。您可以按如下方式驱动这种语言：

因为“

anan

for

n >= 0

”与“

a2n

for n >=0”相同，即“所有符号为偶数的字符串竞赛的集合

a

”那是正则 — 正则对此的表达是

(aa)*

.

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

我建议你阅读这篇为什么语言像{aⁿ bⁿ | n >= 0} 是不规则的。

Answer 2

首先将定义更改为等价的

L = {a^2n | n >= 0}

。现在观察任何属于

L

的字符串都是 2

a

s 的倍数。然后将该定义更改为

(aa)*

，这是一个 正则表达式，因为它仅使用原语来表达正则语言——单个字符 (

a

)、连接 (

aa

) 和 Kleene 星号 (

*

)。现在你完成了。