跳到主要内容

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

Author

zephyr

Description

Let be the set of letters. For a language over , we define as follows.

Here, denotes the length of the string . For example, if , then .

Answer the following questions.

(1) Let . Express using a regular expression.

(2) Let . Give a context-free grammar that generates .

(3) Let be a deterministic finite automaton, and let be the language accepted by . Here, , , , , and are the set of states, the transition function, the initial state, and the set of final states of , respectively. You may assume that the transition function is total. Give a finite automaton that accepts , with a brief explanation.

(4) If the proposition given below is true, then give how to construct a context-free grammar that generates , from a context-free grammar that generates (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 , is a context-free language."


为字母集 。对于 上的语言 ,我们定义 如下。

这里, 表示字符串 的长度。例如,如果 ,那么

回答以下问题。

(1) 设 。用正则表达式表示

(2) 设 。给出生成 的上下文无关文法。

(3) 设 为一个确定性有限自动机,并且设 接受的语言。这里,, , , , 和 分别为 的状态集合、字母表、转移函数、初始状态和终止状态集合。可以假设转移函数 是全定义的。给出一个接受 的有限自动机,并简要解释。

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

命题: " 对于每个上下文无关语言 是一个上下文无关语言。"

Kai

(1)

Let . The language consists of strings of even length formed by repeating the substring "ab".

Solution: To find , consider what does. For each string , there exists a string of the same length such that .

Given that consists of strings of the form , the possible strings must have lengths that can be paired with some such that their concatenation results in a string from .

The key observation is that can be any prefix of strings from . This gives us the possible regular expression:

This is because for any string formed from letters and , there is a corresponding such that as long as the length condition is satisfied.

(2)

Let . This language consists of strings where the numbers of s and s are matched in pairs.

Solution: To generate , consider the strings that can form the beginning of valid strings in . Specifically, includes any prefix of that can be completed to a string in . Therefore, includes strings of the form where , , , and .

A context-free grammar generating can be defined as follows:

  • Variables:

  • Alphabet:

  • Rules:

  • Start Symbol:

This grammar generates strings in the form of prefixes of the strings in .

(3)

Let be a deterministic finite automaton (DFA) that accepts a language . We need to construct a DFA that accepts .

Solution: To construct , consider that consists of strings such that there exists some with and .

  • States: The states of will be pairs of states from , representing the DFA being in a state corresponding to the prefixes and of equal length.
  • Transitions: For each and for each letter , if and , then .
  • Start State: The start state is .
  • Final States: A pair is a final state if there exists some and such that transitions to by some string.

This DFA accepts exactly the strings in by simulating the original DFA on both halves of the string in parallel.

(4)

Proposition: "For every context-free language , is a context-free language."

Solution: The proposition is false. A counterexample can be constructed as follows:

Consider the context-free language , which is known to be context-free. However, would include strings like where do not necessarily follow the strict condition . The language can be shown to be non-context-free because it requires balancing different parts of the string in a way that a context-free grammar cannot generally handle.

This counterexample demonstrates that is not necessarily context-free even if is.

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 .
  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.