两个正则表达式等价的判断

来源:百度知道 编辑:UC知道 时间:2024/05/20 20:51:00
程序判断两个正则表达式是否等价(及表达的是同一种句式),如果等价返回true,否则给出一个句式说明两者的不同之处。如:(a|b)(a|b) 与aa|bb|ab 是不等价的,应返回一个句子,如ba.因为ba属于前者的句式,而后者不能表达。可以不给源程序,算法也行。如果有源程序的话另加分。

这个相当麻烦,如果你一定要做就要这样做
首先把正则表达式转化为,NFA然后NFA-〉DFA-〉SDFA
如果两个正则表达式一样,应当具有唯一的SDFA。

如果是后面的问题,应当是文法包含,目前没有听说有效解法。

关注中