東京大学 情報理工学系研究科 コンピュータ科学専攻 2022年8月実施 専門科目 問題1

标签：

• Tokyo-University
• Equal-Length-Prefix-Operation
• Regular-Expression
• Context-Free-Grammar
• Context-Free-Language-Closure-Properties

Author

zephyr, 祭音Myyura

Description

Let $\Sigma$ be the set $\{a, b\}$ of letters. For a language $L \subseteq \Sigma^*$ over $\Sigma$, we define $\Gamma(L)$ as follows.

$$\Gamma(L) = \{v \in \Sigma^* \mid \exists w \in \Sigma^* \cdot (|v| = |w| \land vw \in L)\}.$$

Here, $|x|$ denotes the length of the string $x$. For example, if $L_1 = \{aa, ba, abb, abbb\}$, then $\Gamma(L_1) = \{a, b, ab\}$.

Answer the following questions.

(1) Let $L_2 = \{(ab)^n \mid n \geq 0\}$. Express $\Gamma(L_2)$ using a regular expression.

(2) Let $L_3 = \{a^n b^n a^m b^m \mid n \geq 0, m \geq 0\}$. Give a context-free grammar that generates $\Gamma(L_3)$.

(3) Let $\mathcal{M} = (Q, \Sigma, \delta, q_0, F)$ be a deterministic finite automaton, and let $L_{\mathcal{M}}$ be the language accepted by $\mathcal{M}$. Here, $Q$, $\Sigma$, $\delta$, $q_0$, and $F$ are the set of states, the transition function, the initial state, and the set of final states of $\mathcal{M}$, respectively. You may assume that the transition function $\delta : Q \times \Sigma \to Q$ is total. Give a finite automaton that accepts $\Gamma(L_{\mathcal{M}})$, with a brief explanation.

(4) If the proposition given below is true, then give how to construct a context-free grammar that generates $\Gamma(L)$, from a context-free grammar that generates $L$ (you may use push-down automata instead of context-free grammars), with a brief explanation. Otherwise, give a counterexample, with a brief explanation.

Proposition: "For every context-free language $L \subseteq \Sigma^*$, $\Gamma(L)$ is a context-free language."

---

设 $\Sigma$ 为字母集 $\{a, b\}$。对于 $\Sigma$ 上的语言 $L \subseteq \Sigma^*$，我们定义 $\Gamma(L)$ 如下。

$$\Gamma(L) = \{v \in \Sigma^* \mid \exists w \in \Sigma^* \cdot (|v| = |w| \land vw \in L)\}.$$

这里，$|x|$ 表示字符串 $x$ 的长度。例如，如果 $L_1 = \{aa, ba, abb, abbb\}$，那么 $\Gamma(L_1) = \{a, b, ab\}$。

回答以下问题。

(1) 设 $L_2 = \{(ab)^n \mid n \geq 0\}$。用正则表达式表示 $\Gamma(L_2)$。

(2) 设 $L_3 = \{a^n b^n a^m b^m \mid n \geq 0, m \geq 0\}$。给出生成 $\Gamma(L_3)$ 的上下文无关文法。

(3) 设 $\mathcal{M} = (Q, \Sigma, \delta, q_0, F)$ 为一个确定性有限自动机，并且设 $L_{\mathcal{M}}$ 为 $\mathcal{M}$ 接受的语言。这里，$Q$, $\Sigma$, $\delta$, $q_0$, 和 $F$ 分别为 $\mathcal{M}$ 的状态集合、字母表、转移函数、初始状态和终止状态集合。可以假设转移函数 $\delta : Q \times \Sigma \to Q$ 是全定义的。给出一个接受 $\Gamma(L_{\mathcal{M}})$ 的有限自动机，并简要解释。

(4) 如果以下命题为真，请给出如何从生成 $L$ 的上下文无关文法构造生成 $\Gamma(L)$ 的上下文无关文法（可以使用下推自动机代替上下文无关文法），并简要解释。否则，请给出一个反例，并简要解释。

命题: " 对于每个上下文无关语言 $L \subseteq \Sigma^*$，$\Gamma(L)$ 是一个上下文无关语言。"

题目描述

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

$$\Gamma(L) =\{v\in\Sigma^*\mid \text{存在 }w\in\Sigma^*\text{，使 }|v|=|w|\text{ 且 }vw\in L\}.$$

其中 $|x|$ 是字符串长度。例如 $L_1=\{aa,ba,abb,abbb\}$ 时， $\Gamma(L_1)=\{a,b,ab\}$。回答下列问题。

（1）令 $L_2=\{(ab)^n\mid n\ge0\}$，用正则表达式表示 $\Gamma(L_2)$。

（2）令 $L_3=\{a^nb^na^mb^m\mid n,m\ge0\}$，给出生成 $\Gamma(L_3)$ 的上下文无关文法。

（3）设 DFA $\mathcal M=(Q,\Sigma,\delta,q_0,F)$ 识别语言 $L_{\mathcal M}$，且 $\delta$ 为全函数。构造识别 $\Gamma(L_{\mathcal M})$ 的有限自动机并简要说明。

（4）判断命题“对每个上下文无关语言 $L\subseteq\Sigma^*$， $\Gamma(L)$ 仍为上下文无关语言”是否成立。若成立，说明如何由生成 $L$ 的 CFG 构造生成 $\Gamma(L)$ 的 CFG（也可改用 PDA）；若不成立，给出反例并简要解释。

Kai

(1)

If $(ab)^n=vw$ and $|v|=|w|$, then $|v|=n$. According as $n$ is even or odd,

$$v=(ab)^r\quad\text{or}\quad v=(ab)^r a.$$

Hence

$$\Gamma(L_2)=(ab)^*(\varepsilon+a).$$

(2)

The midpoint of $a^n b^n a^m b^m$ lies in the first $b$-block when $m\le n$, and in the second $a$-block when $m>n$. Thus

$$\Gamma(L_3) =\{a^n b^r\mid n\ge r\ge0\} \cup\{a^n b^n a^r\mid n,r\ge0\}.$$

It is generated by

$$\begin{aligned} S&\to A\mid BC,\\ A&\to aA\mid aAb\mid\varepsilon,\\ B&\to aBb\mid\varepsilon,\\ C&\to aC\mid\varepsilon. \end{aligned}$$

(3)

For $R\subseteq Q$, put

$$\operatorname{Pre}(R)=\{q\in Q\mid \exists c\in\Sigma:\delta(q,c)\in R\}.$$

Use the DFA with state set $Q\times2^Q$, initial state $(q_0,F)$, transition

$$(q,R)\xrightarrow{c}(\delta(q,c),\operatorname{Pre}(R)),$$

and accepting states $\{(q,R)\mid q\in R\}$. After reading $v$, its second component is

$$\{q\in Q\mid \exists w\in\Sigma^{|v|}:\delta(q,w)\in F\}.$$

It therefore accepts exactly when some such $w$ satisfies $vw\in L_{\mathcal M}$.

(4)

The proposition is false. Over $\Sigma=\{a,b\}$, regard

$$A=aa,\qquad B=ab,\qquad C=ba,\qquad D=bb$$

as fixed-length codewords, and let

$$L=\{A^nB^nC^iD^{3i}\mid n,i\ge1\}.$$

This is context-free. Intersecting its half-prefix language with the regular language $A^+B^+C^+D$ gives

$$\Gamma(L)\cap A^+B^+C^+D =\{A^nB^nC^{n+1}D\mid n\ge1\},$$

because equality of the two half-lengths gives $2n+i+1=n+2i$, hence $i=n+1$. The language on the right is not context-free: fixed-length inverse decoding and removal of the final $C,D$ would yield $\{A^nB^nC^n\mid n\ge1\}$. Since context-free languages are closed under intersection with regular languages, $\Gamma(L)$ cannot be context-free.

Knowledge

RegularExpression ContextFreeGrammar DeterministicFiniteAutomaton ContextFreeLanguage

解题技巧和信息

1. Constructing Regular Expressions: Understanding the structure of the language is crucial to forming the correct regular expression.
2. Designing CFGs: Consider the form of prefixes when designing CFGs for $\Gamma(L)$.
3. DFA Construction: For automaton-based constructions, consider pairs of states to account for parallel processing of string halves.
4. Non-context-free Languages: Remember that some operations can lead to languages that are not context-free even if the original language is.

重点词汇

• Prefix: 前缀
• Context-free grammar (CFG): 上下文无关文法
• Deterministic finite automaton (DFA): 确定性有限自动机
• Regular expression: 正则表达式

参考资料

1. Hopcroft, J.E., Motwani, R., Ullman, J.D. (2006). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. Chapter 2, 5.
2. Sipser, M. (2012). Introduction to the Theory of Computation. Cengage Learning. Chapter 2, 4.