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

Author

zephyr

Description

Let and . For a word , we write for the length of . We also write for the empty word (i.e., the word of length 0). For a word , we define the function by:

In other words, is the word obtained from by replacing the start position of each subword that matches with and any other position with . For example, and . Furthermore, we extend the function to the function that maps a language over to a language over by the following definition:

For example, .

Answer the following questions.

(1) Compute .

(2) Express by using a regular expression.

(3) Suppose that a word (where ) and a deterministic finite automaton are given, and that is the language accepted by . Here, are respectively the set of states, the transition function, the initial state, and the set of accepting states of . Assume that the transition function is total. Give a non-deterministic finite automaton that accepts , with a brief explanation. You may use -transitions.

(4) If the following proposition is true, then give a proof sketch (it suffices to show a pushdown automaton that accepts or a context-free grammar that generates , with a brief explanation). Otherwise, give a counterexample.

Proposition: "For every word , if is a context-free language, then is also a context-free language."

---

设 和 。对于一个单词 ，我们用 表示 的长度。我们也用 表示空字（即长度为 0 的字）。对于一个单词 ，我们定义函数 如下：

换句话说， 是从 获得的单词，通过用 替换每个匹配 的子单词的起始位置，并用 替换其他任何位置。例如， 和 。此外，我们将函数 扩展为函数 ，该函数将 上的语言映射到 上的语言，定义如下：

例如，。

回答以下问题。

(1) 计算 。

(2) 使用正则表达式表示 。

(3) 假设一个单词 （其中 ）和一个确定性有限自动机 已给出，且 是 接受的语言。这里， 分别是状态集、转移函数、初始状态和接受状态集。假设转移函数 是完全的。给出一个接受 的非确定性有限自动机，并简要解释。您可以使用 -转换。

(4) 如果以下命题为真，则给出一个证明草图（证明接受 的下推自动机或生成 的上下文无关文法即可，简要说明）。否则，给出一个反例。

命题：“对于每个单词 ，如果 是一个上下文无关语言，则 也是一个上下文无关语言。”

Kai

(1)

Let's analyze the string babababa and mark the positions where "aba" appears as a subword:

b a b a b a b a
  ^ ^ ^
      ^ ^ ^
          ^ ^ ^

Now, let's replace these starting positions with 't' and the rest with 'f':

(2)

To construct this regular expression, we need to consider all possible ways aba can appear in a string:

1. The string might start with aba:
2. There might be any number of a's or b's before ab:
3. The string might end with any number of a's or b's:

Combining these, we get:

Therefore,

(3)

Let be the given DFA that accepts . Let be the -th figure of word . We can construct an NFA that accepts as follows:

4. For the transition function :
   • For each and :
     • If and :
       • Add -transition from to
     • If and :
       • Add -transition from to
     • If :
       • Add -transition from to

This NFA simulates the DFA while keeping track of potential matches of during each of the transitions in . When a complete match is found, it accepts 't', otherwise 'f'.

(4)

This proposition is true. We can prove it by constructing a pushdown automaton (PDA) that accepts , using a similar approach to the NFA construction in Question 3.

Proof Sketch: Let be a PDA that accepts . Let be the -th symbol of word . We can construct a PDA that accepts as follows:

4. For the transition function :
   • For each :
     • If and :
       • For each , add to
     • If and :
       • For each , add to
     • If and :
       • For each and , add to

Explanation:

• Similar to the NFA construction in Question 3, the state represents that we are in state of the original PDA and have matched symbols of .
• The -transitions simulate the original PDA's transitions for matching the next symbol of .
• The -transition occurs for positions where is not matched, resetting the match counter to 0.
• The -transition occurs when we complete a match of , also resetting the match counter to 0.

This PDA simulates the computations of while keeping track of occurrences of and outputting the corresponding string in . Therefore, is context-free.

Note: The key difference between this construction and the one in Question 3 is that we're now working with a PDA instead of a DFA, which allows us to handle the stack operations necessary for context-free languages. However, the core idea of tracking partial matches of remains the same.

Knowledge

DFA NFA PDA 正则表达式 上下文无关语言 下推自动机

难点思路

1. 理解函数 和 的定义及其在字符串和语言上的作用。
2. 构造接受 的非确定性有限自动机，需要巧妙地结合原 DFA 和模式匹配。
3. 将 NFA 构造的思路扩展到 PDA，以证明 的上下文无关性。

解题技巧和信息

1. 在处理形式语言问题时，尝试从简单的例子开始，然后推广到一般情况。
2. 在构造自动机或文法时，考虑如何将问题的不同方面（如这里的 PDA 转换和模式匹配）结合起来。
3. 对于复杂的语言操作，考虑如何使用现有的形式语言工具（如 NFA、PDA）来模拟这些操作。
4. 注意识别问题之间的联系，如第三问和第四问之间的关系，可以帮助简化解题过程。
5. 在扩展 NFA 到 PDA 时，要注意保持状态转换的基本结构，同时增加对栈操作的处理。

重点词汇

• deterministic finite automaton (DFA) 确定性有限自动机
• non-deterministic finite automaton (NFA) 非确定性有限自动机
• pushdown automaton (PDA) 下推自动机
• context-free grammar (CFG) 上下文无关文法
• regular expression 正则表达式
• -transition -转换

参考资料

1. Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Chapter 2 (Finite Automata), Chapter 3 (Regular Expressions and Languages), Chapter 5 (Context-Free Grammars and Languages), Chapter 6 (Pushdown Automata)
2. Formal Languages and Automata Theory by C. K. Nagpal. Chapters on Regular Languages, Context-Free Languages, and Pushdown Automata