千葉大学 融合理工学府 数学情報科学専攻 数学・情報数理学コース 2019年8月実施 専門 B11

标签：

• Context-Free-Grammar
• Regular-Grammar-and-Regular-Language

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

アルファベット $\{0,1\}$ 上の言語について、(1) $\{0^n1^{2n}:n\ge0\}$ が文脈自由言語であることを示せ。(2) $\{0^n1^m:n>0,m>0,\gcd(n,m)=1\}$ が正則言語でないことを示せ。

题目描述

(1) 证明零的数量为 $n$、一的数量为 $2n$ 的语言是上下文无关语言，允许空串。(2) 证明正数个零后接正数个一且两数量互素的语言不是正则语言。

Kai

(1) 開始記号 $S$ と生成規則

$$\boxed{S\to0S11\mid\varepsilon}$$

をもつ文脈自由文法をとる。最初の規則を $n$ 回、最後に $S\to\varepsilon$ を適用すると $0^n1^{2n}$ が得られる。逆にすべての導出はこの形なので、所望の言語を生成する。

(2) Myhill–Nerode の定理を用いる。異なる素数 $p,q$ に対して接頭語 $0^p,0^q$ を考える。接尾語 $1^p$ を付けると

$$0^p1^p\notin L,\qquad0^q1^p\in L$$

である。従って相異なる素数に対応する接頭語はすべて異なる右合同類に属する。素数は無限個あるので合同類は無限個であり、$L$ は正則でない。