正则表达式 – NFA最小化,无需确定

发布时间：2020-12-14 06:27:53 所属栏目：百科来源：网络整理

导读：众所周知,如何从常规语言的NFA获得最小的DFA.但是,DFA的状态可能会呈指数级增长. 我需要的是减少NFA的一种方式,再次给予NFA,但数量较少的国家. T.I.我不需要结果是确定性的,但我希望它尽可能小,同时保留公认的语言(也许不是绝对最佳,但越小越好). 这个问题的

众所周知,如何从常规语言的NFA获得最小的DFA.但是,DFA的状态可能会呈指数级增长.

我需要的是减少NFA的一种方式,再次给予NFA,但数量较少的国家. T.I.我不需要结果是确定性的,但我希望它尽可能小,同时保留公认的语言(也许不是绝对最佳,但越小越好).

这个问题的最佳算法是什么？或者也许不是“最好的”,但至少“最简单的实施效率不高”？
或者问题是否有一个着名的名字,以便我可以自己找到好的信息来源？

我相信这个问题也被称为NFA最小化.我相信NP一般都很难.

一种富有成效的方法可能是减刺最小化[Paige,Tarjan 1987]及其后衍生物.

This presentation有一些关于问题易处理性的说明,并提到了一些方法,其中有相关优点.

（编辑：李大同）

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