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

Author

zephyr

Description

Let be the set of letters. Given two languages , we define by:

For example, if and , then

For a finite automaton , we write for the language accepted by .

Answer the following questions.

(1) Let and . Give the set .

(2) Let and be the languages expressed by the regular expressions and , respectively. Express by using a regular expression.

(3) Let and be deterministic finite automata. Here, and are the set of states, the transition function, the initial state, and the set of final states of (), respectively. Assume that the transition functions () are total. Give a non-deterministic finite automaton that accepts , with a brief explanation. You may use -transitions.

(4) Answer whether the following statement is true:

• "For every context-free language and regular language , is a regular language."

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

---

设 为字母集合 。给定两个语言 ，我们定义 如下：

例如，如果 且 ，则

对于一个有限自动机 ，我们用 表示 接受的语言。回答以下问题。

(1) 设 和 。给出集合 。

(2) 设 和 分别由正则表达式 和 表示。用正则表达式表示 。

(3) 设 和 为确定性有限自动机。这里， 和 是 的状态集合、转换函数、初态和终态集合（）。假设转换函数 （）是全函数。给出一个非确定性有限自动机，该自动机接受 ，并简要解释。你可以使用 -转换。

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

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

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

Kai

(1)

Let and . We need to find the set .

We check each element :

1. For :
   • Possible are
2. For :
   • Possible are
3. For :
   • Possible are

Collecting all possible :

(2)

Let and . We need to express using a regular expression.

Let's analyze this step by step:

1. Words in are of the form where and for all .
2. Words in are repetitions of .
3. The possible prefixes from that could start a word in are:

• (empty string)

Now, let's consider what would be in each case:

• If , then can be any word in , i.e.,
• If , then must start with and then continue with , i.e.,
• If , then must start with and then continue with , i.e.,

Therefore, can be expressed as the union of these possibilities:

This can be written more compactly as:

or

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

(3)

To construct a non-deterministic finite automaton (NFA) that accepts , we can follow these steps:

a) Start with the structure of .

b) Add -transitions from each state of to the initial state of .

c) Make all final states of non-final.

d) Keep the final states of as final.

Formally, we can define the NFA where:

• is the same as before
• for
• for
• for
• is the initial state of

This NFA simulates until it non-deterministically decides to switch to using an -transition, then continues in until it reaches a final state of .

(4)

The statement "For every context-free language and regular language , is a regular language" is false.

Counterexample:

Let (a context-free language that is not regular)

Let (a regular language)

Then , which is not a regular language.

This counterexample shows that the statement is false in general.

Knowledge

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

难点思路

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

对于问题 3，关键是理解如何通过 NFA 的非确定性来模拟 操作。我们使用 -转移来允许在 的任何状态 " 猜测 " 是否应该开始匹配 的部分。

对于问题 4，难点在于构造合适的反例。需要选择一个非正则的上下文无关语言，并找到一个合适的正则语言，使得它们的 操作结果仍然是非正则的。

解题技巧和信息

1. 对于涉及新定义操作的题目，先仔细理解定义，然后尝试用具体的例子来理解操作的含义。
2. 在处理正则表达式时，考虑语言中单词的结构和可能的前缀。
3. 构造 NFA 时，利用非确定性和 -转移来模拟复杂的操作。
4. 在证明语言类别相关的陈述时，寻找反例通常比证明正确性更容易。尝试使用经典的非正则上下文无关语言作为起点。

重点词汇

• finite automaton 有限自动机
• non-deterministic finite automaton (NFA) 非确定性有限自动机
• regular expression 正则表达式
• context-free language 上下文无关语言
• -transition -转移
• 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).