首页 > 试题广场 >

试证明正规式 ( ab ) * a 与 a( ba ) *

[问答题]

试证明正规式 ( ab ) * a 与 a( ba ) * 是等价的。

添加回答
阿奻_头像 阿奻_

证明：

考虑 L((ab)*a) 中的任意一个串 ababab...aba ，

由串连接的结合性可得： a(ba)(ba)(b...a)(ba) ，它恰好是 L(a(ba)*) ，即 L((ab)*a)= L(a(ba)*) 。


也可以用归纳法证明（提示：以 ab 重复 0 次、 1 次作为归纳基础，假设 ab 重复 n 次成立，证明 ab 重复 n+1 次也成立）。

发表于 2017-05-17 00:58:42 回复(0)
提交观点

问题信息

编译和体系结构
上传者：阿奻_
难度：
1条回答 2985浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号