regular-language - 当联合和连接给出相同的正则表达式时

Question

{w∈{0,1}∗|w 恰好包含一次 01}

我通过联合和连接得到结果

1*0*011*0*

或者

(1* U 0*)01(1* U 0*)

怎么来的？

标签： regular-languagecomputation-theory

Answer 1

你的两个正则表达式不等价。第一个是对的，第二个是不对的。要查看差异，请使用连接的分配属性：

r1 = 1*0*011*0*

r2 = (1* U 0*)01(1* U 0*)
   = 1*011* U 1*010* U 0*011* U 0*010*

请注意，r2 是四个子表达式的并集，每个子​​表达式都描述一种语言。每种描述的语言都是 r1 语言的子集：

1*0*011*0*    1*0*011*0*    1*0*011*0*    1*0*011*0*    
1*  011*      1*  01  0*      0*011*        0*01  1*

因此，L(r2) 是 L(r1) 的子集。已经在评论中指出 L(r1) 不是 L(r2) 的子集，通过反例（考虑字符串 0110）。

要查看 r2 是否正确，首先请注意 L(r2) 中的任何字符串都使用您的语言（01 的唯一出现是在表达式的中间，并且表达式必须生成它），然后论证任何带有此表达式必须恰好生成一个 01。归纳论证很简单，留作练习。