实时自动机与实数集运算的深入探究

### 实时自动机与实数集运算的深入探究 #### 1. 实时自动机基础 实时自动机（RTA）在信号处理领域有着重要的应用。首先，我们来了解一些基本概念。 - **信号定义**：在有限字母表 $V$ 上的信号 $\sigma$ 是一个函数 $\sigma : [0, e) \to V$，其中 $e$ 是非负实数，且该函数只有有限个左间断点。信号 $\sigma$ 的定义域可划分为有限个区间 $[e_{i - 1}, e_i)$，在这些区间上 $\sigma$ 为常数。我们用 $dom(\sigma)$ 表示 $\sigma$ 的定义域，$Sig(V)$ 表示 $V$ 上的信号集合。 - **信号拼接**：对于 $\sigma_1, \sigma_2 \in Sig(V)$，其定义域分别为 $[0, e_1)$ 和 $[0, e_2)$，它们的拼接 $\sigma_1; \sigma_2 = \sigma$ 的定义域为 $[0, e_1 + e_2)$，且当 $t \in [0, e_1)$ 时，$\sigma(t) = \sigma_1(t)$；当 $t \in [e_1, e_1 + e_2)$ 时，$\sigma(t) = \sigma_2(t - e_1)$。这样，$(Sig(V), “; ”, \sigma_{\epsilon})$ 构成一个非交换幺半群，其中单位元 $\sigma_{\epsilon}$ 的定义域为 $[0, 0)$。拼接操作可扩展到信号集合，并由此引出星号运算：对于 $\Sigma \subseteq Sig(V)$，$\Sigma^* = \bigcup_{n \in \mathbb{N}} \Sigma^n$，其中 $\Sigma^0 = \{\sigma_{\epsilon}\}$，$\Sigma^{n + 1} = \Sigma^n; \Sigma$。 - **实时自动机定义**：字母表 $V$ 上的实时自动机（RTA）是一个元组 $A = (Q, V, \lambda, \iota, \delta, Q_0, F)$，其中 $Q$ 是有限状态集，$\delta \subseteq Q \times Q$ 是转移关系，$Q_0, F \subseteq Q$ 分别是初始状态集和最终状态集，$\lambda : Q \to V$ 是状态标记函数，$\iota : Q \to Int_{\geq 0}^{\mathbb{Q}}$ 是区间标记函数。若 $\lambda(q) = a$，则称 $q$ 为 $a$-状态。 - **运行与语言**：长度为 $n$ 的运行是由 $\delta$ 连接的状态序列 $(q_i)_{i \in [n]}$，即 $(q_{i - 1}, q_i) \in \delta$，$\forall i \in [n]$。一个运行是可接受的，当且仅当它从 $Q_0$ 开始并在 $F$ 结束。一个运行与信号 $\sigma$ 相关联，当且仅当存在 “分割” 点 $0 = e_1 \leq \cdots \leq e_{n + 1} = e$，使得 $e_{i + 1} - e_i \in \iota(q_i)$ 且 $\sigma(t) = \lambda(q_i)$ 对于所有 $t \in (e_i, e_{i + 1})$ 和所有 $i \in [n]$。RTA $A$ 的语言 $L(A)$ 是与 $A$ 的某个可接受运行相关联的信号集合。两个 RTA 等价，当且仅当它们具有相同的语言。我们定义定时可识别语言类为 $T_{Rec}(V) = \{\Sigma \in Sig(V) | \exists A \text{ s.t. } L(A) = \Sigma\}$。 以下是一个简单的流程图展示 RTA 的运行过程： ```mermaid graph LR A[开始状态] --> B{是否在Q0} B -- 是 --> C[运行状态序列] C --> D{是否在F} D -- 是 --> E[接受信号] B -- 否 --> F[不接受信号] D -- 否 --> F ``` #### 2. 定时正则表达式与语言 - **基本定时正则表达式定义**：字母表 $V$ 上的基本定时正则表达式集合 $ETRE(V)$ 由规则 $E ::= 0 | [a]_I | E + E | E; E | E^*$ 定义，其中原子 $[a]_I$ 是所有 $a \in V$ 且 $I \in Int_{\geq 0}^{\mathbb{Q}}$ 的表达式。 - **语义解释**： - $|[a]_I| = \{\sigma \in Sig(V) | dom(\sigma) = [0, e), e \in I \text{ 且 } \forall t \in [0, e) \sigma(t) = a\}$ - $|E + F| = |E| \cup |F|$ - $|E; F| = |E|; |F|$ - $|E^*| = |E|^*$ - $|0| = \varnothing$ - **定时正则语言定义**：定时正则语言类定义为 $T_{Reg}(V) = \{\Sigma \in Sig(V) | \exists E \in ETRE(V) \text{ 使得 } |E| = \Sigma\}$。 有一个重要的定理：Kleene 定理表明 $T_{Rec}(V) = T_{Reg}(V)$。 #### 3. 实时自动机的确定性与补运算 为了研究定时可识别语言的补运算，我们需要引入一些确定性的概念。 - **确定性定义**： - **语言确定性**：一个 RTA $A$ 是语言确定的，当且仅当 $L(A)$ 中的每个信号都与唯一的运行相关联。 - **无抖动性**：一个 RTA $A$ 是无抖动的，当且仅当它没有包含 0 的时间标签，并且不存在 $\lambda(q) = \lambda(r)$ 的转移 $(q, r)$。 - **状态确定性**：一个 RTA $A$ 是状态确定的，当且仅当初始状态具有不相交的标签，并且从相同状态开始的转移也具有不相交的标签，即当 $r \neq s$ 且要么 $r, s \in Q_0$ 要么 $(q, r), (q, s) \in \delta$ 时，$\lambda(r) \neq \lambda(s)$ 或 $\iota(r) \cap \iota(s) = \varnothing$。一个 RTA 是确定的，当且仅当它既是状态确定的又是无抖动的。 需要注意的是，确定性蕴含语言确定性，但状态确定性本身并不蕴含语言确定性。而且，确定的 RTA 比一般的 RTA 表达能力弱。例如，语言 $LIN = \{\sigma : [0, n) \to \{a\} | n \in \mathbb{N}\}$ 可以被一个 RTA 接受，但不能被任何无抖动的 RTA 接受。 以下是一个表格总结 RTA 的不同确定性类型： | 确定性类型 | 定义 | | ---- | ---- | | 语言确定性 | 每个信号与唯一运行相关联 | | 无抖动性 | 无含 0 时间标签，无相同标签转移 | | 状态确定性 | 初始和转移状态标签不相交 | | 确定性 | 状态确定且无抖动 | #### 4. 实数子集的运算 - **幂集上的拼接运算**：正实数集的幂集 $P(\mathbb{R}_{\geq 0})$ 自