两个正则表达式的交集

Question

提前感谢大家的帮助！

我在学校上了一门自动机课程，但终生找不出两个正则表达式的交集。我在网上和这里寻找，发现我可以为两种语言创建NFA，单独称赞它们，然后合并(Ise)-不确定这里的英语。

然后，我称赞并集找到了后续的DFA，并从中找到了正则表达式，即交集正则表达式。然而，我正在为这一切的计算而苦苦挣扎。

下面我有一个问题，我改变了表达方式，而不是简单地问一个教程问题。两者都使用相同的字母表：{a,b,c,d}。

让R1 = (a(a+d))*和R2 = ((a+b)+a+(a+d))*

我已经扩展了这些语言，以便更好地理解它们。

想法: R1包含空词(epsilon)，长度为2和4的词R2包含空词，长度为3的词

后续的交集语言必须能被6整除？

我真的不知道如何从这里开始。请有人能帮我创建一个NFA，如果这将是最好的方法。我使用过在线NFA生成器，但当我回顾大学的教程答案时，我总是犯错误。顺便说一下，您如何证明您计算的正则表达式是正确的？

谢谢!

Answer 1

对于R1，有一个简单的DFA：

​

​

R2=(a|b|d)*正如@melpomene在他的评论中所说，这意味着任何字母为a，b或d的单词，因此R2的DFA显然是：

​

​

交集是R1 (因为R2是包含a、b或d的每个主体)

我们可以像这样完成这个DFA：

​

​