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

标签：

• Pumping-Lemma
• Nondeterministic-Pushdown-Automaton
• Regular-Language-Closure-Properties

Author

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

Description

$\Sigma=\{a,b\}$ とし、$w^{\mathrm{op}}$ は語 $w$ の逆順、$L^*$ は Kleene 閉包を表す。

(1) $L=\{ww^{\mathrm{op}}\mid w\in\Sigma^*\}$ は (a) 非決定性有限状態オートマトン、(b) 非決定性プッシュダウンオートマトンで受理可能か。証明せよ。

(2) $L'=\{a^nb^m\mid0\le n\le m\}^*$ は正規言語か。証明せよ。

(3) $L''=(\{a^nb^m\mid0\le n\le m\}\cup\{b^na^m\mid0\le n\le m\})^*$ は正規言語か。証明せよ。

题目描述

在二字母表上，$w^{\mathrm{op}}$ 表示逆序，星号表示 Kleene 闭包。(1) 偶数长回文语言能否分别被非确定有限自动机和非确定下推自动机识别？证明。(2)(3) 分别判断上述两个闭包语言是否正规并证明。

Kai

(1)

(a) 受理不可能。 正規だと仮定し、ポンピング長を $p$ とする。語 $a^pbb a^p\in L$ の先頭 $p$ 文字内の非空部分を反復すると、先頭と末尾の $a$ の個数が異なり回文でなくなる。ポンピング補題に反する。

(b) 受理可能。 前半を読みながら文字をスタックへ積み、非決定的に中央を選んで後半へ移る。後半では入力文字とスタック最上段が等しいときだけ一文字ずつ取り出し、入力終了時にスタックが空なら受理する。受理される語はちょうど $ww^{\mathrm{op}}$ である。空語も受理する。

(2)

正規でない。

$$L'\cap a^*b^*=\{a^nb^m\mid0\le n\le m\}.$$

実際、$a$ を含む二つの非空ブロックを連結すると途中に $ba$ が現れるため、$a^*b^*$ 内では $a$ を含むブロックは高々一つである。

右辺が正規なら、ポンピング長 $p$ に対して $a^pb^p$ の先頭の $a$ を増やしても属するはずだが、$a$ の個数が $b$ より多くなるため矛盾する。正規言語は共通部分で閉じているので結論を得る。

(3)

正規である。 $n=0,m=1$ とすれば、和集合は一文字語 $a,b$ をともに含む。したがって $L''=\Sigma^*$ であり、正規表現 $(a\mid b)^*$ で表される。