正则表达式 – 确定两种语言是否相等[正则表达式]

发布时间：2020-12-14 05:48:44 所属栏目：百科来源：网络整理

导读：准备考试并正在解决这个问题：确定R1表示的字符串集是否是R2的子集？ R1 = (01 +10)* R2 = ((01)* + (10)*) 我的尝试： ?由于代表相同的表达,我试图证明它们是相同的 ??R1?R2 我试图显示R2与R1相同：所以我尝试了这个,使用正则表达式等价定理： ((01ε)*(1

准备考试并正在解决这个问题：

确定R1表示的字符串集是否是R2的子集？

R1 = (01 +10)*      R2 = ((01)* + (10)*)

我的尝试：
?由于代表相同的表达,我试图证明它们是相同的
??R1?R2

我试图显示R2与R1相同：
所以我尝试了这个,使用正则表达式等价定理：

((01ε)*(10ε))=(01ε)(10ε)*

现在我被卡住了,我正在考虑在这里应用关联性规则并显示出来
?(01ε)*(10ε)* =(01 10)*(εε)* =(01 10)* //我认为这一步可能是错误的

因此R2 = R1

步骤：
?(01ε)*(10ε)* =(01 10)*(εε)* =(01 10)*

我认为是错的,我认为我正在应用关联法错误,我不知道如何使用它时它就有*.任何帮助将不胜感激.请：)

解决方法

我有一段时间没有做过证明,但我认为这里有一个简单的反例证明就足够了.

首先断言R1是R2的子集(严格或不重要).

请注意,R1可以生成以下字符串(假设为OR,因此R1可以无限制地以任何模式生成01或10)：

10 01

您可以观察到在R2中不可能生成此字符串,因为R2的定义使得它必须只有01对,或者只有10对.

因此,由于R1可以在R2域之外产生字符串,因此R1不可能是R2的一个子集,严格或不严格.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!