1.40

2024-10-01

 

题目

Recall that string is a prefix of string if a string exists such where , and that is a proper prefix of if in addition . In each of the following parts, we define an operation on a language . Show that the class of regular languages is closed under that operation.

a.

\mathrm{NOEXTEND}(A) = {, w \in A \mid w \text{ is not the proper prefix of any string in } A }.$$

思路

点击展开

a. 在 A 的 DFA 中添加限制：只允许到达一次接受状态，不允许多次到达。

b. 我们希望接受那些不可能通过添加后缀而到达新接受状态的字符串，一个重要的观察是，这只和字符串到达的最后一个接受状态有关。所以，必须也只需让某些接收状态失去资格，变为拒绝状态

解答

点击展开

a. 在 A 的 DFA 中删除接受状态的出边，形成新的 NFA，对应 NOPREFIX(A)

b. 在 A 的 DFA 中 同时 将满足如下条件的接受状态改为拒绝状态：存在从该状态到接受状态的路径，形成新的 DFA，对应 NOEXTEND(A)

评论区

最新评论

--