跳到主要内容

京都大学 情報学研究科 知能情報学専攻 2024年8月実施 専門科目 S-5

标签：

Author​

itsuitsuki

Description​

Consider deterministic finite state automata (Q,Σ,δ,q0,F)(Q, \Sigma, \delta, q_0, F), where QQ is a finite set of states, Σ\Sigma is a finite set of characters, δ:Q×Σ→Q\delta : Q \times \Sigma \to Q is a transition function, q0∈Qq_0 \in Q is a start state, and F⊆QF \subseteq Q is a set of accept states. Also, ϵ∈Σ∗\epsilon \in \Sigma^* denotes the empty string. Let Σ={0,1,2,…,9}\Sigma = \{0, 1, 2, \dots, 9\}. For w∈Σ∗w \in \Sigma^*, n(w)n(w) returns an integer number represented by ww. For example, n(52)=52n(52) = 52 and n(068)=68n(068) = 68. For ϵ\epsilon, we define n(ϵ)=0n(\epsilon) = 0.

(1) Depict the state transition diagram of a deterministic finite state automaton (∣Q∣≤2)(|Q| \leq 2) that accepts L1={w∈Σ∗∣n(w)≡0(mod2)}L_1 = \{w \in \Sigma^* \mid n(w) \equiv 0 \pmod 2\}.

(2) Depict the state transition diagram of a deterministic finite state automaton (∣Q∣≤3)(|Q| \leq 3) that accepts L2={w∈Σ∗∣n(w)≡0(mod3)}L_2 = \{w \in \Sigma^* \mid n(w) \equiv 0 \pmod 3\}.

(3) Show Q,δQ, \delta, and FF of a deterministic finite state automaton that accepts L3={w∈Σ∗∣n(w)≡0(modk)}L_3 = \{w \in \Sigma^* \mid n(w) \equiv 0 \pmod k\} for any k≥2k \geq 2. You may use mod to describe δ\delta.

(4) Let L4={w∈Σ+∣h(w)≠0 or w=0}L_4 = \{w \in \Sigma^+ \mid h(w) \neq 0 \text{ or } w = 0\}, where h(w)h(w) returns the first character of string ww. Show Q,δQ, \delta, and FF of a deterministic finite state automaton that accepts L3∩L4L_3 \cap L_4 for any k≥2k \geq 2. You may use mod to describe δ\delta.

题目描述​

考虑确定性有限自动机 (Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F)，其中 QQ 是有限状态集，Σ\Sigma 是有限字符集，δ:Q×Σ→Q\delta:Q\times\Sigma\to Q 是转移函数，q0∈Qq_0\in Q 是初始状态，F⊆QF\subseteq Q 是接受状态集；ϵ∈Σ∗\epsilon\in\Sigma^* 表示空串。

令 Σ={0,1,2,…,9}\Sigma=\{0,1,2,\ldots,9\}。对 w∈Σ∗w\in\Sigma^*，n(w)n(w) 表示字符串 ww 所代表的十进制整数，允许前导零，例如 n(52)=52n(52)=52、n(068)=68n(068)=68，并规定 n(ϵ)=0n(\epsilon)=0。

  1. 画出一个状态数满足 ∣Q∣≤2|Q|\leq2、接受语言

    L1={w∈Σ∗∣n(w)≡0(mod2)}L_1=\{w\in\Sigma^*\mid n(w)\equiv0\pmod2\}

    的确定性有限自动机状态转移图。

  2. 画出一个状态数满足 ∣Q∣≤3|Q|\leq3、接受语言

    L2={w∈Σ∗∣n(w)≡0(mod3)}L_2=\{w\in\Sigma^*\mid n(w)\equiv0\pmod3\}

    的确定性有限自动机状态转移图。

  3. 对任意 k≥2k\geq2，给出接受

    L3={w∈Σ∗∣n(w)≡0(modk)}L_3=\{w\in\Sigma^*\mid n(w)\equiv0\pmod k\}

    的确定性有限自动机的 Q,δ,FQ,\delta,F；描述 δ\delta 时可以使用取模运算。

  4. 定义

    L4={w∈Σ+∣h(w)≠0 或 w=0},L_4=\{w\in\Sigma^+\mid h(w)\ne0\ \text{或}\ w=0\},

    其中 h(w)h(w) 返回字符串 ww 的首字符。对任意 k≥2k\geq2，给出接受 L3∩L4L_3\cap L_4 的确定性有限自动机的 Q,δ,FQ,\delta,F；描述 δ\delta 时可以使用取模运算。

考点​

  • 余数自动机：以当前十进制前缀对 kk 的余数作为状态，并按读入数字更新余数。
  • 乘积自动机与前导零约束：组合整除性状态和首字符合法性状态，同时正确处理空串及单独的字符串“0”。
  • 正则语言的封闭性：通过自动机交构造体现正则语言对交运算的封闭性。
本页目录