1.67

2024-10-01

题目

Let the rotational closure of language be

a. Show that for any language , we have b. Show that the class of regular languages is closed under rotational closure.

点击展开

a. 展开集合的定义，画出图形示意，结论显然 b. 要判断字符串是否可以围绕某个分割点前后置换，变成，这是个多选择过程，考虑构造 NFA，不同分割点的选择对应不同转移

点击展开

a. 不妨设分割点在分割点右侧，即，两个切割点将分为三段：那么所以，显然有，故

b. 设 A 对应的 DFA 为 M，有个节点，那么把 DFA 复制为份，两两配对这里假设，是 M 的接受节点，是 M 的起始节点

NFA_1.67 三个子图共同构成了最终的 NFA，每个子图代表不同旋转分割点的选择。输入，先在前半个子图中识别，需要从分割点移动到 M 的接受状态；再经过转移到后半个子图识别，需要从 M 的起始状态移动到分割点。存在这样的路径等价于能从 M 的起始状态移动到 M 的接受状态，即，