2017-02-26 79 views
0

感謝您提前提供任何幫助!兩個正則表達式的交集

我在學校自動機課程和我的生活不能找出兩個正則表達式的交集。我在網上查看了這裏,發現我可以爲兩種語言創建NFA,單獨讚美它們然後聯合(ise) - 在這裏不確定英語。

接下來,我恭維工會找到後續的DFA,並從中找到正則表達式,這將是交集正則表達式。但是,我正在努力解決所有這些問題。

我有一個問題在下面,我已經改變了表達式,而不是簡單地問一個教程問題。兩者都使用相同的字母表:{a,b,c,d}

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

我已經擴展了語言,試圖更好地瞭解他們。

思想: R1包含空字(ε),且長度爲2的單詞和4 R2包含空字和長度3

後續交叉點語言必須由6整除的話?

我真的不知道如何從這裏出發。如果這是最好的方法,請有人幫助我創建一個NFA。我使用在線NFA生成器,但在回顧大學教程的答案時不斷犯錯誤。在附註中,你如何證明你計算的正則表達式是正確的?

謝謝!

+0

是不是R1相當於'(A(A + d))*'?此外,它是「補充」。 – melpomene

+0

啊,好點。我現在將刪除最終的廣告。謝謝。 – user62622

+0

我剛剛意識到我不理解你的符號。 「+」是什麼意思? – melpomene

回答

0

有一個簡單的DFA爲R1:

DFA for R1

R2 =(A | B | d)*作爲@melpomene在他的評論,這意味着用字母a,b或d的任何單詞,所述所以一個DFA爲R2顯然是:

eDFA for R2

的交點是R1(R2爲是每個體a,b或d)

W¯¯ E能完成這個DFA是這樣的:

DFA for intersection