跳到主要内容

京都大学 情報学研究科 知能情報学専攻 2019年2月実施 専門科目 F1-2

Author​

祭音Myyura (co-authored with GPT 5.2 extended thinking)

Description (English)​

Give context-free grammars that generate the following languages. In all parts, the alphabet (terminal character set) is .

Q.1

Q.2

Q.3

Kai​

Q.1​

  • Terminals:
  • Nonterminals:
  • Start symbol:
  • Productions:

Here generates any binary string, i.e. .

Q.2​

A string has odd length and middle symbol iff it can be written as

Grammar (G_2)​

  • Terminals:
  • Nonterminals:
  • Start symbol:
  • Productions:

Intuition: Start with the center . Each step adds one symbol on the left and one on the right, preserving odd length and keeping the center fixed.

Q.3​

  • Terminals:
  • Nonterminals:
  • Start symbol:
  • Productions:
目录