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

标签：

Author

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

アルファベット $\Sigma=\{a,b\}$ とする。

$L_1=\{a^n(ab)^m:n,m\ge0\}$ を受理する非決定性有限オートマトンを与えよ。
$L_2=\{a^nb^m:n\ge m\ge0\}$ は正則でないことを示せ。
$\operatorname{shuffle}(w)$ を文字を並べ替えて得る全語の集合とし、 $\operatorname{shuffle}(L)=\bigcup_{w\in L}\operatorname{shuffle}(w)$ とする。 $L$ が正則でも $\operatorname{shuffle}(L)$ は正則とは限らないことを示せ。

字母表为 $\{a,b\}$ 。(1) 构造接受 $a^n(ab)^m$ 的 NFA；(2) 证明 $\{a^nb^m:n\ge m\}$ 非正则；(3) 将语言中每个词的字母任意重排所得语言不一定保持正则，给出证明。

(1) 状態を $q_0,q_1,q_2$ 、初期状態を $q_0$ 、受理状態を $q_0,q_2$ とし、非空の遷移を

\delta(q_0,a)=\{q_0,q_1\},\quad\delta(q_1,b)=\{q_2\},\quad\delta(q_2,a)=\{q_1\}

とする。 $q_0$ のループで $a^n$ を読み、その後 $q_1,q_2$ の往復で $(ab)^m$ を読む。

$非決定性有限オートマトン$

(2) 正則と仮定し、ポンピング長を $p$ とする。 $a^pb^p=xyz$ 、 $|xy|\le p$ 、 $|y|>0$ なら $y=a^k$ （ $k>0$ ）。 $y$ を除くと $xz=a^{p-k}b^p\notin L_2$ となり矛盾する。

(3) (1) の正則言語 $L_1$ に対して

\operatorname{shuffle}(L_1)=\{w:|w|_a\ge|w|_b\}.

もしこれが正則なら、正則言語 $a^*b^*$ との共通部分 $L_2$ も正則となり、(2) に反する。