東京大学 情報理工学系研究科 コンピュータ科学専攻 2021年2月実施 問題3

标签：

• 东京大学
• 语言的左商
• 正则表达式
• 带 ε 转移的非确定性有限自动机
• 正则语言的封闭性质

Author

zephyr, 祭音Myyura

Description

Let $\Sigma$ be the set $\{a, b\}$ of letters. Given two languages $L_1, L_2 \subseteq \Sigma^*$, we define $L_1 \triangleleft L_2$ by:

$$L_1 \triangleleft L_2 = \{w \in \Sigma^* \mid \exists v \in L_1.vw \in L_2\}.$$

For example, if $L_1 = \{ab, bb\}$ and $L_2 = \{aa, abb, bbab\}$, then

$$L_1 \triangleleft L_2 = \{b, ab\}.$$

For a finite automaton $\mathbf{A}$, we write $\mathbf{L(A)}$ for the language accepted by $\mathbf{A}$.

Answer the following questions.

(1) Let $L_3 = \{aa, b, bb\}$ and $L_4 = \{a, b, ab, bb, aaa, bbab\}$. Give the set $L_3 \triangleleft L_4$.

(2) Let $L_5$ and $L_6$ be the languages expressed by the regular expressions $(a^*b)^*$ and $(abba)^*$, respectively. Express $L_5 \triangleleft L_6$ by using a regular expression.

(3) Let $\mathbf{A_1} = (Q_1, \Sigma, \delta_1, q_{1,0}, F_1)$ and $\mathbf{A_2} = (Q_2, \Sigma, \delta_2, q_{2, 0}, F_2)$ be deterministic finite automata. Here, $Q_i, \delta_i, q_{i, 0},$ and $F_i$ are the set of states, the transition function, the initial state, and the set of final states of $\mathbf{A_i}$ ($i \in \{1, 2\}$), respectively. Assume that the transition functions $\delta_i : Q_i \times \Sigma \rightarrow Q_i$ ($i \in \{1, 2\}$) are total. Give a non-deterministic finite automaton that accepts $\mathbf{L(A_1)} \triangleleft \mathbf{L(A_2)}$, with a brief explanation. You may use $\epsilon$-transitions.

(4) Answer whether the following statement is true:

• "For every context-free language $L$ and regular language $R$, $L \triangleleft R$ is a regular language."

Also, give a proof sketch if the answer is yes, and give a counterexample if the answer is no.

---

设 $\Sigma$ 为字母集合 $\{a, b\}$。给定两个语言 $L_1, L_2 \subseteq \Sigma^*$，我们定义 $L_1 \triangleleft L_2$ 如下：

$$L_1 \triangleleft L_2 = \{w \in \Sigma^* \mid \exists v \in L_1.vw \in L_2\}。$$

例如，如果 $L_1 = \{ab, bb\}$ 且 $L_2 = \{aa, abb, bbab\}$，则

$$L_1 \triangleleft L_2 = \{b, ab\}。$$

对于一个有限自动机 $\mathbf{A}$，我们用 $\mathbf{L(A)}$ 表示 $\mathbf{A}$ 接受的语言。回答以下问题。

(1) 设 $L_3 = \{aa, b, bb\}$ 和 $L_4 = \{a, b, ab, bb, aaa, bbab\}$。给出集合 $L_3 \triangleleft L_4$。

(2) 设 $L_5$ 和 $L_6$ 分别由正则表达式 $(a^*b)^*$ 和 $(abba)^*$ 表示。用正则表达式表示 $L_5 \triangleleft L_6$。

(3) 设 $\mathbf{A_1} = (Q_1, \Sigma, \delta_1, q_{1, 0}, F_1)$ 和 $\mathbf{A_2} = (Q_2, \Sigma, \delta_2, q_{2, 0}, F_2)$ 为确定性有限自动机。这里，$Q_i, \delta_i, q_{i, 0},$ 和 $F_i$ 是 $\mathbf{A_i}$ 的状态集合、转换函数、初态和终态集合（$i \in \{1, 2\}$）。假设转换函数 $\delta_i : Q_i \times \Sigma \rightarrow Q_i$（$i \in \{1, 2\}$）是全函数。给出一个非确定性有限自动机，该自动机接受 $\mathbf{L(A_1)} \triangleleft \mathbf{L(A_2)}$，并简要解释。你可以使用 $\epsilon$-转换。

(4) 回答以下陈述是否正确：

• “对于每个上下文无关语言 $L$ 和正则语言 $R$，$L \triangleleft R$ 是正则语言。”

如果答案是肯定的，请给出证明草图；如果答案是否定的，请给出反例。

题目描述

令 $\Sigma=\{a,b\}$。对语言 $L_1,L_2\subseteq\Sigma^*$，定义左商

$$L_1\triangleleft L_2 =\{w\in\Sigma^*\mid \text{存在 }v\in L_1\text{ 使 }vw\in L_2\}.$$

例如，若 $L_1=\{ab,bb\}$、$L_2=\{aa,abb,bbab\}$，则 $L_1\triangleleft L_2=\{b,ab\}$。记 $L(A)$ 为有限自动机 $A$ 接受的语言。 回答下列问题。

（1）令 $L_3=\{aa,b,bb\}$、 $L_4=\{a,b,ab,bb,aaa,bbab\}$，求 $L_3\triangleleft L_4$。

（2）$L_5,L_6$ 分别由正则表达式 $(a^*b)^*$ 和 $(abba)^*$ 表示。 用正则表达式表示 $L_5\triangleleft L_6$。

（3）设 DFA $A_i=(Q_i,\Sigma,\delta_i,q_{i,0},F_i)\ (i=1,2)$，且转移函数均为全函数。 构造识别 $L(A_1)\triangleleft L(A_2)$ 的 NFA 并简要说明；允许使用 $\varepsilon$ 转移。

（4）判断命题“对每个上下文无关语言 $L$ 和正则语言 $R$， $L\triangleleft R$ 都是正则语言”是否正确。若正确，给出证明概要；若错误，给出反例。

Kai

(1)

Let $L_3 = \{aa, b, bb\}$ and $L_4 = \{a, b, ab, bb, aaa, bbab\}$. We need to find the set $L_3 \triangleleft L_4$.

$$L_3 \triangleleft L_4 = \{ w \in \Sigma^* \mid \exists v \in L_3 \text{ such that } vw \in L_4 \}$$

We check each element $v\in L_3$:

1. For $v=aa$, the only word of $L_4$ having this prefix is $aaa$, so $w=a$.
2. For $v=b$, the words $b,bb,bbab$ give $w=\epsilon,b,bab$.
3. For $v=bb$, the words $bb,bbab$ give $w=\epsilon,ab$.

Collecting all possible $w$:

$$L_3 \triangleleft L_4 = \{\epsilon, a, b, ab, bab\}$$

(2)

Let $L_5 = (a^*b)^*$ and $L_6 = (abba)^*$. We need to express $L_5 \triangleleft L_6$ using a regular expression.

$L_5 \triangleleft L_6 = \{w \in \Sigma^* \mid \exists v \in L_5 \text{ such that } vw \in L_6\}$

Let's analyze this step by step:

1. Words in $L_5$ are $\epsilon$ or words ending in $b$.
2. Words in $L_6$ are repetitions of abba.
3. A prefix of a word in $L_6$ that belongs to $L_5$ is either $\epsilon$, $(abba)^t ab$, or $(abba)^t abb$ for some $t\ge0$.

The corresponding suffixes are:

• for $v=\epsilon$, any word in $(abba)^*$;
• after a prefix $(abba)^t ab$, a word in $ba(abba)^*$;
• after a prefix $(abba)^t abb$, a word in $a(abba)^*$.

Therefore,

$L_5 \triangleleft L_6 = (abba)^* \cup ba(abba)^* \cup a(abba)^*$

This can be written more compactly as:

$L_5 \triangleleft L_6 = (\epsilon + ba + a)(abba)^*$

This regular expression captures all possible suffixes that, when concatenated with a word from $L_5$, result in a word from $L_6$.

(3)

Run the product automaton $A_1\times A_2$ from $(q_{1,0},q_{2,0})$, and put

$$S=\{q\in Q_2\mid \exists v\in\Sigma^*:\delta_1^*(q_{1,0},v)\in F_1, \ \delta_2^*(q_{2,0},v)=q\}.$$

Take a copy of $A_2$, add a new initial state with $\epsilon$-transitions to every state in $S$, and retain $F_2$ as the accepting set. It accepts $w$ exactly when some $v\in L(A_1)$ satisfies $vw\in L(A_2)$.

(4)

The statement is true. Let a DFA $A=(Q,\Sigma,\delta,q_0,F)$ accept $R$, and set

$$S=\{\delta^*(q_0,v)\mid v\in L\}\subseteq Q.$$

An NFA consisting of $A$ with all states in $S$ as initial states accepts exactly $L\triangleleft R$. Since $Q$ is finite, this language is regular. (The argument in fact holds for arbitrary $L$.)

Knowledge

正则语言 上下文无关语言 NFA 正则表达式

难点思路

问题 3 和 4 可能对考生来说比较困难。

对于问题 3，先用积自动机找出 $A_2$ 在读完某个 $L(A_1)$ 中的前缀后可能处于的全部状态，再把这些状态作为读取剩余输入的初态。

对于问题 4，任意左侧语言只决定有限状态集中的哪些状态可以充当初态；因此即使左侧语言非正则，所得左商仍是正则语言。

解题技巧和信息

1. 对于涉及新定义操作的题目，先仔细理解定义，然后尝试用具体的例子来理解操作的含义。
2. 在处理正则表达式时，考虑语言中单词的结构和可能的前缀。
3. 构造 NFA 时，利用非确定性和 $\epsilon$-转移来模拟复杂的操作。
4. 区分左商两侧语言的作用：这里右侧语言的有限自动机始终用于读取剩余输入。

重点词汇

• finite automaton 有限自动机
• non-deterministic finite automaton (NFA) 非确定性有限自动机
• regular expression 正则表达式
• context-free language 上下文无关语言
• $\epsilon$-transition $\epsilon$-转移
• counterexample 反例

参考资料

1. Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Chapter 2 (Finite Automata) and Chapter 4 (Context-Free Grammars).
2. Sipser, M. (2012). Introduction to the Theory of Computation. Cengage Learning. Chapter 1 (Regular Languages) and Chapter 2 (Context-Free Languages).